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:
- Admissibility: Ensuring the $w_{max}^2$ constraint is strictly met.
- Target Exponent: Achieving a specific power-law exponent $\gamma > 2$.
- 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