Statistics of cycles in large networks

Abstract

We present a Markov Chain Monte Carlo method for sampling cycle length in large graphs. Cycles are treated as microstates of a system with many degrees of freedom. Cycle length corresponds to energy such that the length histogram is obtained as the density of states from Metropolis sampling. In many growing networks, mean cycle length increases algebraically with system size. The cycle exponent $\alpha$ is characteristic of the local growth rules and not determined by the degree exponent $\gamma$. For example, $\alpha =0.76(4)$ for the Internet at the Autonomous Systems level.

4 pages, 4 figures

References in corpus (6)

• Self-similarity of complex networks
• Delays, connection topology, and synchronization of coupled chaotic maps
• Kinetic Theory of Random Graphs: from Paths to Cycles
• Loops structure of the Internet at the Autonomous System Level
• Diffusion Processes on Power-Law Small-World Networks
• The inhomogeneous evolution of subgraphs and cycles in complex networks

Cited by in corpus (11)

• New approaches to model and study social networks
• On the number of circuits in random graphs
• Distribution of shortest cycle lengths in random networks
• Finding long cycles in graphs
• Graph animals, subgraph sampling and motif search in large networks
• Stochastic and mixed flower graphs
• Optimal Scale-Free Small-World Graphs with Minimum Scaling of Cover Time
• Coherence Scaling of Noisy Second-Order Scale-Free Consensus Networks
• Unevenness of Loop Location in Complex Networks
• Edge corona product as an approach to modeling complex simplical networks
• Scale-free Loopy Structure is Resistant to Noise in Consensus Dynamics in Complex Networks