title: Bias in generation of random graphs.
abstract: We study the statistical properties of the generation of random graphs according to the configuration model, in which one assigns randomly degrees to nodes. This model is often used, for example, for the scale-free degree distribution ~d(-γ). For the efficient variant, where nonfeasible edges are rejected and the construction of a graph continues, there exists a bias, which we calculate explicitly for a small sample ensemble. We find that this bias does not disappear with growing system size. This becomes visible, for example, also for scale-free graphs when measuring quantities such as the graph diameter. Hence the efficient generation of general scale-free graphs with a very broad distribution (γ < 2) remains an open problem.
authors.affiliation: Institute of Physics, University of Oldenburg, D-26111 Oldenburg, Germany.
authors.forename: Hendrike
authors.initials: H
authors.lastname: Klein-Hennig
authors.forename: Alexander K
authors.initials: AK
authors.lastname: Hartmann
mesh_terms: D003196:Computer Graphics; D008962:Models, Theoretical; D013269:Stochastic Processes