Keyword-Covered Group Enlargement Community Search
Abstract
The goal of community search across attributed graphs is to locate the community that takes both attribute cohensiveness and constrained structure into account. The keyword closeness of subgraph is usually measured by similarity distance. However, existing works focus on how to find a community that has most relevant to the keywords of the query vertex through the similarity score, whereas we pay more attention to a community that can jointly cover keywords and find subgraph with the maximum core. To address this problem, we propose a novel query keyword-covered group enlargement community search . Given an initial subgraph and a set of query keywords, the search aims to find the community which satisfies the following conditions: (1) it jointly covers all query keywords; (2) it is a subgraph with the maximum core; (3) it is added the minimum vertex set that meets the conditions (1) and (2). We design a baseline enumerateKGEC algorithm (), which enumerates all the vertex combinations that cover the remaining query keywords. To further accelerate the search speed, we propose two heuristic algorithms candidate set-based algorithm and candidate set and keyword combination algorithm , which can effectively speed up the search and find a feasible solution. Finally, we evaluate the performance of our algorithms on two real datasets and show effectiveness and efficiency of our algorithms for problem.
This paper was recommended by Regional Editor Takuro Sato.
