Efficient Distributed Core Graph Decomposition

Zhang, W; Yang, Z; Wen, D; Wang, X

Efficient Distributed Core Graph Decomposition

Zhang, W Yang, Z Wen, D

Wang, X

Permalink

Publisher:: IEEE
Publication Type:: Conference Proceeding
Citation:: 2023 IEEE International Conference on Data Mining Workshops (ICDMW), 2024, 00, pp. 1023-1031
Issue Date:: 2024-02-06

Closed Access

	Filename	Description	Size
	1708345.pdf	Published version	904.17 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Zhang, W
dc.contributor.author	Yang, Z
dc.contributor.author	Wen, D https://orcid.org/0000-0002-0903-1503
dc.contributor.author	Wang, X
dc.contributor.editor	Pedrycz, W
dc.contributor.editor	Wang, J
dc.contributor.editor	He, Y
dc.contributor.editor	Dinh, TN
dc.contributor.editor	Grant, C
dc.contributor.editor	Qiu, M
dc.date	2023-12-04
dc.date.accessioned	2024-05-13T04:27:51Z
dc.date.available	2024-05-13T04:27:51Z
dc.date.issued	2024-02-06
dc.identifier.citation	2023 IEEE International Conference on Data Mining Workshops (ICDMW), 2024, 00, pp. 1023-1031
dc.identifier.isbn	979-8-3503-8165-8
dc.identifier.issn	2375-9232
dc.identifier.issn	2375-9259
dc.identifier.uri	http://hdl.handle.net/10453/178913
dc.description.abstract	Core decomposition is one of the most fundamental problems in graph analytics which is associated with numerous applications such as community detection protein network analysis and system structure analysis As the sizes of graphs are becoming increasingly large it is challenging to compute core decomposition on a single machine In this paper we study the problem of k Core decomposition in the distributed environment Specifically we propose the distributed Filter Array k Core FAkCore algorithm which adopts the commonly used Scatter Gather framework We design an auxiliary data structure of running counts for each vertex to track the statistics of its neighbors core number It allows us to recompute the core number of a vertex only when the value is updated Together with an enhanced message filtering mechanism our method significantly reduces redundant computation and communication in the existing distributed k Core decomposition algorithm Experiments on 10 real world graphs show that our method outperforms the baseline algorithms by 1 4 times on average and up to 2 2 times
dc.language	en
dc.publisher	IEEE
dc.relation.ispartof	2023 IEEE International Conference on Data Mining Workshops (ICDMW)
dc.relation.ispartof	2023 IEEE International Conference on Data Mining Workshops
dc.relation.ispartofseries	International Conference on Data Mining Workshops
dc.relation.isbasedon	10.1109/icdmw60847.2023.00135
dc.rights	info:eu-repo/semantics/closedAccess
dc.title	Efficient Distributed Core Graph Decomposition
dc.type	Conference Proceeding
utslib.citation.volume	00
utslib.location.activity	Shanghai, China
pubs.organisational-group	University of Technology Sydney
pubs.organisational-group	University of Technology Sydney/Faculty of Engineering and Information Technology
utslib.copyright.status	closed_access	*
dc.date.updated	2024-05-13T04:27:49Z
pubs.finish-date	2023-12-04
pubs.place-of-publication	Piscataway, USA
pubs.publication-status	Published
pubs.start-date	2023-12-04
pubs.volume	00
dc.location	Piscataway, USA

Abstract:

Core decomposition is one of the most fundamental problems in graph analytics which is associated with numerous applications such as community detection protein network analysis and system structure analysis As the sizes of graphs are becoming increasingly large it is challenging to compute core decomposition on a single machine In this paper we study the problem of k Core decomposition in the distributed environment Specifically we propose the distributed Filter Array k Core FAkCore algorithm which adopts the commonly used Scatter Gather framework We design an auxiliary data structure of running counts for each vertex to track the statistics of its neighbors core number It allows us to recompute the core number of a vertex only when the value is updated Together with an enhanced message filtering mechanism our method significantly reduces redundant computation and communication in the existing distributed k Core decomposition algorithm Experiments on 10 real world graphs show that our method outperforms the baseline algorithms by 1 4 times on average and up to 2 2 times

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

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