Structure of shells in complex networks

We define shell l in a network as the set of nodes at distance l with respect to a given node and define r(l) as the fraction of nodes outside shell l. In a transport process, information or disease usually diffuses from a random node and reach nodes shell after shell. Thus, understanding the shell structure is crucial for the study of the transport property of networks. We study the statistical properties of the shells of a randomly chosen node. For a randomly connected network with given degree distribution, we derive analytically the degree distribution and average degree of the nodes residing outside shell l as a function of r(l). Further, we find that r(l) follows an iterative functional form r(l)=phi(r(l-1)), where phi is expressed in terms of the generating function of the original degree distribution of the network. Our results can explain the power-law distribution of the number of nodes B-l found in shells with l larger than the network diameter d, which is the average distance between all pairs of nodes. For real-world networks the theoretical prediction of r(l) deviates from the empirical r(l). We introduce a network correlation function c(r(l))equivalent to r(l)/phi(r(l-1)) to characterize the correlations in the network, where r(l) is the empirical value and phi(r(l-1)) is the theoretical prediction. c(r(l))=1 indicates perfect agreement between empirical results and theory. We apply c(r(l)) to several model and real-world networks. We find that the networks fall into two distinct classes: (i) a class of poorly connected networks with c(r(l))>1, where a larger (smaller) fraction of nodes resides outside (inside) distance l from a given node than in randomly connected networks with the same degree distributions. Examples include the Watts-Strogatz model and networks characterizing human collaborations such as citation networks and the actor collaboration network; (ii) a class of well-connected networks with c(r(l))< 1. Examples include the Barabaacutesi-Albert model and the autonomous system Internet network.