Cohesive Subgraph Search Using Keywords in Large Networks

IEEE Keyword search problem has been widely studied to retrieve relevant substructures from graphs. However, existing approaches aim at finding compact trees/subgraphs containing the keywords, and ignore density to evaluate how strongly and stablely the keyword nodes are connected. In this paper, we study the problem of finding cohesive subgraph containing query keywords with high density and compactness, and formulate it as minimal dense truss search problem based on k-truss model. However, unlike ${k}$-truss based community search that can be efficiently done by local search from a given set of nodes, this problem is nontrivial as the keyword nodes to be included in the retrieved substructure is previously unknown. To tackle this problem, we first design a novel hybrid KT-Index that keeps the keyword and truss information compactly to support efficient search of dense truss with the maximum trussness ${G_{den}}$. Then, we develop a novel refinement approach to extract minimal dense truss from ${G_{den}}$, by checking each node at most once based on the anti-monotonicity property of k-truss, together with several optimization strategies including batch based deletion, early-stop based deletion, and local exploration. Extensive experimental studies on real-world networks validated the effectiveness and efficiency of our approaches