Dresden 2006 – scientific programme

Parts | Days | Selection | Search | Downloads | Help

DY: Dynamik und Statistische Physik

DY 12: Statistical Physics of Complex Networks II

DY 12.3: Talk

Monday, March 27, 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.