Preprint: Statistics of cycles in large networks

Bioinformatics Preprint 05-020

Titel:
Statistics of cycles in large networks

Author(s):
Konstantin Klemm, Peter F. Stadler

Submitted

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.

Keywords: Cycle basis, Metropolis sampling, network statistics, internet

Return to 2005 working papers list.
Last modified: 2004-03-28 19:56:33 studla