| Summary: | Searching for neighbors for a query node in a spatial network is a fundamental problem and has been extensively investigated. However, most existing works focus only on the node level when conducting such a query and rarely pay attention to the social relations among the neighbors. We argue that a user, in some cases, is more likely to engage in some activities collectively, i.e., going to the bar with friends rather than alone. For this reason, we consider the neighbor searching problem at a community level in this paper and examine a new problem: Neighboring Geosocial Communities Search (NGCS) over large spatial graphs. Specifically, given a parameter <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> and query node <inline-formula> <tex-math notation="LaTeX">$q$ </tex-math></inline-formula>, we aim to find the top-<inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> nearest communities for <inline-formula> <tex-math notation="LaTeX">$q$ </tex-math></inline-formula>. Moreover, in each returned community, nodes have cohesive relations with each other and are covered by a minimum covering circle (MCC) whose radius is less than <inline-formula> <tex-math notation="LaTeX">$r$ </tex-math></inline-formula>. It is obvious that the NGCS problem finds its standard applications in marketing and other scenarios but it is very challenging for large spatial graphs because it requires detecting all qualified cohesive user communities. Therefore, in this paper, we adopt a local search approach to reduce the difficulty. The introduced algorithm finds the top-<inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> neighboring geo-social communities through a progressive search in the graph without thoroughly examining the graph. Analyses show that the complexity of the algorithm is decreased by an order of magnitude. Extensive experiments on real social networks confirm the superiority and effectiveness of our solutions.
|
|---|