Entropy of labeled versus unlabeled networks
arXiv:2204.08508 · doi:10.1103/PhysRevE.106.054308
Abstract
The structure of a network is an unlabeled graph, yet graphs in most models of complex networks are labeled by meaningless random integers. Is the associated labeling noise always negligible, or can it overpower the network-structural signal? To address this question, we introduce and consider the sparse unlabeled versions of popular network models, and compare their entropy against the original labeled versions. We show that labeled and unlabeled Erdos-Renyi graphs are entropically equivalent, even though their degree distributions are very different. The labeled and unlabeled versions of the configuration model may have different prefactors in their leading entropy terms, although this remains conjectural. Our main results are upper and lower bounds for the entropy of labeled and unlabeled one-dimensional random geometric graphs. We show that their unlabeled entropy is negligible in comparison with the labeled entropy. This means that in sparse networks the entropy of meaningless labeling may dominate the entropy of the network structure. The main implication of this result is that the common practice of using exchangeable models to reason about real-world networks with distinguishable nodes may introduce uncontrolled aberrations into conclusions made about these networks, suggesting a need for a thorough reexamination of the statistical foundations and key results of network science.
References in corpus (35)
- The structure and function of complex networks
- The statistical mechanics of networks
- Class of correlated random networks with hidden variables
- The Statistical Physics of Real-World Networks
- Entropy measures for complex networks: Toward an information theory of complex topologies
- The entropy of network ensembles
- A General Formalism for Inhomogeneous Random Graphs
- Parsimonious module inference in large networks
- The entropy of randomized network ensembles
- Assessing the relevance of node features for network structure
- Analytical maximum-likelihood method to detect patterns in real networks
- Network Analysis of Particles and Grains
- Maximum likelihood: extracting unbiased information from complex networks
- Quantifying randomness in real networks
- Generalized Bose-Fermi statistics and structural correlations in weighted networks
- The Shannon and the Von Neumann entropy of random networks with heterogeneous expected degree
- Entropy of stochastic blockmodel ensembles
- Enhanced reconstruction of weighted networks from strengths and degrees
- Breaking of ensemble equivalence in networks
- Gibbs entropy of networks ensembles by cavity methods
- Entropies of complex networks with hierarchically constrained topologies
- Unbiased sampling of network ensembles
- Random Graphs with Hidden Color
- Exponential Random Simplicial Complexes
- Entropy distribution and condensation in random networks with a given degree distribution
- Sparse Maximum-Entropy Random Graphs with a Given Power-Law Degree Distribution
- Ensemble nonequivalence in random graphs with modular structure
- Classical Information Theory of Networks
- Entropy of Spatial Network Ensembles
- Duality between equilibrium and growing networks
- Entropy rate of non-equilibrium growing networks
- Uncertainty Reduction for Stochastic Processes on Complex Networks
- Atomic subgraphs and the statistical mechanics of networks
- Grand canonical ensembles of sparse networks and Bayesian inference
- Statistical physics of exchangeable sparse simple networks, multiplex networks and simplicial complexes