.png){kind=icon}
.png){kind=icon}
Return
Cohesive Subgraph Search Using Keywords in Large Networks
.png){kind=icon}
PRE
AI
DOI：10.1109/TKDE.2020.2975793.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Keyword search has been widely studied to retrieve relevant substructures from graphs for a given set of keywords. However, existingwell-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 = {w(1), w(2), . . .. w(l)}, 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.
Keywords:
Cohesive subgraph
subgraph search
keyword search
graph database
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
10.4
Papers:
6.7K
Citations:
3.2W
Organization
View more organizations