Sparse maximum-entropy random graphs with a given power-law degree distribution

DOI10.1007/S10955-017-1887-7zbMATH Open1402.05194arXiv1705.10261OpenAlexW3101134365MaRDI QIDQ1756545FDOQ1756545

Authors: Gabor Lippner, Dmitri Krioukov, Pim Van der Hoorn 

Publication date: 21 December 2018

Published in: Journal of Statistical Physics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1705.10261

Recommendations

• An \(L^p\) theory of sparse graph convergence. I: Limits, sparse random graph models, and power law distributions
• An algorithm generating random graphs with power law degree distributions
• Uniform generation of random graphs with power-law degree sequences
• Conditional configuration graphs with discrete power-law distribution of vertex degrees
• Random graphs with a given degree sequence

zbMATH Keywords

sparse random graphsmaximum-entropy graphspower-law degree distributions

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Density (toughness, etc.) (05C42) Entropy in general topology (54C70)

Cites Work

• Limits of dense graph sequences
• Large networks and graph limits
• A Mathematical Theory of Communication
• Complex networks: structure and dynamics
• Title not available (Why is that?)
• Title not available (Why is that?)
• An Exponential Family of Probability Distributions for Directed Graphs
• Random Graphs
• Latent Space Approaches to Social Network Analysis
• A critical point for random graphs with a given degree sequence
• The phase transition in inhomogeneous random graphs
• Networks. An introduction.
• Representations for partially exchangeable arrays of random variables
• Graph limits and exchangeable random graphs
• Estimating and understanding exponential random graph models
• Information Theory and Statistical Mechanics
• Consistency under sampling of exponential random graph models
• Title not available (Why is that?)
• Random graphs with a given degree sequence
• Connected components in random graphs with given expected degree sequences
• The average distances in random graphs with given expected degrees
• Title not available (Why is that?)
• Title not available (Why is that?)
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Axiomatic derivation of the principle of maximum entropy and the principle of minimum cross-entropy
• The asymptotic number of labeled graphs with given degree sequences
• Title not available (Why is that?)
• Hyperbolic graph generator
• Singularities in the entropy of asymptotically large simple graphs
• The large deviation principle for the Erdős-Rényi random graph
• Graphons, cut norm and distance, couplings and rearrangements
• Title not available (Why is that?)
• The number of graphs and a random graph with a given degree sequence
• Network science. With Márton Pósfai
• Graph properties, graph limits, and entropy
• Sparse graphs using exchangeable random measures
• Sparse exchangeable graphs and their limits via graphon processes
• Analytical maximum-likelihood method to detect patterns in real networks
• Hamiltonian dynamics of preferential attachment
• Title not available (Why is that?)

Cited In (3)

• Random Simplicial Complexes: Models and Phenomena
• Asymptotic behavior of common connections in sparse random networks
• Limit theorems for assortativity and clustering in null models for scale-free networks

Uses Software

• Hyperbolic graph generator

This page was built for publication: Sparse maximum-entropy random graphs with a given power-law degree distribution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1756545)