Distributed k-core decomposition

• DOI: 10.1145/1993806.1993836
• Publication Date: 2011-06-08T14:36:21Z
• Authors: Alberto Montresor; Francesco De Pell...; Daniele Miorandi
• Keywords: Modular decomposition

Among the novel metrics used to study relative importance of nodes in complex networks, k-core decomposition has found a number applications areas as diverse sociology, proteinomics, graph visualization, and distributed system analysis design. This paper proposes new algorithms for computation network, with purpose (i) enabling run-time k-cores "live" systems (ii) allowing decomposition, over set connected machines, very large graphs, that cannot be hosted single machine. Lower bounds on complexity are given, an exhaustive experimental real-world graphs is provided.