Group homophily based facility location selection in geo-social networks

Yuliang Ma, Ningning Cui, Zhong-Zhong Jiang, Ye Yuan, Guoren Wang

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.
BibTeX
@inproceedings{ma2023group,
  author = {Yuliang Ma and Ningning Cui and Zhong-Zhong Jiang and Ye Yuan and Guoren Wang},
  title = {{Group homophily based facility location selection in geo-social networks}},
  booktitle = {The Web Conference},
  year = {2023},
  url = {https://openreview.net/forum?id=E8zE1vii49W},
}

Loading related content...

Figure