Entropies of complex networks with hierarchically constrained topologies

Abstract

The entropy of a hierarchical network topology in an ensemble of sparse random networks with "hidden variables" associated to its nodes, is the log-likelihood that a given network topology is present in the chosen ensemble.We obtain a general formula for this entropy,which has a clear simple interpretation in some simple limiting cases. The results provide new keys with which to solve the general problem of "fitting" a given network with an appropriate ensemble of random networks.

(18 pages)

References in corpus (27)

• Statistical mechanics of complex networks
• Mixture models and exploratory analysis in networks
• Class of correlated random networks with hidden variables
• Phase Transitions in the Coloring of Random Graphs
• Ferromagnetic ordering in graphs with arbitrary degree distribution
• A General Formalism for Inhomogeneous Random Graphs
• The entropy of randomized network ensembles
• The number of guards needed by a museum: A phase transition in vertex covering of random graphs
• Statistical mechanics of the random K-SAT model
• Coloring random graphs
• Solution of the 2-star model of a network
• Optimisation problems and replica symmetry breaking in finite connectivity spin-glasses
• Kullback-Leibler distance as a measure of the information filtered from multivariate data
• Tricritical Points in Random Combinatorics: the (2+p)-SAT case
• Finite Connectivity Attractor Neural Networks
• Replicated Transfer Matrix Analysis of Ising Spin Models on `Small World' Lattices
• On large deviation properties of Erdos-Renyi random graphs
• Finitely connected vector spin systems with random matrix interactions
• Sparsely-spread CDMA - a statistical mechanics based analysis
• Analytic solution of attractor neural networks on scale-free graphs
• Cavity approach for real variables on diluted graphs and application to synchronization in small-world lattices
• The Little-Hopfield model on a Random Graph
• Dynamical replica analysis of disordered Ising spin systems on finitely connected random graphs
• Diagonalization of replicated transfer matrices for disordered Ising spin systems
• Statistical Mechanics Analysis of LDPC Coding in MIMO Gaussian Channels
• Properties of atypical graphs from negative complexities
• Statics and dynamics of the Lebwohl-Lasher model in the Bethe approximation

Cited by in corpus (35)

• Community detection in graphs
• The Statistical Physics of Real-World Networks
• Entropy measures for complex networks: Toward an information theory of complex topologies
• Statistical Mechanics of Multiplex Ensembles: Entropy and Overlap
• The entropy of network ensembles
• Generalized network structures: The configuration model and the canonical ensemble of simplicial complexes
• Efficient and exact sampling of simple graphs with given arbitrary degree sequence
• The Shannon and the Von Neumann entropy of random networks with heterogeneous expected degree
• Emergence of overlap in ensembles of spatial multiplexes and statistical mechanics of spatial interacting networks ensembles
• Gibbs entropy of networks ensembles by cavity methods
• Unbiased sampling of network ensembles
• Entropy of dynamical social networks
• Annealed and Mean-Field formulations of Disease Dynamics on Static and Adaptive Networks
• Constrained Markovian dynamics of random graphs
• Multiplex networks with heterogeneous activities of the nodes
• Constructing and sampling directed graphs with given degree sequences
• Tailored graph ensembles as proxies or null models for real networks I: tools for quantifying structure
• Entropy distribution and condensation in random networks with a given degree distribution
• Correlations between weights and overlap in ensembles of weighted multiplex networks
• On Minimum Violations Ranking in Paired Comparisons
• Spectral density of random graphs with topological constraints
• Ensemble nonequivalence in random graphs with modular structure
• Statistical Mechanics of Multi-Edge Networks
• Entropy rate of non-equilibrium growing networks
• Network resilience against intelligent attacks constrained by degree dependent node removal cost
• Tailored graph ensembles as proxies or null models for real networks II: results on directed graphs
• The role of adjacency matrix degeneration in maximum entropy weighted network models
• A geometric entropy detecting the Erdös-Rényi phase transition
• Grand canonical ensembles of sparse networks and Bayesian inference
• Entropy of labeled versus unlabeled networks
• Statistical physics of exchangeable sparse simple networks, multiplex networks and simplicial complexes
• Entropy of microcanonical finite-graph ensembles
• A Gaussian integral that counts regular graphs
• Tsallis mapping in growing complex networks with fitness
• Entropy of random graph ensembles constrained with generalised degrees