IFIMAR   20926
INSTITUTO DE INVESTIGACIONES FISICAS DE MAR DEL PLATA
artículos
Título:
Structure of shells in complex networks
Autor/es:
J. SHAO; S. V. BULDYREV; L. A. BRAUNSTEIN; S. HAVLIN; H. E. STANLEY
Revista:
PHYSICAL REVIEW E - STATISTICAL PHYSICS, PLASMAS, FLUIDS AND RELATED INTERDISCIPLINARY TOPICS
Referencias:
Año: 2009
ISSN:
1063-651X
Resumen:
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.
rds']