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

Abstract

Being able to produce synthetic networks by means of generative random graph models and scalable algorithms is a recurring tool-of-the-trade in network analysis, as it provides a well founded basis for the statistical analysis of various properties in real-world networks. In this paper, we illustrate how to generate large random graphs having a power-law degree profile by means of the Chung-Lu model. In particular, we are concerned with the fulfillment of a fundamental hypothesis that must be placed on the model parameters, without which the generated graphs loose 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 in order to generate random graphs which fulfill a number of requirements on the behavior of the smallest, largest, and average expected degrees and have several desirable properties, including a power-law degree distribution with any prescribed exponent larger than 2, the presence of a giant component and no potentially isolated nodes.

Please cite this paper as:

@article{fasino2019generating,
  title={Generating large scale-free networks with the {C}hung-{L}u random graph model},
  author={Fasino, Dario and Tonetto, Arianna and Tudisco, Francesco},
  journal={Networks},
  year={2020}
}

Keywords: Scale-free networks random graphs Chung–Lu model networks