Sparse Maximum-Entropy Random Graphs with a Given Power-Law Degree Distribution

Pim van der Hoorn, Gabor Lippner, Dmitri Krioukov
Journal of Statistical Physics
173: 806
October 6, 2017

Abstract

Even though  power-law or close-to-power-law degree distributions are ubiquitously  observed in a great variety of large real networks, the mathematically  satisfactory treatment of random power-law graphs satisfying basic  statistical requirements of realism is still lacking. These requirements are:  sparsity, exchangeability, projectivity, and unbiasedness. The last  requirement states that entropy of the graph ensemble must be maximized under  the degree distribution constraints. Here we prove that the hypersoft  configuration model, belonging to the class of random graphs with latent  hyperparameters, also known as inhomogeneous random graphs or W-random  graphs, is an ensemble of random power-law graphs that are sparse, unbiased,  and either exchangeable or projective. The proof of their unbiasedness relies  on generalized graphons, and on mapping the problem of maximization of the  normalized Gibbs entropy of a random graph ensemble, to the graphon entropy  maximization problem, showing that the two entropies converge to each other  in the large-graph limit.

Related publications