1. Group homophily based facility location selection in geo-social networks.
- Author
-
Ma, Yuliang, Cui, Ningning, Jiang, Zhong-Zhong, Yuan, Ye, and Wang, Guoren
- Subjects
- *
VORONOI polygons , *PARALLEL algorithms , *HEURISTIC algorithms , *MEETING facilities , *SOCIAL networks - Abstract
Conditional p-center problem is one of the classical facility location problems, which aims to find p facilities meeting the given distance condition with q pre-existing facilities. It is worth noting that, with the proliferation of the social network, the effect of social factor is non-negligible. However, the state-of-the-art solutions for the conditional p-center problem fail to deal with the social-aware scenario, and the key challenge is that the existing methods are incompatible with integrating the social condition. In this paper, we first formalize the conditional p-center problem in geo-social networks (GSCpC). To tackle this problem, we develop a homophily-based relaxation algorithm by considering both social constraint and spatial constraint. Specifically, in the first phase, we propose a partition algorithm based on Voronoi diagram to conquer the social constraint. Next, in the second phase, we propose a heuristic algorithm to refine the query results by minimizing the distance. To accelerate the performance, we also propose a category-aware user grouping strategy and a spatial distance based strategy to prune the unpromising results significantly. Experimental results on real-world datasets demonstrate that our approaches are more efficient and effective compared to the benchmarks. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF