Cohesive Subgraph Search Using Keywords in Large Networks

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

Cohesive Subgraph Search Using Keywords in Large Networks

Zhu, Y Zhang, Q Qin, L

Chang, L Yu, JX

Permalink

Publisher:: Institute of Electrical and Electronics Engineers
Publication Type:: Journal Article
Citation:: IEEE Transactions on Knowledge and Data Engineering, 2021, 34, (1), pp. 178-191
Issue Date:: 2021

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

The embargo period expires on 31 Mar 2022

Adobe PDF

Download Accepted versionAdobe PDF (3.54 MB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Zhu, Y
dc.contributor.author	Zhang, Q
dc.contributor.author	Qin, L https://orcid.org/0000-0001-6068-5062
dc.contributor.author	Chang, L
dc.contributor.author	Yu, JX
dc.date.accessioned	2022-01-31T04:38:22Z
dc.date.available	2022-01-31T04:38:22Z
dc.date.issued	2021
dc.identifier.citation	IEEE Transactions on Knowledge and Data Engineering, 2021, 34, (1), pp. 178-191
dc.identifier.issn	1041-4347
dc.identifier.issn	1558-2191
dc.identifier.uri	http://hdl.handle.net/10453/153942
dc.description.abstract	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 <formula><tex>${k}$</tex></formula>-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 <formula><tex>${G_{den}}$</tex></formula>. Then, we develop a novel refinement approach to extract minimal dense truss from <formula><tex>${G_{den}}$</tex></formula>, 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.
dc.language	English
dc.publisher	Institute of Electrical and Electronics Engineers
dc.relation	http://purl.org/au-research/grants/arc/DP160101513
dc.relation.ispartof	IEEE Transactions on Knowledge and Data Engineering
dc.relation.isbasedon	10.1109/TKDE.2020.2975793
dc.rights	info:eu-repo/semantics/embargoedAccess
dc.subject	08 Information and Computing Sciences
dc.subject.classification	Information Systems
dc.title	Cohesive Subgraph Search Using Keywords in Large Networks
dc.type	Journal Article
utslib.citation.volume	34
utslib.for	08 Information and Computing Sciences
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 - AAII - Australian Artificial Intelligence Institute
utslib.copyright.status	open_access	*
pubs.consider-herdc	false
utslib.copyright.embargo	2022-03-31T00:00:00+1000Z
dc.date.updated	2022-01-31T04:38:20Z
pubs.issue	1
pubs.publication-status	Published
pubs.volume	34
utslib.citation.issue	1

Abstract:

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.

Please use this identifier to cite or link to this item:

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