Tomography of scale-free networks and shortest path trees

In this paper we model the tomography of scale-free networks by studying the structure of layers around an arbitrary network node. We find, both analytically and empirically, that the distance distribution of all nodes from a specific network node consists of two regimes. The first is characterized by rapid growth, and the second decays exponentially. We also show analytically that the nodes degree distribution at each layer exhibits a power-law tail with an exponential cutoff. We obtain similar empirical results for the layers surrounding the root of shortest path trees cut from such networks, as well as the Internet.

Figure 1

Illustration of the exposure process. The large circles denote exposed layers of the giant component, while the small circles denote individual sites. The sites outside the circles have not been reached yet. (a) We begin with the highest degree node and fill out layer No. 1. (b) In the exposure of layer No. $l+1$ any open connection emerging from layer No. $l$ may connect to any open node ($T_l$ connections) or loop back into layer No. $l$ (${\chi }_l$ connections). (c) The number of connections emerging from layer No. $l+1$ is the difference between $T_l$ and $T_{l+1}$ after reducing the incoming connections $S_{l+1}$ from layer No. $l$.

Figure 2

(Color online) Approximate number of nodes $\left(S_l\right)$ vs layer index $l$ for a network with $N={10}^6$ nodes, $\lambda =2.85$, and $m=1$. Filled symbols represent simulation results while black lines are a numerical solution for the derived recursive relations. Empty symbols represent the gamma function with $\alpha =10.576$ and $\beta =2.225$. Bottom: from the semilog plot we see that there is an exponential decay of $S_l$ for layers $l>L$ starting from a given layer $L$ which we believe is related to the radius of the graph.

Figure 3

(Color online) Log-log plot of $P_l\left(k\right)$ for different layers $l=0,1,2,\dots$, for a network with $N={10}^6$ nodes, $\lambda =2.85$, and $m=1$. Symbols represent simulation results while black lines are a numerical solution for the derived recursive relations.

Figure 4

(Color online) Number of nodes at each layer for a router level cut of the Internet with $N=112969$ nodes (LC topology). Analytical reconstruction for $S_l$ is done with $\lambda =3$ and $m=1$. The fit to the gamma function was done with parameters $\alpha =9.99$ and $\beta =1.701$.

Figure 5

(Color online) Log-log plot of $P_l\left(k\right)$ for different layers $l=0,1,2,\dots$, for a router level cut of the Internet with $N=112969$ nodes (LC topology). Qualitative analytical reconstruction is done with $\lambda =3$, and $m=1$.

Figure 6

(Color online) Tomography of a 100 000 client multicast tree cut from a CM topology of ${10}^6$ nodes, with $m=1$ and $\lambda =2.5$. The root was chosen with a high degree, and the clients were chosen randomly. Top: Number of nodes at each layer (filled symbols). Empty symbols represent a gamma distribution function with $\alpha =10.302$ and $\beta =3.424$. Middle: Log-log plot of the degree distributions $P_l\left(k\right)$ for different layers $l=0,1,2,\dots$ . Bottom: A semilog plot of the same distributions. The degree distributions exhibit a power-law tail $({\lambda }_{\text{tree}}\approx 2.5)$ with an exponential cutoff which is becoming stronger at each layer.

Figure 7

(Color online) Tomography of a 100 000 client multicast tree cut from a BA topology of ${10}^6$ nodes with $m_0=6$, $m=1.5$, $p=0.1$, and $q=0$. The root was chosen with a high degree, and the clients were chosen randomly. Top: Number of nodes at each layer (filled symbols). Empty symbols represent a gamma distribution function with $\alpha =18.215$ and $\beta =3.896$. Middle: Log-log plot of the degree distributions $P_l\left(k\right)$ for different layers $l=0,1,2,\dots$ . Bottom: A semilog plot of the same distributions. The degree distributions exhibit a power-law tail $({\lambda }_{\text{tree}}\approx 3.2)$ with an exponential cutoff which is becoming stronger at each layer.

Figure 8

(Color online) Top: Number of degree two nodes $(k=2)$ at each layer of a multicast tree cut from CM topology with $\lambda =2.5$ and ${10}^6$ nodes. Empty symbols represent a fit to the gamma distribution with $\alpha =11.173$ and $\beta =3.984$. Bottom: Number of high-degree nodes $(k⩾8)$ at each layer of a multicast tree cut from the same underlying topology. Empty symbols represent the corresponding gamma distribution with $\alpha =12.25$ and $\beta =7.36$. It can be seen that the high-degree nodes tend to reside much closer to the root than the low-degree nodes.

Figure 9

(Color online) Top: Number of degree two nodes $(k=2)$ at each layer of a multicast tree cut from BA topology with $m_0=6,m=1.5,p=0.1,q=0$, and ${10}^6$ nodes. Empty symbols represent a fit to the gamma distribution with $\alpha =23.846$ and $\beta =5.397$. Bottom: Number of high-degree nodes $(k⩾7)$ at each layer of a multicast tree cut from the same underlying topology. Empty symbols represent the corresponding gamma distribution with $\alpha =16.862$ and $\beta =5.959$. It can be seen that the high-degree nodes tend to reside much closer to the root than the low-degree nodes.

Figure 10

(Color online) Tomography of Internet tree with 12 810 nodes and 5072 clients. Top: Log-log plot of the degree distributions $P_l\left(k\right)$ for different layers $l=0,5,10,13$. Bottom: A semilog plot of the same distributions. There is strong indication that the degree distributions exhibit a power-law tail (${\lambda }_{\text{tree}}\approx 3.18$ [10]) with an exponential cutoff which is becoming stronger at each layer.