Distributed k-Core Decomposition

作者：Montresor Alberto^*; De Pellegrini Francesco; Miorandi Daniele

来源：IEEE Transactions on Parallel and Distributed Systems, 2013, 24(2): 288-300.

DOI：10.1109/TPDS.2012.124

• k-Core decomposition
• graph analysis
• bulk synchronous parallel

Several novel metrics have been proposed in recent literature in order to study the relative importance of nodes in complex networks. Among those, k-coreness has found a number of applications in areas as diverse as sociology, proteinomics, graph visualization, and distributed system analysis and design. This paper proposes new distributed algorithms for the computation of the k-coreness of a network, a process also known as k-core decomposition. This technique 1) allows the decomposition, over a set of connected machines, of very large graphs, when size does not allow storing and processing them on a single host, and 2) enables the runtime computation of k-cores in %26quot;live%26quot; distributed systems. Lower bounds on the algorithms complexity are given, and an exhaustive experimental analysis on real-world data sets is provided.

• 出版日期2013-2