Structure of shells in complex networks

In a network, we define shell $ell$ as the set of nodes at distance $ell$ with respect to a given node and define $r_ell$ as the fraction of nodes outside shell $ell$. 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. For a randomly connected network with given degree distribution, we derive analytically the degree distribution and average degree of the nodes residing outside shell $ell$ as a function of $r_ell$. Further, we find that $r_ell$ follows an iterative functional form $r_ell=phi(r_{ell-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_ell$ found in shells with $ell$ 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_ell$ deviates from the empirical $r_ell$. We introduce a network correlation function $c(r_ell)equiv r_{ell+1}/phi(r_ell)$ to characterize the correlations in the network, where $r_{ell+1}$ is the empirical value and $phi(r_ell)$ is the theoretical prediction. $c(r_ell)=1$ indicates perfect agreement between empirical results and theory. We apply $c(r_ell)$ to several model and real world networks. We find that the networks fall into two distinct classes: (i) a class of {it poorly-connected} networks with $c(r_ell)>1$, which have larger average distances compared with randomly connected networks with the same degree distributions; and (ii) a class of {it well-connected} networks with $c(r_ell)<1$.