Group homophily based facility location selection in geo-social networks

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.