Generating large scale-free networks with the Chung-Lu random graph model

Dario Fasino, Arianna Tonetto, Francesco Tudisco

Abstract

Random graph models are essential tools for studying network structural properties and benchmarking community detection algorithms. They also serve as testbeds for studying diffusion and routing processes. This paper illustrates how to generate large random graphs with a power-law degree distribution using the Chung–Lu model. We focus on the fulfillment of a fundamental hypothesis—admissibility—without which the generated graphs lose their theoretical properties, such as the controllability of expected node degrees and the absence of degree correlations. We provide explicit formulas for model parameters to generate graphs with power-law exponents $\gamma > 2$, prescribed asymptotic behavior for degrees, and a guaranteed giant component.

Introduction

In network science, synthetic "scale-free" graphs—where node degrees follow a power-law distribution—are vital for benchmarking algorithms and simulating processes like epidemic spreading. The Chung–Lu (CL) model is a mathematically elegant choice for this task: each node $i$ is assigned a weight $w_i$, and the probability of an edge existing between nodes $i$ and $j$ is proportional to the product of their weights.

However, the model's theoretical integrity relies on a strict condition known as admissibility. Specifically, the square of the largest weight must not exceed the sum of all weights ($w_{max}^2 \le \sum w_i$). If weights are chosen naively to follow a power law, this condition is frequently violated as the network grows, particularly when the power-law exponent $\gamma$ falls between 2 and 3—the range most characteristic of real-world networks. When admissibility fails, the model loses control over expected degrees and introduces unintended correlations between nodes.

Methodology

The Shifted Weight Sequence

To address the admissibility challenge, the authors refine the weight sequence by introducing a shifting parameter $i_0$. Instead of a standard power law, they employ the distribution:

$$w_i = c(i_0 + i)^{-p}$$

where $p = 1/(\gamma - 1)$. The core contribution of this work is the derivation of explicit formulas for the constant $c$ and the shift $i_0$. These parameters are tuned to satisfy three primary objectives:

  1. Admissibility: Ensuring the $w_{max}^2$ constraint is strictly met.
  2. Target Exponent: Achieving a specific power-law exponent $\gamma > 2$.
  3. Structural Control: Prescribing the average degree and the size of the largest hub node.

The shift parameter $i_0$ effectively acts as a "safety valve," flattening the top of the degree distribution just enough to maintain admissibility without compromising the overall power-law behavior.

Efficient Generation: The Ball-Dropping Algorithm

Generating massive graphs requires computational efficiency. A naive approach checking every possible pair of nodes results in $O(n^2)$ complexity, which is prohibitive for large $n$. The authors utilize an efficient "ball-dropping" algorithm. By generating edge endpoints based on the weight distribution, the algorithm achieves a complexity of $O(m \log m)$, where $m$ is the number of edges. This allows for the generation of networks with millions of nodes in seconds on standard hardware.

Experimental Evaluation

The approach was evaluated using synthetic benchmarks with up to $10^6$ nodes and $10^7$ edges. Through extensive parameter sweeps across various exponents ($\gamma = 2.3, 2.6, 2.9$), the authors verified that the empirical results closely match theoretical predictions.

Key findings include:

  • Linear Scalability: Execution time scales linearly with the number of edges.
  • Theoretical Fidelity: Empirical degree profiles follow the predicted power-law curves, especially for degrees larger than the minimum expected degree.
  • Giant Component Verification: For an average degree $d > 1$, the model consistently produces a unique giant component containing a significant fraction of the network's volume, aligning with the theoretical expectations of the model.

Discussion and Insights

The $\gamma = 3$ Boundary

The research highlights that admissibility is naturally easier to satisfy when $\gamma \ge 3$. The "danger zone" is $2 < \gamma < 3$, where hubs grow so large they threaten the model's probabilistic assumptions. The proposed shifting method is particularly crucial for researchers working within this common real-world range.

CL as a Null Model

Unlike the Barabási–Albert (preferential attachment) model, the CL model does not inherently produce degree correlations (e.g., assortativity). This makes it a superior "null model" for testing whether specific features in a real-world network—such as community structure or high clustering—are significant or merely artifacts of the degree distribution.

Limitations and Future Work

While the shifted CL model provides a robust framework for scale-free generation, it has limitations:

  • Clustering: The standard CL model produces graphs with low clustering (few triangles), whereas real-world social networks often exhibit high clustering.
  • Directionality: The current work is limited to undirected graphs. Extending admissibility proofs to directed scale-free graphs remains an open challenge.
  • Dynamics: The model is static and does not capture the temporal evolution of networks.

In conclusion, this paper provides a rigorous "recipe" for generating massive, theoretically sound scale-free networks, ensuring that the resulting graphs maintain the mathematical properties required for valid scientific inquiry.

Summary updated

Abstract

Random graph models are a recurring tool-of-the-trade for studying network structural properties and benchmarking community detection and other network algorithms. Moreover, they serve as test-bed generators for studying diffusion and routing processes on networks. In this paper, we illustrate how to generate large random graphs having a power-law degree distribution using the Chung--Lu model. In particular, we are concerned with the fulfilment of a fundamental hypothesis that must be placed on the model parameters, without which the generated graphs lose all the theoretical properties of the model, notably, the controllability of the expected node degrees and the absence of correlations between the degrees of two nodes joined by an edge. We provide explicit formulas for the model parameters to generate random graphs that have several desirable properties, including a power-law degree distribution with any exponent larger than $2$, a prescribed asymptotic behaviour of the largest and average expected degrees, and the presence of a giant component.
BibTeX
@article{fasino2019generating,
  author = {Dario Fasino and Arianna Tonetto and Francesco Tudisco},
  title = {{Generating large scale-free networks with the Chung-Lu random graph model}},
  journal = {Networks},
  year = {2019},
  doi = {10.1002/net.22012},
}
Figure