Efficient Distributed Core Graph Decomposition
- 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 |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
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: