A model of Internet topology using k-shell decomposition

By S. Carmi, Shlomo Havlin, Scott Kirkpatrick, Yuval Shavitt, Eran Shir. Proceedings of the National Academy of Sciences of the United States of America, 2006

753 citations recorded by the source corpus.

We study a map of the Internet (at the autonomous systems level), by introducing and using the method of k-shell decomposition and the methods of percolation theory and fractal geometry, to find a model for the structure of the Internet. In particular, our analysis uses information on the connectivity of the network shells to separate, in a unique (no parameters) way, the Internet into three subcomponents: (i) a nucleus that is a small (≈100 nodes), very well connected globally distributed subgraph; (ii) a fractal subcomponent that is able to connect the bulk of the Internet without congesting the nucleus, with self-similar properties and critical exponents predicted from percolation theory; and (iii) dendrite-like structures, usually isolated nodes that are connected to the rest of the network through the nucleus only. We show that our method of decomposition is robust and provides insight into the underlying structure of the Internet and its functional consequences. Our approach of decomposing the network is general and also useful when studying other complex networks.

Subfields: Condensed Matter Physics, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/1d8d8f11c8992147f4663c0b561f0a6976700910

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Condensed Matter Physics

In Statistical and Nonlinear Physics

Citations in the corpus

Critical phenomena in complex networks (2007, background): “Unfortunately, the resulting kh turned out to be several (3) times smaller than the observed values (Alvarez-Hamelin et al., 2005b; Carmi et al., 2007).”
Searching for superspreaders of information in real-world social media (2014, background): “Among these measures, PageRank, betweenness centrality and k-core are global indices since their calculation requires the complete network structure as opposed to the local degree (details in Methods).”
Vital nodes identification in complex networks (2016, background): “[37] argued that the location of a node (whether in the central place) is more important than its degree, and they applied the k-core decomposition [38, 39] that iteratively decomposes the network according to the residual degree of the nodes.”
Identifying influential spreaders in complex networks (2010, neutral): “Data have been gathered from the DIMES project [13].”
Analyzing and modeling real-world phenomena with complex networks: a survey of applications (2007, background): “Such a tendency to have a strong c re in the Internet was reported in [220, 221], where the nucleus of the Internet, i.”
Local search of communities in large graphs (2014, background): “k-core decomposition is empirically investigated on many real large networks and shown to be a new perspective to characterize the structure and function of real networks [27].”