Dresden 2011 – wissenschaftliches Programm

Bereiche | Tage | Auswahl | Suche | Aktualisierungen | Downloads | Hilfe

SOE: Fachverband Physik sozio-ökonomischer Systeme

SOE 14: Networks: From Topology to Dynamics II (with BP, DY)

SOE 14.7: Vortrag

Mittwoch, 16. März 2011, 12:30–12:45, GÖR 226

Is there a bias in the generation of simple random graphs with the configuration model? — •Hendrike Klein-Hennig and Alexander K. Hartmann — Institute of Physics, University of Oldenburg

The configuration model is an often used and well known procedure to generate random graphs with an arbitrary degree sequence. The basic idea is to assign a fixed degree to each vertex, which create edges emerging from the vertex called stubs. In a second step random pairs of stubs are connected until there are no stubs left. This procedure generates every possible graph realization with the same probability. In this work two generation procedures are compared how to deal with self-loops and multiple edges (forbidden edges) to generate undirected simple graphs. In the first procedure the entire graph is disregarded and the generation process is restarted from the beginning as soon as a forbidden edge is encountered. Another method, which is frequently applied [1], is to disregard only the forbidden edge, restoring the stubs and drawing a new pair, while keeping the rest of the graph. An analysis of small example graphs shows that for the second generation procedure the graphs are not necessarily created with equal probability. For large graph sizes the behavior is studied using statistical tests on computer generated graphs [2].

[1] M.Catanzaro, M.Boguñá and R. Pastor-Satorras, Generation of uncorrelated random scale-free networks, Phys. Rev. E 71 027103 (2005)

[2] A.K. Hartmann, Practical Guide to Computer Simulations, (World Scientific, 2009)