Hierarchical Core Decomposition in Parallel: From Construction to Subgraph Search

Chu, D; Zhang, F; Zhang, W; Lin, X; Zhang, Y

Hierarchical Core Decomposition in Parallel: From Construction to Subgraph Search

Chu, D Zhang, F Zhang, W Lin, X Zhang, Y

Permalink

Publisher:: IEEE
Publication Type:: Conference Proceeding
Citation:: 2022 IEEE 38th International Conference on Data Engineering (ICDE), 2022, 2022-May, pp. 1138-1151
Issue Date:: 2022

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

The embargo period expires on 2 Aug 2024

Adobe PDF

Download Accepted versionAdobe PDF (634.25 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Chu, D
dc.contributor.author	Zhang, F
dc.contributor.author	Zhang, W
dc.contributor.author	Lin, X
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638
dc.date	2022-05-09
dc.date.accessioned	2024-03-04T04:15:46Z
dc.date.available	2024-03-04T04:15:46Z
dc.date.issued	2022
dc.identifier.citation	2022 IEEE 38th International Conference on Data Engineering (ICDE), 2022, 2022-May, pp. 1138-1151
dc.identifier.isbn	978-1-6654-0883-7
dc.identifier.issn	1063-6382
dc.identifier.issn	2375-026X
dc.identifier.uri	http://hdl.handle.net/10453/176069
dc.description.abstract	The model of k core discovers a novel hierarchical structure of a network which has been widely applied in various areas e g sociology biology and brain science Based on the containment relations of k cores with different k the hierarchical core decomposition HCD of a graph formalizes the hierarchy of all k cores for each possible k HCD is effective in locating high quality subgraphs e g densest subgraph search and exploring particular network phenomena e g user engagement study However existing solutions of HCD are still not efficient enough for both the hierarchy construction and the subgraph search on the hierarchy In this paper we propose the first parallel construction algorithm PHCD for HCD using a new union find based paradigm and the first parallel algorithm PBKS to search high quality subgraphs from the hierarchy with respect to various community scoring metrics We prove the problem of hierarchy construction is mathcal P complete difficult to parallelize effectively Despite the negative result our PHCD has a near linear time cost and PBKS is time optimal in score computation for most community metrics Extensive experiments are conducted on 10 real world networks where our proposed parallel algorithms significantly outperform the existing solutions for both the hierarchy construction and the subgraph search
dc.language	en
dc.publisher	IEEE
dc.relation	http://purl.org/au-research/grants/arc/FT170100128
dc.relation	http://purl.org/au-research/grants/arc/DP210101393
dc.relation.ispartof	2022 IEEE 38th International Conference on Data Engineering (ICDE)
dc.relation.ispartof	IEEE International Conference on Data Engineering
dc.relation.ispartofseries	IEEE International Conference on Data Engineering
dc.relation.isbasedon	10.1109/icde53745.2022.00090
dc.rights	info:eu-repo/semantics/embargoedAccess
dc.title	Hierarchical Core Decomposition in Parallel: From Construction to Subgraph Search
dc.type	Conference Proceeding
utslib.citation.volume	2022-May
utslib.location.activity	Kuala Lumpur, Malaysia
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	2024-08-02T00:00:00+1000Z
dc.date.updated	2024-03-04T04:15:44Z
pubs.finish-date	2022-05-12
pubs.place-of-publication	Piscataway, USA
pubs.publication-status	Published
pubs.start-date	2022-05-09
pubs.volume	2022-May
dc.location	Piscataway, USA

Abstract:

The model of k core discovers a novel hierarchical structure of a network which has been widely applied in various areas e g sociology biology and brain science Based on the containment relations of k cores with different k the hierarchical core decomposition HCD of a graph formalizes the hierarchy of all k cores for each possible k HCD is effective in locating high quality subgraphs e g densest subgraph search and exploring particular network phenomena e g user engagement study However existing solutions of HCD are still not efficient enough for both the hierarchy construction and the subgraph search on the hierarchy In this paper we propose the first parallel construction algorithm PHCD for HCD using a new union find based paradigm and the first parallel algorithm PBKS to search high quality subgraphs from the hierarchy with respect to various community scoring metrics We prove the problem of hierarchy construction is mathcal P complete difficult to parallelize effectively Despite the negative result our PHCD has a near linear time cost and PBKS is time optimal in score computation for most community metrics Extensive experiments are conducted on 10 real world networks where our proposed parallel algorithms significantly outperform the existing solutions for both the hierarchy construction and the subgraph search

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

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