Bioinformatics Preprint 05-020

**Download:**

[PostScript]
[PDF]

**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