The entropy of randomized network ensembles

Abstract

Randomized network ensembles are the null models of real networks and are extensivelly used to compare a real system to a null hypothesis. In this paper we study network ensembles with the same degree distribution, the same degree-correlations or the same community structure of any given real network. We characterize these randomized network ensembles by their entropy, i.e. the normalized logarithm of the total number of networks which are part of these ensembles. We estimate the entropy of randomized ensembles starting from a large set of real directed and undirected networks. We propose entropy as an indicator to assess the role of each structural feature in a given real network.We observe that the ensembles with fixed scale-free degree distribution have smaller entropy than the ensembles with homogeneous degree distribution indicating a higher level of order in scale-free networks.

(6 pages,1 figure,2 tables)

References in corpus (17)

• Emergence of scaling in random networks
• Community structure in social and biological networks
• Cooperative Game Theory Approaches for Network Partitioning
• Hierarchical organization of modularity in metabolic networks
• Specificity and stability in topology of protein networks
• Comparing community structure identification
• Dynamical and correlation properties of the Internet
• New Model of Internet Topology Using k-shell Decomposition
• MEDUSA - New Model of Internet Topology Using k-shell Decomposition
• k-core organization of complex networks
• The statistical mechanics of networks
• Mixture models and exploratory analysis in networks
• Statistical ensemble of scale-free random graphs
• Correlated random networks
• Principles of statistical mechanics of random networks
• Homogeneous complex networks
• A statistical mechanics approach for scale-free networks and finite-scale networks

Cited by in corpus (86)

• Community detection in graphs
• The structure and dynamics of multilayer networks
• Mathematical Formulation of Multi-Layer Networks
• 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
• Assessing the relevance of node features for network structure
• Generalized network structures: The configuration model and the canonical ensemble of simplicial complexes
• Entropy Rate of Diffusion Processes on Complex Networks
• Quantifying randomness in real networks
• Percolation on correlated networks
• The Shannon and the Von Neumann entropy of random networks with heterogeneous expected degree
• The entropic origin of disassortativity in complex networks
• Entropy of stochastic blockmodel ensembles
• Gibbs entropy of networks ensembles by cavity methods
• Reconstruction methods for networks: the case of economic and financial systems
• Multifractal Network Generator
• Clustering implies geometry in networks
• Entropies of complex networks with hierarchically constrained topologies
• Low Algorithmic Complexity Entropy-deceiving Graphs
• Unbiased sampling of network ensembles
• Entropy of dynamical social networks
• Extracting Information from Multiplex Networks
• Annealed and Mean-Field formulations of Disease Dynamics on Static and Adaptive Networks
• Mesoscopic Structures Reveal the Network Between the Layers of Multiplex Datasets
• Link prediction based on path entropy
• Critical fluctuations in spatial complex networks
• Fast and scalable likelihood maximization for Exponential Random Graph Models with local constraints
• Mapping and discrimination of networks in the complexity-entropy plane
• Enhancing neural-network performance via assortativity
• Complex Quantum Networks: a Topical Review
• Does the brain behave like a (complex) network? I. Dynamics
• Tailored graph ensembles as proxies or null models for real networks I: tools for quantifying structure
• Local Empathy provides Global Minimization of Congestion in Communication Networks
• Entropy distribution and condensation in random networks with a given degree distribution
• Configuration model for correlation matrices preserving the node strength
• Correlations between weights and overlap in ensembles of weighted multiplex networks
• The Grand Canonical ensemble of weighted networks
• Layer Communities in Multiplex Networks
• Sparse Maximum-Entropy Random Graphs with a Given Power-Law Degree Distribution
• Meta-validation of bipartite network projections
• Information content of colored motifs in complex networks
• Centrality anomalies in complex networks as a result of model over-simplification
• Statistical Mechanics of Multi-Edge Networks
• What is the Entropy of a Social Organization?
• Lower bound of assortativity coefficient in scale-free networks
• Duality between equilibrium and growing networks
• Approximate entropy of network parameters
• Information sharing in Quantum Complex Networks
• Networks with arbitrary edge multiplicities
• Entropy rate of non-equilibrium growing networks
• Fluctuations analysis in complex networks modeled by hidden variable models. Necessity of a large cut-off in hidden-variable models
• Analysis of the convergence of the degree distribution of contracting random networks towards a Poisson distribution using the relative entropy
• Percolation transition in correlated hypergraphs
• Weighted hypersoft configuration model
• The scaling of the minimum sum of edge lengths in uniformly random trees
• Random Simplicial Complexes: Models and Phenomena
• The role of adjacency matrix degeneration in maximum entropy weighted network models
• A geometric entropy detecting the Erdös-Rényi phase transition
• Statistical mechanics of random geometric graphs: Geometry-induced first order phase transition
• Riemannian-geometric entropy for measuring network complexity
• Algorithmic complexity of multiplex networks
• Analytical estimation of the correlation dimension of integer lattices
• Percolation transition and distribution of connected components in generalized random network ensembles
• Controlling network ensembles
• Models, Entropy and Information of Temporal Social Networks
• Entropy of labeled versus unlabeled networks
• Entropy rate of random walks on complex networks under stochastic resetting
• Sparse power-law network model for reliable statistical predictions based on sampled data
• Discovering universal statistical laws of complex networks
• Tackling information asymmetry in networks: a new entropy-based ranking index
• The Thermodynamics of Network Coding, and an Algorithmic Refinement of the Principle of Maximum Entropy
• Rotated multifractal network generator
• Entropy of microcanonical finite-graph ensembles
• Generating random networks that consist of a single connected component with a given degree distribution
• Constraints and Entropy in a Model of Network Evolution
• Ranking nodes according to their path-complexity
• Fluctuations of motifs and non self-averaging in complex networks. A self- vs non-self-averaging phase transition scenario
• A Gaussian integral that counts regular graphs
• Random walk in degree space and the time-dependent Watts-Strogatz model
• Ensemble equivalence for distinguishable particles
• Nodal statistics-based equivalence relation for graph collections
• Maximum entropy modeling of Optimal Transport: the sub-optimality regime and the transition from dense to sparse networks
• Tsallis mapping in growing complex networks with fitness
• Detectability threshold in weighted modular networks