Structure of shells in complex networks

J. SHAO; S. V. BULDYREV; L. A. BRAUNSTEIN; S. HAVLIN; H. E. STANLEY

PHYSICAL REVIEW E - STATISTICAL PHYSICS, PLASMAS, FLUIDS AND RELATED INTERDISCIPLINARY TOPICS

Año: 2009

1063-651X

In a network, we define shell $ell$ as the set of nodes atdistance $ell$ with respect to a given node anddefine $r_ell$ as the fraction of nodes outside shell $ell$.In a transport process, information or disease usually diffuses from a randomnode and reach nodes shell after shell.Thus, understanding the shell structure is crucial for the study ofthe transport property of networks.We study the statistical properties of the shells from a randomly chosen node.For a randomly connected network with given degree distribution, we derive analytically thedegree 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 theoriginal degree distribution of the network.Our results can explain the power-law distributionof the number of nodes $B_ell$ found in shells with $ell$ larger than thenetwork 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 theempirical value and $phi(r_ell)$ is the theoretical prediction.$c(r_ell)=1$ indicates perfect agreement between empirical results andtheory.We apply $c(r_ell)$ to several model and real world networks. We findthat the networks fall into two distinct classes: (i) a class of{it poorly-connected} networks with $c(r_ell)>1$, {f where larger (smaller)fraction of nodes residing outside (inside) distance $ell$ from a given nodesthan randomly connected networks with the same degree distributions};%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$. Examples of poorly-connected networks includethe Watts-Strogatz model and networkscharacterizing human collaborations, whichinclude two citation networks and the actor collaboration network.Examples of well-connected networks include the Barab´{a}si-Albertmodel and the Autonomous System (AS) Internet network.