Bias in generation of random graphs

Abstract

We study the statistical properties of the generation of random graphs according the configuration model, where one assigns randomly degrees to nodes. This model is often used, e.g., for the scale-free degree distribution ~d^gamma. For the efficient variant, where non-feasible 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 also visible, e.g., for scale-free graphs when measuring quantities like the graph diameter. Hence, the efficient generation of general scale-free graphs with a very broad distribution (gamma <2) remains an open problem.

8 pages, 5 figures

References in corpus (3)

• Generating simple random graphs with prescribed degree distribution
• Efficient and exact sampling of simple graphs with given arbitrary degree sequence
• All scale-free networks are sparse

Cited by in corpus (11)

• Inducing Effect on the Percolation Transition in Complex Networks
• Large-deviation properties of the largest biconnected component for random graphs
• Clustering of random scale-free networks
• Exact sampling of graphs with prescribed degree correlations
• The distribution of shortest path lengths in subcritical Erdős-Rényi networks
• Boolean decision problems with competing interactions on scale-free networks: Critical thermodynamics
• Large deviation and anomalous fluctuations scaling in degree assortativity on configuration networks
• Phase transition in the bipartite z-matching
• Unbiased degree-preserving randomisation of directed binary networks
• Constructing transient amplifiers for death-Birth updating: A case study of cubic and quartic regular graphs
• Controlled Markovian dynamics of graphs: unbiased generation of random graphs with prescribed topological properties