Back to Search
Start Over
Efficient Radius-Bounded Community Search in Geo-Social Networks.
- Source :
-
IEEE Transactions on Knowledge & Data Engineering . Sep2022, Vol. 34 Issue 9, p4186-4200. 15p. - Publication Year :
- 2022
-
Abstract
- Driven by real-life applications in geo-social networks, we study the problem of computing radius-bounded $k$ k -cores (RB- $k$ k -cores) that aims to find communities satisfying both social and spatial constraints. In particular, the model $k$ k -core (i.e., the subgraph where each vertex has at least $k$ 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$ k -core. We explore several algorithmic paradigms to compute RB- $k$ 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$ k -cores, we study the diversified radius-bounded $k$ k -core search problem, which finds $t$ t RB- $k$ k -cores to cover the most number of vertices. We first propose a baseline algorithm that identifies the distinctive RB- $k$ k -cores after finding all the RB- $k$ k -cores. Beyond this, we design algorithms that can efficiently maintain the top- $t$ t candidate RB- $k$ 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$ k -cores. Moreover, our techniques can be used to compute the minimum-circle-bounded $k$ k -core and significantly outperform the existing techniques. [ABSTRACT FROM AUTHOR]
- Subjects :
- *APPROXIMATION algorithms
*COMMUNITIES
*EUCLIDEAN distance
*SOCIAL networks
Subjects
Details
- Language :
- English
- ISSN :
- 10414347
- Volume :
- 34
- Issue :
- 9
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Knowledge & Data Engineering
- Publication Type :
- Academic Journal
- Accession number :
- 158405980
- Full Text :
- https://doi.org/10.1109/TKDE.2020.3040172