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

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 (HSCM), 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.

References in corpus (5)

• Hyperbolic Geometry of Complex Networks
• The entropy of network ensembles
• The entropy of randomized network ensembles
• Maximum likelihood: extracting unbiased information from complex networks
• Clustering implies geometry in networks

Cited by in corpus (15)

• Network Geometry
• Link prediction with hyperbolic geometry
• Small worlds and clustering in spatial networks
• Meta-validation of bipartite network projections
• A geometry-induced topological phase transition in random graphs
• Random hyperbolic graphs in $d+1$ dimensions
• Weighted hypersoft configuration model
• Random Simplicial Complexes: Models and Phenomena
• Dynamic Hidden-Variable Network Models
• Multiscale network renormalization: scale-invariance without geometry
• Propinquity drives the emergence of network structure and density
• Entropy of labeled versus unlabeled networks
• On the External Validity of Average-Case Analyses of Graph Algorithms
• Random graphs and real networks with weak geometric coupling
• Sparse power-law network model for reliable statistical predictions based on sampled data