2011/03/28 by Alberto Montresor, Montresor, Alberto, Francesco De Pellegrini +3
Computer Science · Physics and Astronomy · #Complex Network Analysis Techniques #FOS: Computer and information sciences #Opportunistic and Delay-Tolerant Networks #Other Computer Science (cs.OH) #Peer-to-Peer Network Technologies #cs.OH
paper · pdf · doi:10.48550/arxiv.1103.5320
openalex publication_date 2011/03/28 · arxiv created 2011/03/29 · arxiv updated 2011/03/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Among the novel metrics used to study the relative importance of nodes in complex networks, k-core decomposition 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-core decomposition of a network, with the purpose of (i) enabling the run-time computation of k-cores in "live" distributed systems and (ii) allowing the decomposition, over a set of connected machines, of very large graphs, that cannot be hosted in a single machine. Lower bounds on the algorithms complexity are given, and an exhaustive experimental analysis on real-world graphs is provided.