Bias in generation of random graphs.

Area of Science:

• Graph theory
• Statistical modeling
• Network science

Background:

• The configuration model is widely used for generating random graphs, particularly those with scale-free degree distributions.
• Scale-free networks are characterized by a power-law degree distribution, often denoted as ~d(-γ).
• Efficient generation algorithms are crucial for studying large-scale networks.

Purpose of the Study:

• To investigate the statistical properties of random graph generation using the configuration model.
• To identify and quantify biases introduced by efficient graph generation variants.
• To assess the impact of these biases on the properties of generated scale-free graphs.

Main Methods:

• Analysis of the configuration model for random graph generation.
• Explicit calculation of bias in an efficient generation variant using a small sample ensemble.
• Examination of bias persistence with increasing system size.
• Measurement of graph properties, such as diameter, for scale-free graphs.

Main Results:

• An efficient variant of the configuration model introduces a calculable bias.
• This bias does not diminish as the system size increases.
• The persistent bias affects measurable properties like graph diameter in scale-free networks.

Conclusions:

• The efficient generation of general scale-free graphs, especially those with very broad distributions (γ < 2), remains a significant challenge due to persistent biases.
• Further research is needed to develop unbiased methods for generating such networks.
• Understanding and mitigating these biases is critical for accurate network modeling and analysis.