← Publications
workshop2023

Efficient Distributed Core Graph Decomposition

Wenqian Zhang, Zhengyi Yang*, Dong Wen, Xiaoyang Wang

International Workshop on Complex Heterogeneous Data Mining (CHDM)

RAIDS Lab Authors

Zhengyi Yang
Zhengyi Yang
(corresponding author)
Director

Details

Year
2023
Venue
International Workshop on Complex Heterogeneous Data Mining (CHDM)
Host Conference
IEEE International Conference on Data Mining (ICDM 2023)
Publisher
Institute of Electrical and Electronics Engineers (IEEE)
Host Rankings
ICORE 2026 A* · CORE 2023 A* · CCF B

Research Area

Scalable Data Systems

Tags

GraphCore DecompositionDistributed

Resources

DOI ↗

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.

Author Affiliations

Wenqian Zhang
University of New South Wales
Zhengyi Yang
University of New South Wales
Dong Wen
University of New South Wales
Xiaoyang Wang
University of New South Wales

BibTeX

@inproceedings{zhang2023efficient,
  title = {Efficient Distributed Core Graph Decomposition},
  author = {Zhang, Wenqian and Yang, Zhengyi and Wen, Dong and Wang, Xiaoyang},
  url = {http://dx.doi.org/10.1109/ICDMW60847.2023.00135},
  doi = {10.1109/icdmw60847.2023.00135},
  booktitle = {2023 IEEE International Conference on Data Mining Workshops (ICDMW)},
  publisher = {IEEE},
  year = {2023},
  month = Dec,
  pages = {1023-1031}
}