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 rl 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 rl. Further, we find that rl follows an iterative functional form rl=phi(rl-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 Bl 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 rl deviates from the empirical rl. We introduce a network correlation function c(rl) identical with rl/phi(rl-1) to characterize the correlations in the network, where rl is the empirical value and phi(rl-1) is the theoretical prediction. c(rl)=1 indicates perfect agreement between empirical results and theory. We apply c(rl) 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(rl)>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(rl)