Percolation and Loop Statistics in Complex Networks

Abstract

Complex networks display various types of percolation transitions. We show that the degree distribution and the degree-degree correlation alone are not sufficient to describe diverse percolation critical phenomena. This suggests that a genuine structural correlation is an essential ingredient in characterizing networks. As a signature of the correlation we investigate a scaling behavior in $M_N(h)$, the number of finite loops of size $h$, with respect to a network size $N$. We find that networks, whose degree distributions are not too broad, fall into two classes exhibiting $M_N(h)\sim (constant)$ and $M_N(h)\sim (\ln N{)}^{\psi }$, respectively. This classification coincides with the one according to the percolation critical phenomena.

4 pages and 2 figures; A major revision has been made

References in corpus (30)

• Statistical mechanics of complex networks
• Assortative mixing in networks
• Mixing patterns in networks
• Network robustness and fragility: Percolation on random graphs
• Resilience of the Internet to random breakdowns
• Dynamical and correlation properties of the Internet
• Immunization of complex networks
• Universal Behavior of Load Distribution in Scale-free Networks
• Large-scale topological and dynamical properties of Internet
• Epidemic spreading in correlated complex networks
• Class of correlated random networks with hidden variables
• Are randomly grown graphs really random?
• The topological relationship between the large-scale attributes and local interaction patterns of complex networks
• Cut-offs and finite size effects in scale-free networks
• Resilience to damage of graphs with degree correlations
• Infinite-Order Percolation and Giant Fluctuations in a Protein Interaction Network
• Anomalous percolating properties of growing networks
• Diffusion-annihilation processes in complex networks
• Clustering of correlated networks
• Number of loops of size h in growing scale-free networks
• Loops of any size and Hamilton cycles in random scale-free networks
• Uncorrelated Random Networks
• Evolution of scale-free random graphs: Potts model formulation
• Optimal design, robustness, and risk aversion
• Loops structure of the Internet at the Autonomous System Level
• Statistics of Cycles: How Loopy is your Network?
• Intrinsic degree-correlations in static model of scale-free networks
• Universal Properties of Growing Networks
• Circuits in random graphs: from local trees to global loops
• Finding long cycles in graphs

Cited by in corpus (6)

• Networking - A Statistical Physics Perspective
• Distribution of shortest cycle lengths in random networks
• The characteristics of cycle-nodes-ratio and its application to network classification
• Effect of degree correlations above the first shell on the percolation transition
• Percolation transition and distribution of connected components in generalized random network ensembles
• Unevenness of Loop Location in Complex Networks