Cohesive Subgraph Search Using Keywords in Large Networks

Keyword search has been widely studied to retrieve relevant substructures from graphs for a given set of keywords. However, existing well-studied approaches aim at finding compact trees/subgraphs containing the keywords, and ignore a critical measure, density, to represent how strongly and stably the keyword nodes are connected in the substructure. In this paper, given a set of keywords
$Q = \lbrace w_1, w_2, \ldots, w_l\rbrace$
, we study the problem of finding a cohesive subgraph containing
$Q$
with high density and compactness from a graph
$G$
. We model the cohesive subgraph based on a carefully chosen
$k$
-truss model, and formulate the problem of finding cohesive subgraphs for keyword queries as
minimal dense truss
search problem, i.e., finding minimal subgraph that maximizes the trussness covering
$Q$
. However, unlike
$k$
-truss based community search that can be efficiently done based on the local search from a given set of nodes,
minimal dense truss
search for keyword queries is a nontrivial task as the subset of keyword nodes to be included in the retrieved substructure is previously unknown. To tackle this problem, we first design a novel hybrid KT-Index to keep the keyword and truss information compacly, and then propose an efficient algorithm that carries the search on KT-Index directly to find the dense truss with the maximum trussness
$G_{den}$
without repeated accesses to the original graph. Then, we develop a novel refinement approach to extract minimal dense truss from the dense truss
$G_{den}$
, by checking each node at most once based on the anti-monotonicity property derived from
$k$
-truss, together with several optimization strategies including batch based deletion, early-stop based deletion, and local exploration. Moreover, we also extend the proposed method to deal with the top-
$r$
search. Extensive experimental studies on real-world networks validated the effectiveness and efficiency of our approaches.