On Spatial-Aware Community Search

• Published in: IEEE transactions on knowledge and data engineering 2019-04, Vol.31 (4), p.783-798
• Main Authors: Fang, Yixiang, Wang, Zheng, Cheng, Reynold, Li, Xiaodong, Luo, Siqiang, Hu, Jiafeng, Chen, Xiaojun
• Format: Article
• Language: English
• Subjects: Algorithms; Apexes; Approximation; Approximation algorithms; Communities; Community search; Datasets; geo-social networks; Graph theory; Indexes; Knowledge management; Lifting equipment; Mathematical analysis; Measurement; online queries; Search problems; Searching; Social network services; Social networks; spatial graphs; Urban areas
• ISSN: 1041-4347; 1558-2191
• DOI: 10.1109/TKDE.2018.2845414

Communities are prevalent in social networks, knowledge graphs, and biological networks. Recently, the topic of community search (CS) has received plenty of attention. The CS problem aims to look for a dense subgraph that contains a query vertex. Existing CS solutions do not consider the spatial extent of a community. They can yield communities whose locations of vertices span large areas. In applications that facilitate setting social events (e.g., finding conference attendees to join a dinner), it is important to find groups of people who are physically close to each other, so it is desirable to have a spatial-aware community (or SAC), whose vertices are close structurally and spatially. Given a graph G and a query vertex q , we develop an exact solution to find the SAC containing q , but it cannot scale to large datasets, so we design three approximation algorithms. We further study the problem of continuous SAC search on a "dynamic spatial graph," whose vertices' locations change with time, and propose three fast solutions. We evaluate the solutions on both real and synthetic datasets, and the results show that SACs are better than communities returned by existing solutions. Moreover, our approximation solutions perform accurately and efficiently.