Paper Info
Title
On Spatial-Aware Community Search
Abstract
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 <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">spatial-aware community</italic> (or SAC), whose vertices are close structurally and spatially. Given a graph <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$G$</tex-math><alternatives><inline-graphic xlink:href="fang-ieq1-2845414.gif"/></alternatives></inline-formula> and a query vertex <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$q$</tex-math><alternatives><inline-graphic xlink:href="fang-ieq2-2845414.gif"/></alternatives></inline-formula> , we develop an exact solution to find the SAC containing <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$q$</tex-math><alternatives><inline-graphic xlink:href="fang-ieq3-2845414.gif"/></alternatives></inline-formula> , 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.
Year
DOI
Venue
2019
10.1109/TKDE.2018.2845414
IEEE Transactions on Knowledge and Data Engineering
Keywords
Field
DocType
Approximation algorithms,Search problems,Measurement,Social network services,Indexes,Lifting equipment,Urban areas
Social group,Community search,Approximation algorithm,Graph,Data mining,Social network,Lifting equipment,Vertex (geometry),Computer science,Biological network
Journal
Volume
Issue
ISSN
31
4
1041-4347
Citations 
PageRank 
References 
3
0.37
18
Authors
7
Name
Order
Citations
PageRank
Yixiang Fang122723.06
Zheng Wang263093.98
Reynold Cheng33069154.13
Xiaodong Li4553.89
Siqiang Luo524014.59
Jiafeng Hu616210.87
Xiaojun Chen71298107.51