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

J. IGNACIO ALVAREZ-HAMELIN, LUCA DALL'ASTA, ALAIN BARRAT, ALESSANDRO VESPIGNANI

Vancouver

Conferencia; Advances in Neural Information Processing Systems 18; 2005

Neural Information Processing Systems Foundation

We use the k-core decomposition to develop algorithms for the analysis of large scale complex networks. This decomposition, based on a recursive pruning of the least connected vertices, allows to disentangle the hierarchical structure of networks by progressively focusing on their central cores. By using this strategy we develop a general visualization algorithm that can be used to compare the structural properties of various networks and highlight their hierarchical structure. The low computationalcomplexity of the algorithm, O(n + e), where n is the size of the network, 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.