Keyword-Centric Community Search

Zhiwei Zhang, Xin Huang, Jianliang Xu, Byron Choi, Zechao Shang

2019 · 47 citations · 22 references

Concepts

Abstract

Community search that finds only the communities pertaining to the query input has been widely studied from simple graphs to attributed graphs. However, a significant limitation of previous studies is that they all require the input of query nodes, which makes it difficult for users to specify exact queries if they are unfamiliar with the queried graph. To address this issue, in this paper we study a novel problem of keyword-centric community search (KCCS) over attributed graphs. In contrast to prior studies, no query nodes, but only query keywords, need to be specified to discover relevant communities. Specifically, given an attributed graph G, a query Q consisting of query keywords W <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Q</sub> , and an integer k, KCCS serves to find the largest subgraph of k-core of G that achieves the strongest keyword closeness w.r.t. W <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Q</sub> . We design a new function of keyword closeness and propose efficient algorithms to solve the KCCS problem. Furthermore, a novel core-based inverted index is developed to optimize performance. Extensive experiments on large real networks demonstrate that our solutions are more than three times faster than the baseline approach, and can find cohesive communities closely related to the query keywords.

References

22