Querying cohesive subgraphs by keywords

Zhu, Y; Zhang, Q; Qin, L; Chang, L; Yu, JX

Querying cohesive subgraphs by keywords

Zhu, Y Zhang, Q Qin, L

Chang, L Yu, JX

Permalink

Publication Type:: Conference Proceeding
Citation:: Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018, 2018, pp. 1328 - 1331
Issue Date:: 2018-10-24

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Accepted Manuscript versionAdobe PDF (739.7 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Zhu, Y	en_US
dc.contributor.author	Zhang, Q	en_US
dc.contributor.author	Qin, L https://orcid.org/0000-0001-6068-5062	en_US
dc.contributor.author	Chang, L	en_US
dc.contributor.author	Yu, JX	en_US
dc.date.available	2020-10-24T18:05:22Z
dc.date.issued	2018-10-24	en_US
dc.identifier.citation	Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018, 2018, pp. 1328 - 1331	en_US
dc.identifier.isbn	9781538655207	en_US
dc.identifier.uri	http://hdl.handle.net/10453/131178
dc.description.abstract	© 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.	en_US
dc.relation.ispartof	Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018	en_US
dc.relation.isbasedon	10.1109/ICDE.2018.00141	en_US
dc.rights	info:eu-repo/semantics/openAccess
dc.title	Querying cohesive subgraphs by keywords	en_US
dc.type	Conference Proceeding
utslib.for	0805 Distributed Computing	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - CAI - Centre for Artificial Intelligence
utslib.copyright.status	open_access	*
pubs.publication-status	Published	en_US

Abstract:

© 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:

http://hdl.handle.net/10453/131178