A model of Internet topology using k-shell decomposition

Abstract

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 ( approximately 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.

Fig. 1.

For each k-crust, we plot the size of the crust (i.e., total number of nodes that belong to the crust), the size of the largest and second-largest connected components of the crusts (the second is magnified ×10 to make it visible), and the average distance between nodes in the largest cluster of each crust.

Fig. 2.

Visualization of our data of the Internet at the AS level. (Upper) A plot of all nodes, ordered by their k-shell indices, using the program of ref. . The legend to the left denotes degree, and the legend to the right denotes k-shell index. (Lower) A schematic plot of the suggested Medusa model decomposition of the AS level Internet into three components.

Fig. 3.

The nucleus in random networks and the k-shell distribution. (a) The size of the nucleus and its k-shell index, as a function of N in random scale-free networks. The random network model used is the configuration model (with γ = 2.35 as was measured in our data). Each data point is an average over at least 1,000 realizations. The values for the Internet are also indicated (stars). The probabilities to observe deviations at least as large as those of the Internet are <10⁻¹ and <10⁻¹⁰ for the nucleus size and the k-shell index, respectively. (b) The contribution of each shell to the peer-connected component. The straight line is drawn for illustration.

Fig. 4.

Properties of the peer-connected component. (a) For few selected crusts, we plot the number of boxes needed to cover the largest cluster of the crust as a function of the box sizes l. On a log–log scale, the slope of this curve is the fractal dimension of the network (5). (b) The probability distribution of the sizes of the finite clusters of the 6-crust. Percolation theory predicts p_s ∼ s^−5/2 (20). The plot shows the probability distribution after logarithmic binning and a straight line with slope (−3/2). Using the MLE method (24) (excluding the first data point), the exponent best describing the data came out as 2.46 (Kolmogorov–Smirnov statistic equals 0.018).