Structure of shells in complex networks

Abstract

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 }=\varphi (r_{\ell -1})$, where $\varphi$ 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}/\varphi (r_{\ell })$ to characterize the correlations in the network, where $r_{\ell +1}$ is the empirical value and $\varphi (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$.

References in corpus (3)

• Optimal Paths in Disordered Complex Networks
• Ring structures and mean first passage time in networks
• Evolution equation for a model of surface relaxation in complex networks

Cited by in corpus (43)

• Catastrophic cascade of failures in interdependent networks
• Robustness of a Network of Networks
• Discrete-time Markov chain approach to contact-based disease spreading in complex networks
• Robustness of interdependent networks under targeted attack
• Cascade of failures in coupled network systems with multiple support-dependent relations
• Percolation on complex networks: Theory and application
• The critical effect of dependency groups on the function of networks
• A k-shell decomposition method for weighted networks
• Interdependent networks with correlated degrees of mutually dependent nodes
• Robustness of a Tree-like Network of Interdependent Networks
• Percolation in Interdependent and Interconnected Networks: Abrupt Change from Second to First Order Transition
• Percolation of localized attack on complex networks
• Percolation of Partially Interdependent Scale-free Networks
• Percolation in networks composed of connectivity and dependency links
• Epidemic spreading on complex networks with general degree and weight distributions
• Percolation of a general network of networks
• Percolation of partially interdependent networks under targeted attack
• Quantifying loopy network architectures
• The influence of the broadness of the degree distribution on network's robustness: comparing localized attack and random attack
• $k$-core percolation on complex networks: Comparing random, localized and targeted attacks
• Networking - A Statistical Physics Perspective
• Centrality scaling in large networks
• Strategy for stopping failure cascades in interdependent networks
• The combined effect of connectivity and dependency links on percolation of networks
• Mapping from Architecture to Dynamics: A Unified View of Dynamical Processes on Networks
• Distance distribution in configuration model networks
• Age-Stratified COVID-19 Spread Analysis and Vaccination: A Multitype Random Network Approach
• Network Overload due to Massive Attacks
• The distribution of shortest path lengths in subcritical Erdős-Rényi networks
• The distribution of shortest path lengths in a class of node duplication network models
• Distribution of shortest cycle lengths in random networks
• History-dependent percolation on multiplex networks
• Effect of degree correlations above the first shell on the percolation transition
• Analytical results for the distribution of shortest path lengths in directed random networks that grow by node duplication
• The effect of interdependence on the percolation of interdependent networks
• Jamming in complex networks with degree correlation
• Containing rumors spreading on correlated multiplex networks
• The mean and variance of the distribution of shortest path lengths of random regular graphs
• Statistical analysis of edges and bredges in configuration model networks
• Phases of Small Worlds: A Mean Field Formulation
• The distribution of shortest path lengths on trees of a given size in subcritical Erdos-Renyi networks
• Localized attack on clustering networks
• Modelling the Self-similarity in Complex Networks Based on Coulomb's Law