Reducing Degeneracy in Maximum Entropy Models of Networks

Abstract

Based on Jaynes' maximum entropy principle, exponential random graphs provide a family of principled models that allow the prediction of network properties as constrained by empirical data (observables). However, their use is often hindered by the degeneracy problem characterized by spontaneous symmetry-breaking, where predictions fail. Here we show that degeneracy appears when the corresponding density of states function is not log-concave, which is typically the consequence of nonlinear relationships between the constraining observables. Exploiting these nonlinear relationships here we propose a solution to the degeneracy problem for a large class of systems via transformations that render the density of states function log-concave. The effectiveness of the method is illustrated on examples.

5 pages, 4 figures, 4 animated figures as supplemental material

References in corpus (5)

• Cooperative Game Theory Approaches for Network Partitioning
• Community Structure in Jazz
• Efficient and exact sampling of simple graphs with given arbitrary degree sequence
• Prediction of spatio-temporal patterns of neural activity from pairwise correlations
• Solution for the properties of a clustered network

Cited by in corpus (18)

• The Statistical Physics of Real-World Networks
• Quantifying randomness in real networks
• A Bayesian machine scientist to aid in the solution of challenging scientific problems
• Clustering implies geometry in networks
• Exponential Random Simplicial Complexes
• Sampling motif-constrained ensembles of networks
• Classical Information Theory of Networks
• Bayesian machine scientist to compare data collapses for the Nikuradse dataset
• Entropy rate of random walks on complex networks under stochastic resetting
• Connectedness matters: Construction and exact random sampling of connected graphs
• Statistical physics of exchangeable sparse simple networks, multiplex networks and simplicial complexes
• Missing links as a source of seemingly variable constants in complex reaction networks
• DERGMs: Degeneracy-restricted exponential random graph models
• Distinguishing Cell Phenotype Using Cell Epigenotype
• Equilibrium distributions in entropy driven balanced processes
• Relaxation dynamics of maximally clustered networks
• Ensemble inequivalence and phase transitions in unlabeled networks
• Maximum Likelihood under constraints: Degeneracies and Random Critical Points