Statistics of Cycles: How Loopy is your Network?

Abstract

We study the distribution of cycles of length h in large networks (of size N>>1) and find it to be an excellent ergodic estimator, even in the extreme inhomogeneous case of scale-free networks. The distribution is sharply peaked around a characteristic cycle length, h* ~ N^a. Our results suggest that h* and the exponent a might usefully characterize broad families of networks. In addition to an exact counting of cycles in hierarchical nets, we present a Monte-Carlo sampling algorithm for approximately locating h* and reliably determining a. Our empirical results indicate that for small random scale-free nets of degree exponent g, a=1/(g-1), and a grows as the nets become larger.

Further work presented and conclusions revised, following referee reports

Cited by in corpus (25)

• Characterization of complex networks: A survey of measurements
• Mathematical Formulation of Multi-Layer Networks
• Random Walks on Multiplex Networks
• Cycles and clustering in bipartite networks
• Local structure of directed networks
• Random walk centrality in interconnected multilayer networks
• High Dimensional Apollonian Networks
• A general geometric growth model for pseudofractal scale-free web
• On the number of circuits in random graphs
• Degree-dependent intervertex separation in complex networks
• Algorithm for counting large directed loops
• Criticality on networks with topology-dependent interactions
• An algorithm for counting circuits: application to real-world and random graphs
• Statistics of cycles in large networks
• Finding long cycles in graphs
• Percolation and Loop Statistics in Complex Networks
• Stochastic and mixed flower graphs
• Random graph model with power-law distributed triangle subgraphs
• Coherence Scaling of Noisy Second-Order Scale-Free Consensus Networks
• Optimal Scale-Free Small-World Graphs with Minimum Scaling of Cover Time
• Unevenness of Loop Location in Complex Networks
• Vertex routing models
• Spanning Trees of Recursive Scale-Free Graphs
• Growing Networks with Super-Joiners
• Learning heterogenous reaction rates from stochastic simulations