Large scale networks fingerprinting and visualization using the k-core decomposition

Part of Advances in Neural Information Processing Systems 18 (NIPS 2005)

Bibtex Metadata Paper

Authors

J. Alvarez-hamelin, Luca Dall'asta, Alain Barrat, Alessandro Vespignani

Abstract

We use the k-core decomposition to develop algorithms for the analysis of large scale complex networks. This decomposition, based on a re- cursive pruning of the least connected vertices, allows to disentangle the hierarchical structure of networks by progressively focusing on their cen- tral cores. By using this strategy we develop a general visualization algo- rithm that can be used to compare the structural properties of various net- works and highlight their hierarchical structure. The low computational complexity of the algorithm, O(n + e), where n is the size of the net- work, and e is the number of edges, makes it suitable for the visualization of very large sparse networks. We show how the proposed visualization tool allows to find specific structural fingerprints of networks.