K-core decomposition of Internet graphs: hierarchies, self-similarity and measurement biases

José Ignacio Alvarez-Hamelin; Luca Dall'Asta; Alain Barrat; Alessandro Vespignani

doi:10.3934/nhm.2008.3.371

Article Contents

2008, Volume 3, Issue 2: 371-393. Doi: 10.3934/nhm.2008.3.371

This issue Previous Article Viable flux distribution in metabolic networks Next Article Spectral plot properties: Towards a qualitative classification of networks

K-core decomposition of Internet graphs: hierarchies, self-similarity and measurement biases

1.
CONICET and Facultad de Ingeniería, Universidad de Buenos Aires, Paseo Colón 850, C1063ACV Ciudad de Buenos Aires
2.
Abdus Salam International Center for Theoretical Physics, Strada Costiera 11, 34014 Trieste
3.
LPT (UMR du CNRS 8627), Université de Paris-Sud
4.
School of Informatics, Indiana University, Bloomington, IN 47048

Received: February 2008

Revised: March 2008

Published: June 2008

Abstract / Introduction Related Papers Cited by

Abstract

We consider the $k$-core decomposition of network models and Internet graphs at the autonomous system (AS) level. The k-core analysis allows to characterize networks beyond the degree distribution and uncover structural properties and hierarchies due to the specific architecture of the system. We compare the $k$-core structure obtained for AS graphs with those of several network models and discuss the differences and similarities with the real Internet architecture. The presence of biases and the incompleteness of the real maps are discussed and their effect on the $k$-core analysis is assessed with numerical experiments simulating biased exploration on a wide range of network models. We find that the $k$-core analysis provides an interesting characterization of the fluctuations and incompleteness of maps as well as information helping to discriminate the original underlying structure.

Keywords:

k-core decomposition,
Internet maps.

Mathematics Subject Classification: 68R10, 05C90, 68M07.

Citation:

Article Metrics

HTML views() PDF downloads(136) Cited by(0)

K-core decomposition of Internet graphs: hierarchies, self-similarity and measurement biases

Abstract

Access History

Article Metrics

Access History

Other Articles By Authors

Catalog

K-core decomposition of Internet graphs: hierarchies, self-similarity and measurement biases

Abstract

Access History

SHARE

Article Metrics

Access History

Other Articles By Authors

Catalog

Export File

Citation

Format

Content