Querying cohesive subgraphs by keywords
- Publication Type:
- Conference Proceeding
- Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018, 2018, pp. 1328 - 1331
- Issue Date:
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is currently unavailable due to the publisher's embargo.
The embargo period expires on 24 Oct 2020
© 2018 IEEE. Keyword search problem has been widely studied to retrieve related substructures from graphs for a keyword set. However, existing well-studied approaches aim at finding compact trees/subgraphs containing the keywords, and ignore a critical measure, density, to reflect how strongly and stablely the keyword nodes are connected in the substructure. In this paper, we study the problem of finding a cohesive subgraph containing the query keywords based on the k-Truss model, and formulate it as minimal dense truss search problem, i.e., finding minimal subgraph with maximum trussness covering the keywords. We first propose an efficient algorithm to find the dense truss with the maximum trussness containing keywords based on a novel hybrid KT-Index (Keyword-Truss Index). Then, we develop a novel refinement approach to extract the minimal dense truss based on the anti-monotonicity property of k-Truss. Experimental studies on real datasets show the outperformance of our method.
Please use this identifier to cite or link to this item: