Efficient Distributed Core Graph Decomposition

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