Distributed k-Core Decomposition

被引：131
作者：
Montresor, Alberto [1 ]
De Pellegrini, Francesco [2 ]
Miorandi, Daniele [2 ]
机构：
[1] Univ Trento, Dept Comp Sci & Engn, I-38123 Trento, Italy
[2] CREATE NET, I-38123 Povo, Italy
来源：
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS | 2013年 / 24卷 / 02期
关键词：
k-Core decomposition; graph analysis; bulk synchronous parallel;
D O I：
10.1109/TPDS.2012.124
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
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 "live" distributed systems. Lower bounds on the algorithms complexity are given, and an exhaustive experimental analysis on real-world data sets is provided.
引用
收藏
页码：288 / 300
页数：13
相关论文
共 27 条
[1]  
[Anonymous], 2010, Proceedings of the 19th International Conference on World Wide Web, WWW'10, DOI DOI 10.1145/1772690.1772778
[2]  
[Anonymous], 2006, NIPS
[3]   Analyzing yeast protein-protein interaction data obtained from different sources [J].
Bader, GD ;
Hogue, CWV .
NATURE BIOTECHNOLOGY, 2002, 20 (10) :991-997
[4]   Fast algorithms for determining (generalized) core groups in social networks [J].
Batagelj, Vladimir ;
Zaversnik, Matjaz .
ADVANCES IN DATA ANALYSIS AND CLASSIFICATION, 2011, 5 (02) :129-145
[5]  
Caceres E, 1997, LECT NOTES COMPUT SC, V1256, P390
[6]  
Cheatham T., 1995, Proceedings of the Twenty-Eighth Hawaii International Conference on System Sciences, P268, DOI 10.1109/HICSS.1995.375451
[7]  
Cheng J, 2011, PROC INT CONF DATA, P51, DOI 10.1109/ICDE.2011.5767911
[8]  
Czajkowski G., 2009, P 28 ACM S PRINC DIS
[9]  
Dean J, 2004, USENIX ASSOCIATION PROCEEDINGS OF THE SIXTH SYMPOSIUM ON OPERATING SYSTEMS DESIGN AND IMPLEMENTATION (OSDE '04), P137
[10]  
Dorogovtsev S.N., 2006, Physical Review Letters, V96, P4, DOI DOI 10.1103/PHYSREVLETT.96.040601
123