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

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.

References in corpus (14)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Assortative mixing in networks
• Who is the best connected scientist? A study of scientific coauthorship networks
• Dynamical and correlation properties of the Internet
• Universal Behavior of Load Distribution in Scale-free Networks
• New Model of Internet Topology Using k-shell Decomposition
• MEDUSA - New Model of Internet Topology Using k-shell Decomposition
• k-core organization of complex networks
• An O(m) Algorithm for Cores Decomposition of Networks
• k-core decomposition: a tool for the visualization of large scale networks
• Exploring networks with traceroute-like probes: theory and simulations
• Lessons from Three Views of the Internet Topology
• Network Inference from TraceRoute Measurements: Internet Topology `Species'