# Dresden 2006 – wissenschaftliches Programm

## Bereiche | Tage | Auswahl | Suche | Downloads | Hilfe

# DY: Dynamik und Statistische Physik

## DY 12: Statistical Physics of Complex Networks II

### DY 12.3: Vortrag

### Montag, 27. März 2006, 11:30–11:45, H\"UL 186

**Monte Carlo sampling of cycles in large networks** — •Konstantin Klemm and Peter F. Stadler — Dept. of Bioinformatics, Leipzig University

An important characteristic of many complex networks is redundant wiring, which leads to the occurrence of cycles. Abundance of small cycles, in particular triangles, has been widely studied. Larger cycles with lengths up to system size have received much less attention due to the lack of efficient numerical tools. Here we present a Markov chain Monte Carlo algorithm that is able to sample cycles of all lengths with equal probability. By choosing length dependent (Boltzmann) weights the equilibrium distribution can be tuned to particularly long or short cycles.

As the main result for growing networks, we find that the dependence between
network size *N* and typical cycle length is algebraic [1], ⟨ *h* ⟩
∝ *N*^{α}, with distinct values of α for different wiring rules.
The Barabasi-Albert model has α=1. Other preferential and
non-preferential attachment rules and the growing Internet graph yield
α<1.

[1] K. Klemm and P. F. Stadler, e-print cond-mat/0506493.