Efficient Radius-bounded Community Search in Geo-social Networks
- Publisher:
- Institute of Electrical and Electronics Engineers (IEEE)
- Publication Type:
- Journal Article
- Citation:
- IEEE Transactions on Knowledge and Data Engineering, 2020, PP, (99), pp. 1-1
- Issue Date:
- 2020-01-01
Open Access
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is open access.
Driven by real-life applications in geo-social networks, we study the problem of computing radius-bounded k-cores (RB-k-cores) that aims to find communities satisfying both social and spatial constraints. In particular, the model k-core (i.e., the subgraph where each vertex has at least k neighbors) is used to ensure the social cohesiveness, and a radius-bounded circle is used to restrict the locations of users in an RB-k-core. We explore several algorithmic paradigms to compute RB-k-cores, including a triple-vertex-based paradigm, a binary-vertex-based paradigm, and a paradigm utilizing the concept of rotating circles. The rotating-circle-based paradigm is further enhanced by several pruning techniques to achieve better efficiency. In addition, to find representative RB-k-cores, we study the diversified radius-bounded k-core search problem, which finds t RB-k-cores to cover the most number of vertices. We first propose a baseline algorithm that identifies the distinctive RB-k-cores after finding all the RB-k-cores. Beyond this, we design algorithms that can efficiently maintain the top-t candidate RB-k-cores and also achieve a guaranteed approximation ratio. Experimental studies on both real and synthetic datasets demonstrate that our proposed techniques can efficiently compute (diversified) RB-k-cores. Moreover, our techniques can be used to compute the minimum-circle-bounded k-core and significantly outperform the existing techniques.
Please use this identifier to cite or link to this item: