The ambiguity of nestedness under soft and hard constraints

Abstract

Many real networks feature the property of nestedness, i.e. the neighbours of nodes with a few connections are hierarchically nested within the neighbours of nodes with more connections. Despite the abstract simplicity of this notion, different mathematical definitions of nestedness have been proposed, sometimes giving contrasting results. Moreover, there is an ongoing debate on the statistical significance of nestedness, since even random networks where the number of connections (degree) of each node is fixed to its empirical value are typically as nested as real-world ones. Here we propose a clarification that exploits the recent finding that random networks where the degrees are enforced as hard constraints (microcanonical ensembles) are thermodynamically different from random networks where the degrees are enforced as soft constraints (canonical ensembles). We show that if the real network is perfectly nested, then the two ensembles are trivially equivalent and the observed nestedness, independently of its definition, is indeed an unavoidable consequence of the empirical degrees. On the other hand, if the real network is not perfectly nested, then the two ensembles are not equivalent and alternative definitions of nestedness can be even positively correlated in the canonical ensemble and negatively correlated in the microcanonical one. This result disentangles distinct notions of nestedness captured by different metrics and highlights the importance of making a principled choice between hard and soft constraints in null models of ecological networks.

arXiv comment16 pages, 12 figures

References in corpus (23)

• Statistical mechanics and dynamics of solvable models with long-range interactions
• The statistical mechanics of networks
• The Statistical Physics of Real-World Networks
• Emergence of structural and dynamical properties of ecological mutualistic networks
• The Babe Ruth Algorithm: a fast, unbiased procedure to randomize presence-absence data matrices with fixed row and column totals
• Nestedness in complex networks: Observation, emergence, and implications
• Analytical maximum-likelihood method to detect patterns in real networks
• Maximum likelihood: extracting unbiased information from complex networks
• Randomizing bipartite networks: the case of the World Trade Web
• Equivalence and nonequivalence of ensembles: Thermodynamic, macrostate, and measure levels
• Factors determining nestedness in complex networks
• Breaking of ensemble equivalence in networks
• Detecting early signs of the 2007-2008 crisis in the world trade
• Phase transitions in a complex network
• Unbiased sampling of network ensembles
• Breaking the spell of nestedness
• Extensive load in multitasking associative networks
• From Dyson to Hopfield: Processing on hierarchical networks
• A Hebbian approach to complex network generation
• The role of asymmetric interactions on the effect of habitat destruction in mutualistic networks
• Sampling motif-constrained ensembles of networks
• Network nestedness as generalized core-periphery structures
• Ensemble inequivalence in random graphs

Cited by in corpus (11)

• Comparing Alternatives to the Fixed Degree Sequence Model for Extracting the Backbone of Bipartite Projections
• Reconstructing networks
• Meta-validation of bipartite network projections
• Strong ensemble nonequivalence in systems with local constraints
• Bow-Tie Structures of Twitter Discursive Communities
• Fluctuating ecological networks: a synthesis of maximum-entropy approaches for pattern detection and process inference
• Pattern detection in bipartite networks: a review of terminology, applications and methods
• fastball: A fast algorithm to sample bipartite graphs with fixed degree sequences
• The Evolution of Competitiveness across Economic, Innovation and Knowledge production activities
• Description length of canonical and microcanonical models
• Italian Twitter semantic network during the Covid-19 epidemic