# Nestedness in complex networks: observation, emergence, and implications

Manuel Sebastian Mariani<EMAIL_ADDRESS>Zhuo-Ming Ren  Jordi
Bascompte  Claudio Juan Tessone<EMAIL_ADDRESS>Institute of
Fundamental and Frontier Sciences, University of Electronic Science and
Technology of China, Chengdu 610054, PR China  URPP Social Networks,
University of Zurich, CH-8050 Zurich, Switzerland  Alibaba Research Center for
Complexity Sciences, Alibaba Business School, Hangzhou Normal University,
Hangzhou 311121, China  Department of Evolutionary Biology and Environmental
Studies, University of Zurich, Winterthurerstrasse 190, CH-8057 Zurich,
Switzerland

###### Abstract

The observed architecture of ecological and socio-economic networks differs
significantly from that of random networks. From a network science standpoint,
non-random structural patterns observed in real networks call for an
explanation of their emergence and an understanding of their potential
systemic consequences. This article focuses on one of these patterns:
nestedness. Given a network of interacting nodes, nestedness can be described
as the tendency for nodes to interact with subsets of the interaction partners
of better-connected nodes. Known since more than $80$ years in biogeography,
nestedness has been found in systems as diverse as ecological mutualistic
organizations, world trade, inter-organizational relations, among many others.
This review article focuses on three main pillars: the existing methodologies
to _observe_ nestedness in networks; the main theoretical mechanisms conceived
to explain the _emergence_ of nestedness in ecological and socio-economic
networks; the _implications_ of a nested topology of interactions for the
stability and feasibility of a given interacting system. We survey results
from variegated disciplines, including statistical physics, graph theory,
ecology, and theoretical economics. Nestedness was found to emerge both in
bipartite networks and, more recently, in unipartite ones; this review is the
first comprehensive attempt to unify both streams of studies, usually
disconnected from each other. We believe that the truly interdisciplinary
endeavor – while rooted in a complex systems perspective – may inspire new
models and algorithms whose realm of application will undoubtedly transcend
disciplinary boundaries.

###### keywords:

Complex Systems , Socio-economic networks , Ecological Networks , Nestedness ,
Economic Complexity , Emergence

###### Contents

  1. 1 Introduction
    1. 1.1 What are nested networks?
    2. 1.2 Historical background
    3. 1.3 How to read this article
  2. 2 Classes of (potentially) nested networks
    1. 2.1 Nested networks in graph theory
      1. 2.1.1 Nested split graphs
      2. 2.1.2 Threshold graphs
    2. 2.2 Ecological networks
      1. 2.2.1 Mutualistic networks
      2. 2.2.2 Antagonistic networks
      3. 2.2.3 Spatial networks
    3. 2.3 Socio-economic networks
      1. 2.3.1 Country-level trade networks
      2. 2.3.2 Contractor networks
      3. 2.3.3 Interbank networks
      4. 2.3.4 Spatial networks
      5. 2.3.5 Communication networks in organizations
      6. 2.3.6 Online communication networks and software development
    4. 2.4 Other classes of networks
  3. 3 Observing nestedness: metrics and null models
    1. 3.1 Metrics to quantify nestedness
      1. 3.1.1 Gap-counting metrics
      2. 3.1.2 Distance-based metrics
      3. 3.1.3 Overlap metrics
      4. 3.1.4 Eigenvalue-based metrics
    2. 3.2 Including a null model
      1. 3.2.1 Nine basic classes of randomization procedures
      2. 3.2.2 Computing the expected nestedness: maximum-entropy approach
      3. 3.2.3 Statistical tests
    3. 3.3 Nestedness maximization: Packing the adjacency matrix
      1. 3.3.1 Genetic algorithms
      2. 3.3.2 Non-linear iterative algorithms
      3. 3.3.3 Nestedness temperature minimization: BINMATNEST or fitness-complexity?
    4. 3.4 Bottom-line: How to measure nestedness?
  4. 4 Relation between nestedness and other systemic properties
    1. 4.1 Nestedness and other network properties
      1. 4.1.1 Nestedness and degree distribution
      2. 4.1.2 Nestedness and disassortativity
      3. 4.1.3 Nestedness and core-periphery structure
      4. 4.1.4 Nestedness and modularity
    2. 4.2 Nestedness and ecological properties
      1. 4.2.1 Nestedness and macroecological properties
      2. 4.2.2 Spatial networks: Nestedness and beta diversity
      3. 4.2.3 Interaction networks: Nestedness and relative species abundance distribution
    3. 4.3 Nestedness and economic properties
      1. 4.3.1 Individual nestedness contributions and the survival of firms
      2. 4.3.2 Nestedness and prediction of economic links
      3. 4.3.3 Nestedness maximization and the future development of countries
      4. 4.3.4 Nestedness and hidden economic capabilities
  5. 5 Emergence of nestedness: rewiring and formation mechanisms
    1. 5.1 Graph-theoretic mechanisms
      1. 5.1.1 Threshold model
      2. 5.1.2 Growing perfectly nested networks with arbitrary degree distribution
    2. 5.2 Ecological mechanisms
      1. 5.2.1 Self-organizing network model
      2. 5.2.2 Bipartite cooperation: specialization and interaction
      3. 5.2.3 Fitness maximization based on population dynamics
      4. 5.2.4 Nestedness as an evolutionary spandrel: Speciation and divergence
      5. 5.2.5 Invasion dynamics with different assemblage rules
    3. 5.3 Social and economic mechanisms
      1. 5.3.1 Network formation based on centrality maximization
      2. 5.3.2 Network formation in a two-stage game
      3. 5.3.3 Network rewiring based on social climbing
      4. 5.3.4 Emergence of nestedness in the country-product network: Innovation and novelty
    4. 5.4 Bottom-line: Why does nestedness emerge in empirical networks?
  6. 6 Implications of nestedness for systemic stability and feasibility
    1. 6.1 Robustness against structural perturbations
      1. 6.1.1 Topological robustness of nested networks
      2. 6.1.2 Nestedness maximization and the structural importance of individual nodes
    2. 6.2 Stability and feasibility of systems with competition and mutualism in the population dynamics approach
      1. 6.2.1 Stability and feasibility of equilibrium points
      2. 6.2.2 Stability and feasibility in a two-species competition model
      3. 6.2.3 Stability and feasibility in models with competition and mutualism
      4. 6.2.4 The impact of nestedness on feasibility and global stability
    3. 6.3 Local stability of mutualistic systems in the random-matrix theory approach
      1. 6.3.1 Stability-complexity relation: May’s result for random matrices
      2. 6.3.2 Stability of mutualistic networks
      3. 6.3.3 Stability of nested mutualistic networks
    4. 6.4 Bottom-line: What is the impact of nestedness on robustness, feasibility, and stability?
  7. 7 Observing nestedness at the mesoscopic scale
    1. 7.1 Quantifying the degree of nestedness of a subgraph
    2. 7.2 Finding the largest nested subgraph
    3. 7.3 Detecting in-block nestedness
      1. 7.3.1 Nestedness of network modules
      2. 7.3.2 Detecting in-block nested structures
      3. 7.3.3 Detecting multiple core-periphery pairs
  8. 8 Outlook
  9. A Software and relevant datasets
    1. A.1 Software for nestedness and network analysis
      1. A.1.1 Metrics and null models
      2. A.1.2 Nested network generation
      3. A.1.3 Community detection and nestedness at the mesoscopic scale
    2. A.2 Datasets of socio-economic and ecological networks
      1. A.2.1 World Trade data
      2. A.2.2 Ecological spatial networks
      3. A.2.3 Ecological interaction networks
  10. B Network-based metrics of node importance in bipartite networks

##  1 Introduction

Network science constitutes one of the pillars of the modern science of
complexity. Broadly speaking, network science can be defined as the “study of
the collection, management, analysis, interpretation, and presentation of
relational data” [1]. Given a complex system with many interacting components,
a suitable network representation simplifies its analysis by describing it –
in the simplest portrayal – as a collection of nodes and links connecting
them. The working hypothesis is that while the obtained network represents a
simplification of the complex system it was derived from, it carries enough
information to allow us to understand the functioning of the system and the
emergence of collective phenomena from the interactions of its constituents.
Leveraging its inherently interdisciplinary nature, network science borrows
ideas and tools from a variety of research fields, especially those where
networks (also. especially in mathematics and computer science, termed graphs)
have been long studied: graph theory [2], social science [3], economics [4],
scientometrics [5, 6], computer science [7], and ecology [8, 9], among others.

Perhaps one of the most intriguing features of real networks is the existence
of common structural and dynamical patterns that are found in a large number
of systems from various domains of science, nature, and technology. The
pervasiveness of structural patterns in systems from various fields makes it
possible to analyze them with a common set of tools [10]. A popular example of
such widespread structural patterns is the heavy-tailed degree distribution
[11] (i.e., the distribution of the number of connections per node). Power-law
degree distributions (often termed as “scale-free”) have been reported in a
wide variety of different systems, ranging from social and information
networks to protein-protein interaction networks (see [12] for a dedicated
book). The ubiquity of heavy-tailed degree distributions has motivated a large
number of studies aimed at unveiling plausible mechanisms that explain their
emergence [13, 10], understanding their implications for spreading [14, 15],
network robustness [16], synchronization phenomena [17, 18], etc.

This review article focuses on one of these widely-observed (and, as a result,
widely studied and debated) network structural patterns: _nestedness_.
Informally speaking, nestedness refers to a hierarchical organization where
the set of neighbors of a node is a subset (superset) of the neighbors of
lower (larger) degree. Originally conceived [19, 20] and discovered [21] in
biogeography where it was found in the spatial distribution patterns of
species [21, 22], nestedness has been found in a wide variety of systems,
including ecological interaction networks [23], trade networks [24, 25, 26],
inter-organizational networks [27, 28], firm spatial networks [29, 30],
interbank payment networks [31, 25], social-media information networks [32],
among others. Nestedness has been observed in two distinct families of
networks. On the one hand, bipartite networks (in which nodes of two
categories are connected in some way), like mutualistic networks in ecology.
On the other hand, more recently, nestedness has been found also in unipartite
networks, i.e., those where all the nodes are of the same nature, like
interacting agents in economics. The two streams of research have run mostly
in parallel, paying little or no attention to each other. To the best of our
knowledge, for the first time, this review provides an in-depth discussion of
both research areas.

The widespread occurrence of a given pattern in systems of different nature
naturally leads to a number of questions related to the fundamental mechanisms
behind its emergence and its implication for the systems’ functioning and
preservation. Based on the massive amount of works on nestedness, this review
will address several questions: Which classes of networks exhibit a nested
architecture? What are the possible mechanisms behind the emergence of
nestedness in ecological and socio-economic networks? Is the emergence of
nestedness the result of an optimization process where constituents tend to
maximize their fitness [33], or is it a consequence of the assemblage rules of
the system [34, 35]? Which mechanisms are responsible for the emergence of
nestedness in social systems and trade networks? [36, 25] Is nestedness
beneficial or harmful for the stability [37] and the persistence [38] of a
given ecological community? How is nestedness related to other widely observed
network properties, such as modularity [39, 40] and core-periphery structure
[41]? Given a network, is nestedness a global property, or a property that is
only respected by specific subsets of the network? [42, 43, 40, 44] How can we
exploit nestedness for predicting future properties of economic systems, such
as the gross domestic product of countries [45] and the appearance of a new
firm at a given geographic location [29]?

Admittedly, some of these questions have been controversial in the literature,
and sometimes, contradictory results have been supported by different studies.
A complete coverage of all existing theses on each topic would be impossible
to attain. However, when necessary, we will try our best to present the most
relevant findings that have been used to support competing claims.

This review article aims at providing the reader with a cross-disciplinary
perspective on nestedness, the subtleties associated with its observation, the
possible mechanisms behind its emergence, and its implications. Driven by
these questions, our review is an interdisciplinary effort where we collected
results from network science, statistical physics, ecology, economics, social
sciences, among others, which makes our review fundamentally different from
recent ones [46, 47, 48, 49] and books [9] which have focused exclusively on
the structure and dynamics of ecological networks. We hope that this effort
will allow researchers who have been interested in nestedness to learn the
methodologies and findings of scholars from other fields, which might
accelerate the progress of research on this area and, at the same time, reveal
similar organizing principles across disciplines [27].

A substantial part of the methodologies detailed in this article come from
statistical physics and dynamical systems: population dynamics [50, 38],
network formation models [36, 51], dynamical system stability analysis [37],
fitness optimization techniques [33, 44, 40], prediction based on dynamical
systems [45]. Other methodologies and results come from theoretical ecology
[38, 34, 35], theoretical economics [52, 25], and graph theory [53, 54]. We
will always try to provide sufficient background information for all the
methodologies and problems presented throughout the review.

###  1.1 What are nested networks?

Before detailing the historical developments of nestedness, we provide the
definition of perfectly nested networks together with the basic ideas behind
nestedness analysis. In abstract terms, we refer here to systems that are
composed of many constituents. Said elements are not isolated but they
interact with (or are related to) others. If these interactions can be
described as dyadic, the system admits a representation in terms of a
_network_ [4, 11, 10]: its constituents are represented as nodes (or vertexes)
and their mutual interactions (or relations) as links (or edges, or
_bonds_)111This is not the only way to represent relational data. For example,
temporal [55, 56] and multilayer [57, 58] networks provide with more
sophisticated representations that allow us to take into account temporal
effects and multiple types of interactions, respectively.. The set of nodes
connected to a certain node constitute its neighborhood, and the number of
such connections is referred to as its degree.

For example, if the network under consideration is a friendship network, two
individuals are linked when they have amity between them. In a trade network,
whose constituents are countries, an edge is present if there exists a trade
relationship between two given countries. In the examples above the elements
of the system (individuals or countries), while heterogeneous, are of the same
nature; it is then said that the network is unipartite. There are other
networks whose constituents can be divided into two distinct classes. For
example, in a habitat, a set of pollinator species and a set of flowering
plants are mutually related if the former helps in the pollination (and feeds
from) the latter. In this case, relations connect agents of a distinct nature.
This construct is called a bipartite network.

Figure 1:  Simple examples of nested and non-nested networks in both cases:
unipartite and bipartite networks. The adjacency matrices of the perfectly
nested networks (bottom panels) exhibit a clear “triangular” shape: a
separatrix partitions the matrices into unambiguously-defined filled regions
(i.e., regions that only contain ones) and empty regions (i.e., regions that
only contain zeros). In this review, we refer to this kinds of matrices as
perfectly nested matrices.

A _perfectly nested network_ is formally defined in the following terms:
consider any two nodes $i$ and $j$; if the degree of $i$ is smaller than the
degree of $j$, then the neighborhood of $i$ is contained in the neighborhood
of $j$. This definition is generally valid for unipartite and bipartite
networks with a single proviso: for the second group, the nodes to be compared
must belong to the same class. Any network here considered accepts a
representation in terms of a binary adjacency matrix $\mathsf{A}$ whose
elements $A_{ij}$ are equal to $1$ ($0$) if the two vertices are connected
(not connected). For the particular case of nested networks, the adjacency
matrix has a very peculiar shape (see lower row in Fig. 1): after re-ordering
its rows and columns by degree, there exists a monotonic separatrix above
which all the elements are equal to one, and zero below222Strictly speaking,
in bipartite network analysis, the matrix that connects nodes of different
type is typically referred to as biadjacency matrix [59] or incidence matrix
[11], whereas the adjacency matrix still refers to the matrix whose elements
represent all possible pairs of nodes – the elements that connect nodes of the
same type are, by definition, all equal to zero. To simplify the discussion,
when we will present methods for bipartite networks that apply equally well to
unipartite networks, we will refer to the biadjacency matrix as the adjacency
matrix. This abuse of terminology has no harmful consequences as the elements
of the adjacency matrix that connect nodes of the same type are all equal to
zero..

The first observation is that this definition can accommodate topologies as
different as a star network (a highly centralized topology where one hub is
connected to all the other nodes) and a fully-connected network (where each
node is connected with everyone else). It is also clear, however, that this is
a very stringent network topology which is seldom (if ever) observed in real-
world networks. Therefore, a priori, this kind of network structure may seem a
kind of curiosity. However, research has shown that networks showing this
property abound in a wide variety of research fields, and its definition
respected to a large extent: the vast majority of links are located in nested
neighborhoods as defined above. Asking “how much of a network structure
respects the property of nestedness” gave rise to several measures that aim at
quantifying the degree of nestedness of a given network, and several null
models to quantify the statistical significance of the observed levels of
nestedness. In this review, when we say that a network is “nested”, we mean
that it exhibits a level of nestedness (according to a given metric for
nestedness) that cannot be explained by a reasonable null model.

From this definition, it is evident that metrics for nestedness and null
models used to produce random networks that respect given constraints are of
vital importance [60, 61, 62]. Different metrics and null models may be
responsible for the validation or rejection of the hypothesis of nestedness
significance, and different combinations of metrics and null models can lead
to different conclusions [63]. Therefore, a proper definition of null models
is crucial, and far from trivial: null models purely based on preserving
simple topological properties can be either too restrictive – when the full
degree sequences must be exactly preserved in bipartite networks, for example
– offering little freedom from the observed network [61, 63, 64]; or too lax –
like requiring only that the network density is preserved – in which only
rarely the null hypothesis that the empirical degree of nestedness in a
network is significant can be rejected [65, 66, 48, 67]. These issues will be
discussed in Section 3.2 and 4.1.1.

The notion of nestedness introduced above is based on degree. Unless otherwise
stated, when we refer to nestedness throughout this review, we refer to the
nestedness by degree defined above. One can also take a different perspective
and ask whether a network exhibit a significant level of nestedness when
pairwise node orderings build on a node-level scalar property different than
the degree – e.g., species abundance [68] and islands’ area [69]. In other
words, one investigates whether the network’s adjacency matrix exhibit a
significant degree of nestedness once its rows and columns are sorted by a
given property $s$. This consideration leads to two additional notions of
nestedness that have been studied:

  * 1.

_Nestedness by other scalar properties._ Consider a node-level scalar property
$s$. One can re-define nestedness based on property $s$: the neighborhoods of
two given nodes $i$ and $j$ such that $s_{i}<s_{j}$ are nested by property $s$
if and only if the neighborhood of $i$ is a subset of the neighborhood of $j$.
The network is highly nested by property $s$ if many of its pairs of nodes’
neighborhoods are nested by $s$. In other words, a network is highly-nested by
$s$ if, after ordering the adjacency matrix’s rows and columns by $s$, the
resulting matrix exhibits a clear separation between its filled and its empty
region.

  * 2.

_Maximal nestedness._ One seeks to find the ordering of rows and columns that
maximizes the level of nestedness of the network. Scholars have especially
aimed to find maximal-nestedness structures in the context of nestedness
temperature analysis of ecological networks [22, 70] (see Section 3.1.2).

Based on the definitions provided above, one can compute, for instance, the
level of nestedness of an ecological mutualistic system based on species
abundance, and compare the resulting nestedness with the maximal nestedness
that can be achieved by the system [68]. In biogeography, one can study the
nestedness of a species-island network by both degree and island-level
environmental variables, including area and distance from the mainland – see
[69] for a comparative analysis.

Besides, nestedness-maximizing ranking algorithms have found important
applications for the prediction of the future development of countries [24,
45] and the identification of the most vulnerable constituents in ecological
networks [71] and world trade networks [72]. When defining existing metrics
for nestedness (Section 3), we will specify which aspect of nestedness they
capture. It is worth noticing that metrics for nestedness that take as input a
pairwise ordering of the nodes can be applied to measure both nestedness by
degree and nestedness by other scalar properties. On the other hand,
algorithms that seek to maximize nestedness (like those used to minimize
nestedness temperature [22, 70, 73]) cannot be used to evaluate the level of
nestedness by a specific node-level property; however, one can compare the
resulting maximal nestedness with the degree of nestedness by a property of
interest [68].

###  1.2 Historical background

While the concept of nestedness was precisely formulated by Patterson and
Atmar [21], the preceding literature offers studies [19, 20] where the notion
of nestedness was already implicitly discussed. In particular, in his book
_Zoogeography_ [20], Darlington described the potential effect of spatial
distance on the patterns of distribution of species on islands. He considered
two possible mechanisms of animal over-water dispersal when moving from the
continent to islands. He noticed that other things being equal, individuals of
a given species might be expected to populate first the nearest island, and
then move to the following nearest islands by crossing water gaps of minimal
length. This occupation process, referred to as _immigrant pattern_ by
Darlington [20] and _selective immigration_ by subsequent studies [74, 48],
naturally results in a nested structure where the species found on the
farthest islands (i.e., the species with the higher dispersal rate [74]) are
also found in the nearest islands (see Fig. 57 in [20]).

Besides, between the 70s and the 80s, ecologists became increasingly
interested in the spatial distribution patterns of species and statistical
null models to assess their statistical significance333In this respect, it is
surprising that a network null model that preserves the individual nodes’
degrees, typically referred to as _configuration model_ in network science
[11], was already designed in 1979 by Connor and Simberloff [65]. [75, 76, 65,
77]. It was not until 1986 that the notion of _nestedness_ was introduced
together with the first metric to measure it. This was done by Patterson and
Atmar [21] who found that several species spatial distribution patterns
exhibit a highly nested structure that cannot be explained by null models. In
a subsequent study, the same authors introduced the popular nestedness
temperature [22], a metric for nestedness which has been applied in a large
number of papers in ecology [48].

In parallel, graph theory had started investigating threshold graphs and
nested split graphs, which constitute classes of graphs that are equivalent to
perfectly nested graphs (see Section 2.1). Remarkably, the term “nested
bipartite graph” together with the first mathematical definition of a
perfectly nested bipartite graph already appeared in a paper [78] published by
the mathematician Franz Hering in 1971. Rigorous results for threshold graphs
and nested split graphs are reviewed in the 1995 book by Mahadev and Peled
[79].

In 2003, Bascompte et al. [23] brought the concept of nestedness to ecological
interaction networks by analyzing $25$ plant-pollinator networks and $27$
plant-frugivore networks, finding that most of them exhibit a degree of
nestedness that cannot be explained by degree-preserving null models.
Motivated by this finding, scholars have aimed at uncovering the basic
mechanisms that are potentially responsible for the emergence of nestedness
(see Section 5.2). Besides, a large number of works have attempted to
understand how nestedness impacts both the structural and the dynamical
stability of the system. Scholars have investigated this relation by means of
simulating co-extinction cascades [71], numerical simulations and analytic
results on models of mutualistic and competitive interactions [50, 38],
random-matrix theory [37]. We refer to Section 6 for the details.

Stimulated by works on ecological networks, interest in nestedness analysis
has arisen in socio-economic networks as well. In 2007, Soramäki et al. [31]
found that the interbank payment network is organized in a topology with a
densely connected core and a periphery that is only connected with the core: a
structure that is compatible with nestedness. Saavedra et al. [27] found that
manufacturer-contractor networks exhibit a nested structure, and proposed a
parsimonious model to explain its emergence. König et al. [25] found that four
economic networks are significantly nested: the Fedwire network of
settlements, Austrian inter-bank network, the world trade network and the
worldwide arm trade network. Besides, they proposed a network formation model
to explain its emergence.

As for bipartite trade networks, Saracco et al. [26] found that when analyzing
the bipartite country-product trade network by means of standard nestedness
analysis tools, a decrease of nestedness took place before the 2007-2008
financial crisis. In parallel, Tacchella et al. [24] have designed a non-
linear ranking algorithm to quantify the competitiveness of countries and the
sophistication of products. In fact, the algorithm sorts rows and columns of
the network’s adjacency matrix in such a way that the nested architecture of
the system is revealed [24, 71], and it often outperforms genetic algorithms
from the ecological literature in maximizing nestedness [73].

Symbol |  Network science |  Graph theory |  Ecology
---|---|---|---
$\mathcal{G}$ |  Network |  Graph |  Community
$i\in\\{1,\dots,N\\}$ |  Node |  Vertex |  Species
$N$ |  Network size |  Graph order |  Community size
$(i,j)$ |  Link, edge, bond |  Edge, arc |  Interaction
$\mathsf{A}=\\{A_{ij};A_{ij}=1\text{ iff }(i,j)\text{ is observed}\\}$ |  Adjacency matrix |  Adjacency matrix |  Interaction matrix
$E=\sum_{ij}A_{ij}$ |  Number of links/edges |  Graph size |  Number of pairwise interactions
$\rho=2\,E/(N\,(N-1))$ |  Connectance or Density |  Graph density |  Fill
$\mathcal{N}_{i}=\\{j|A_{ij}=1\\}$ |  Neighborhood |  Neighborhood |  Set of interactors
$k_{i}=\sum_{j}A_{ij}$ |  Degree |  Degree, valency |  Marginal total
$\braket{k}=N^{-1}\sum_{j}k_{j}=2\,E/N$ |  Average degree |  Average degree |  Average number of interactions per species
Node $i$ with $k_{i}\gg\braket{k}$ |  High-degree node, hub |  High-degree node |  Generalist
Node $i$ with $k_{i}\sim 1$ |  Low-degree node |  Low-degree node |  Specialist
$O_{ij}=\sum_{k}A_{ik}\,A_{jk}$ |  Common neighbors |  Common neighbors |  Overlap
$\Xi_{i}$ |  $i$’s Community |  $i$’s Cluster |  $i$’s Compartment

Table 1: Notation for binary unipartite networks. Mathematically equivalent
concepts are expressed through different terms in different disciplines. In
this review, we will mostly use the network science nomenclature, yet we will
sometimes switch to the ecology language when presenting results in ecology.

Symbol |  Network science |  Graph theory |  Ecology |  Biogeography
---|---|---|---|---
$\mathcal{G}$ |  Network |  Graph |  Community |  Region, archipelago
$\mathcal{R,C}$ |  Two disjoint sets of nodes |  Two disjoint sets of vertices |  Set of active and passive species |  Set of patches and species
$i\in\\{1,\dots,N\\}$ |  Class-$\mathcal{R}$’s node, Row-nodes |  Class-$\mathcal{R}$’s vertex |  Active species |  Species
$\alpha\in\\{1,\dots,M\\}$ |  Class-$\mathcal{C}$’s node, Column-node |  Class-$\mathcal{C}$’s vertex |  Passive species |  Patches, islands, sites
$S=N+M$ |  Network size |  Graph order |  Community size |
$(i,\alpha)$ |  Link, edge, bond |  Edge, arc |  Interaction |  Presence
$\mathsf{A}=\\{A_{i\alpha};A_{i\alpha}=1\text{ iff }(i,\alpha)\text{ is observed}\\}$ |  (Bi-)Adjacency or Incidence matrix |  (Bi-)Adjacency or Incidence matrix |  Interaction matrix |  Presence-absence matrix
$E=\sum_{i,\alpha}A_{i\alpha}$ |  Number of links/edges |  Graph size |  Number of pairwise interactions |
$\rho=E/(N\,M)$ |  Connectance, Density |  Graph density |  Fill |  Fill
$\mathcal{N}_{i}=\\{\alpha|A_{i\alpha}=1\\}$ |  $i$’s Neighborhood |  $i$’s Neighborhood |  Set of $i$’s partners |  Set of sites where $i$ is present
$\mathcal{N}_{\alpha}=\\{i|A_{i\alpha}=1\\}$ |  $\alpha$’s Neighborhood |  $\alpha$’s Neighborhood |  Set of $\alpha$’s partners |  Set of $\alpha$’s present species
$k_{i}=\sum_{\alpha}A_{i\alpha}$ |  Degree |  Degree, valency |  Row’s marginal total or Active species’ degree |  Species frequency
$k_{\alpha}=\sum_{i}A_{i\alpha}$ |  Degree |  Degree |  Column’s marginal total or Passive species’ degree |  Site richness
$\braket{k^{R}}=N^{-1}\sum_{j}k_{j}$ |  Average degree of class-$\mathcal{R}$ nodes |  Average degree of class-$\mathcal{R}$ nodes |  Average rows’ marginal total |  Average species frequency
$\braket{k^{C}}=M^{-1}\sum_{\alpha}k_{\alpha}$ |  Average degree of class-$\mathcal{C}$ nodes |  Average degree of class-$\mathcal{C}$ nodes |  Average columns’ marginal total |  Average site richness
Node $i$ with $k_{i}\gg\braket{k^{R}}$ |  Hub |  Hub |  Generalist |  Ubiquitous species
Node $i$ with $k_{i}\sim 1$ |  Low-degree node |  Low-degree node |  Specialist |  Rare species
$O_{ij}=\sum_{\alpha}A_{i\alpha}\,A_{j\alpha}$ |  Common neighbors |  Common neighbors |  Rows’ Overlap |  Rows’ Overlap
$O_{\alpha\beta}=\sum_{i}A_{i\alpha}\,A_{i\beta}$ |  Common neighbors |  Common neighbors |  Columns’ Overlap |  Columns’ Overlap
$\Xi_{i}$ |  $i$’s Community |  $i$’s Cluster |  $i$’s Compartment |

Table 2: Notation for binary bipartite networks. Mathematically equivalent
concepts are expressed through different terms in different disciplines. In
this review, we will mostly use the network science nomenclature, yet we will
sometimes switch to the ecology language when presenting results in ecology.

###  1.3 How to read this article

The main goal of this article is to review three main aspects of nestedness:
its observation, the modeling of its emergence, and its implications. We
detail below which Sections specifically deal with each of these three
aspects:

  * 1.

Observing nestedness. Section 2 provides an overview of the classes of real
networks of interest for this review. Sections 3 addresses the questions: How
to measure the level of nestedness of a given system? How to choose a suitable
null model to assess the statistical significance of the observed level of
nestedness? How to maximize the degree of nestedness of a given network by
properly ranking its nodes? Section 7 surveys the methods that aim to quantify
nestedness at a mesoscopic scale, which shifts the question from assessing
whether a given system is nested to finding sub-components of the system such
that the nodes that belong to the found components exhibit a nested
interaction topology.

  * 2.

Modeling the emergence of nestedness. Section 5 deals with possible mechanisms
to explain the emergence of nestedness that have been identified in graph
theory, ecology, and economics. Proposed mechanisms range from optimization
principles that postulate that nodes aim to maximize their fitness [33] or
their centrality [80, 36, 81, 25] when choosing their interactors, to
stochastic processes where nestedness is the outcome of duplication and link
randomization processes [34]. No agreement on the main mechanisms behind the
emergence of nestedness has been reached yet.

  * 3.

Implications of nestedness. Section 6 deals with both the implications of
nestedness for network robustness against targeted attacks, for the stability
and feasibility of equilibrium points of mutualistic dynamical processes on
interaction networks. In this context, _stability_ refers to the ability of
the system to return to its original equilibrium state after a small
perturbation (_local_ stability) or after a perturbation of any magnitude
(_global_ stability); _feasibility_ refers to the existence of equilibrium
points such that all species are represented by at least one individual. The
latter problem is critical to the assessment of the impact of nestedness on
the co-existence of species in ecological systems. The variety of methods
adopted in the literature to tackle these problems has led to variegated
conclusions.

The Outlook section will point to the current challenges in research in
nestedness as well as the most promising unexplored directions in the topic.

Due to its interdisciplinary nature, our review encompasses methodologies and
findings from diverse fields. For readers interested in different aspects of
nestedness, we provide the following road-map:

  * 1.

A reader interested in the ecological aspects of nestedness analysis may
consider reading the following sections: Sections 2.2 for a short overview of
the area; 3 to learn about the technical aspects of measuring nestedness;
4.2.3 to learn about the relation between nestedness and other properties; 5.2
and 5.4 for the main mechanisms that have been proposed in the ecological
literature to explain the observed nestedness of interaction networks; 6 for
the implications of nestedness for systemic robustness, stability, and
feasibility; 8 for an overview of current challenges and open directions in
research on nestedness.

  * 2.

A reader interested in the socio-economic aspects of nestedness analysis may
consider reading the following sections: Section 2.3 for a brief overview of
socio-economic networks of interest; 3 to learn about the technical aspects of
measuring nestedness; 4.3 to learn about the applications of nestedness to
predictive problems in socio-economic systems; 5.3 to learn about possible
social and economic mechanisms that can explain the emergence of nestedness in
socio-economic systems; 8 for an overview of current challenges and open
directions in research on nestedness.

  * 3.

A reader interested in the methodological aspects of nestedness analysis may
consider reading the following Sections: 2.1 to learn about the equivalence
between perfectly nested networks, nested split graphs, and threshold graphs;
3 to learn about the technical aspects of measuring nestedness; 5.1 to learn
how to generate perfectly nested networks with different degree distributions;
7 to learn the technical aspects and main implications of detecting nestedness
at the mesoscopic scale.

  * 4.

A reader who is already familiar with the literature of nestedness in
ecological systems and would like to catch up with the most recent
developments in the topic may consider reading the following Sections: Section
5 to discover recent mechanisms that have been proposed to explain the
emergence of nestedness in interaction networks; 6 to discover the recent
developments on the implications of nestedness for systemic robustness,
feasibility, and stability; 7 to learn the technical aspects and main
implications of detecting nestedness at the mesoscopic scale; 8 for an
overview of current challenges and open directions in research on nestedness.

The notation of the review for unipartite and bipartite networks is shown in
Table 1 and 2, respectively.

##  2 Classes of (potentially) nested networks

In this Section, we present classes of graph-theoretical, ecological, economic
and social systems where a nested architecture has been found. For each of
these research fields, we provide a classification of the types of networks
involved, and we mention some of the most representative papers that pointed
out their nested architecture. The main goal of this Section is to provide
readers with a brief introduction to the specific language of the systems
studied in this review, without aiming to be exhaustive. For each of the
systems presented below, wherever possible, we point to Web repositories where
datasets can be found (see Appendix A).

Research field |  System type |  Row nodes |  Column nodes |  Links
---|---|---|---|---
Ecology |  Spatial network, region |  Species |  Island/site |  Species occupy islands/sites
Ecology |  Pollination network |  Pollinator animal |  Plant |  Pollinator pollinates plant
Ecology |  Seed-dispersal network |  Frugivore animal |  Plant |  Frugivore disperses plant’s seed
Economics |  Interbank payment |  Bank |  Bank |  Bank pays bank
Economics |  Manufacturer-contractor |  Manufacturer |  Contractor |  Manufacturer outsources activity to contractor
Economics |  Trade |  Country |  Country |  Country trades with country
Economics |  International trade |  Country |  Product |  Country exports product
Table 3: Main networks of interest in this review, together with the
interpretation of their nodes and links. Networks where the row- and column-
nodes are the same are unipartite.

###  2.1 Nested networks in graph theory

This article will focus on the “physical” aspects of nestedness, including the
mechanisms that lead to its emergence and its implications for dynamical
processes on networks. While rigorous results from graph theory will not
constitute a central topic, it is instructive to acknowledge the deep
connection between nested networks and classes of graphs that have been widely
studied: threshold and split graphs [79]. The fact that many rigorous results
have been obtained for these two classes of graphs [79] might inspire their
application to the analysis of nested ecological and economic networks.
Rigorous theorems on graph theory [82] have been used, for example, by
Staniczenko et al. [83] to motivate the spectral radius of the adjacency
matrix as a possible metric for nestedness (see Section 3.1.4). For the sake
of completeness, we also mention that triangulated planar graphs are also
nested networks [84] and can be leveraged for hierarchical clustering of
empirical data [85]. In the following, we narrow down our focus to unweighted
unipartite networks (graphs), and define nested split and threshold graphs.

####  2.1.1 Nested split graphs

_Split graphs_ have been originally introduced and studied by Földes and
Hammer [86] and, independently, by Chernyak and Chernyak [87]. A graph
$\mathcal{G}$ can be referred to as a split graph if and only if its nodes can
be partitioned into a _clique_ (or _dominating set_) $\mathcal{K}$ and a
_stable set_ (or _independent set_) $\mathcal{S}$ – in this case, one denotes
the split graph as $\mathcal{G}(\mathcal{K},\mathcal{S})$. In the graph-
theoretical language, a _clique_ [88] is a subset of nodes such that every
pair of nodes that belong to the clique is connected through a link; a _stable
set_ [89] is a subset of nodes such that no two nodes are connected through a
link.

A split graph $\mathcal{G}(\mathcal{K},\mathcal{S})$ is referred to as _nested
split graph_ [90] if and only if the neighborhoods of the nodes that belong to
the stable set $\mathcal{S}$ are nested: given two nodes $i$ and $j$ that
belong to $\mathcal{S}$, if $k_{i}<k_{j}$, then the neighborhood of $i$ is
included in the neighborhood of $j$444In graph theory, one says that vertex
$j$ dominates vertex $i$ [79].. By definition, a nested split graph is also a
perfectly nested network. Such equivalence will be exploited in Section 5.1 to
introduce a generative algorithm for perfectly nested networks. The
fingerprint of a nested split graph is a _stepwise adjacency matrix_ [91]: a
symmetric binary matrix $\mathsf{A}$ whose elements $A_{ij}$ satisfy the
property that if $i<j$ and $A_{ij}=1$, then $A_{hk}=1$ if $h<k<j$ and $h\leq
i$. A stepwise matrix exhibits a peculiar “triangular” shape (see Fig. 1).

####  2.1.2 Threshold graphs

Importantly, nested split graphs are equivalent to an important class of
graphs: the threshold graphs [79]. _Threshold graphs_ were introduced in the
70s by Chvátal and Hammer [92]. A graph is referred to as a threshold graph if
and only if there exist non-negative real numbers $\\{w_{i}\\},\theta$ such
that a subset $\mathcal{U}$ of the nodes is stable if and only if its total
weight $w(\mathcal{U}):=\sum_{i\in\mathcal{U}}w_{i}$ does not exceed the
threshold $\theta$: $w(\mathcal{U})\leq\theta$. One can prove (Theorem 1.2.4
in the book [79]) that given a graph $\mathcal{G}$, the property that
$\mathcal{G}$ is a threshold graph is equivalent to the property that
$\mathcal{G}$ is a nested split graph. Therefore, nested split graphs,
threshold graphs, and perfectly nested networks are equivalent.

###  2.2 Ecological networks

As ecologists are typically interested in studying how species interact with
one another and with their surroundings, networks naturally emerge as a
powerful tool to study ecological systems. We introduce here the basic
concepts of three broad classes of ecological networks [9]: mutualistic
networks, antagonistic networks, and spatial networks.

####  2.2.1 Mutualistic networks

Mutualistic systems are typically represented as bipartite networks composed
of two kinds of nodes, corresponding to animal and plant species. In such
networks, _mutualism_ is the key element: the nodes of one class benefit from
the interactions with the nodes of the other class. Different types of
mutualism exist in nature. In line with [9], in this review, we focus on two
main types of mutualistic interactions: pollination and seed-dispersal. Both
mechanisms involve the dissemination of an agent (pollen or seeds) performed
by animals, in exchange for nutrients provided by the plant [93]. Yet, there
are fundamental differences between the two types of interactions: for
example, pollen has to be transferred to a very specific location (the stigma
of a conspecific flower), whereas a similar spatial target is not necessary
for seeds. We refer to [93] for an insightful discussion of analogies and
differences between the two mechanisms. For our purposes, we consider
mutualistic networks as bipartite networks where animals (”active species”)
interact with plants (”passive species”).

The study of mutualistic systems has a long and fascinating history in
ecology555We refer to Chapter One of the book [9] for a historical overview of
studies of mutualism in ecology.. Nestedness in both pollination and seed-
dispersal mutualistic networks has been found in 2003 by Bascompte et al.
[23]. That finding has spurred a large number of works that have aimed at
understanding both the possible mechanisms behind the emergence of nestedness
(see Sections 5.2), and the potential implications of nestedness for a given
mutualistic system (see Sections 6). Some of the conclusions on the impact of
nestedness on systemic stability are based on population dynamics models that
describe how the abundances of plant and animal species are affected by the
abundances of their interactors, given a topology of interactions. These
models of mutualism are described in Section 6.2.3.

####  2.2.2 Antagonistic networks

In contrast with mutualistic interactions, antagonistic pairwise interactions
benefit one species to the detriment of the other. We focus here on two
classes of antagonistic networks: food webs and host-parasite networks.

##### Food webs

While early studies of food webs date back to the first half of the XX century
[9], analysis of the structure and stability of food webs intensified in the
70s, also fueled by May’s fundamental theoretical work on the stability-
complexity relation [94] (see Section 6.3.1). The simplest type of food web is
a unipartite directed network where a directed link from species $i$ to
species $j$ means that species $j$ preys on species $i$ [11]. If a set of
species of interest preys on and is predated by the same sets of species,
mostly, one can coarse-grain the network by representing the set of species of
interest as a single node, referred to as trophic species [11]. This
unipartite directed network is typically referred to as _community food web_.
Besides, ecologists have considered subsets of a complete food web by
selecting, for example, a specific type of “resource” species (e.g., plants),
and all the species (e.g., herbivores) that consume the resource species. The
resulting bipartite networks are typically referred to as resource-consumer
[23] or source/sink networks [47, 11].

The ecological literature has reported mixed findings on the nestedness of
resource-consumer networks. Bascompte et al. [23] found that their level of
nestedness is significantly lower than that of mutualistic networks. This
finding has not been confirmed by a subsequent study by Kondoh et al. [95],
who found that the degree of nestedness of trophic is comparable to that of
mutualistic networks. As the nestedness of mutualistic networks has been
attracted substantially more attention than that of food webs, we mainly focus
on mutualistic networks in this article.

##### Host-parasitoid networks

Parasitoids represent a special type of predators: they lay their eggs inside,
on the surface of or near their hosts, and the feeding larvae use their host
as food [9]. This kind of interaction has been widely studied in ecology. As
being based on antagonistic interactions, one would expect host-parasitoid
networks to exhibit substantially different structural patterns compared to
mutualistic networks [96, 9]. Yet, some studies [97, 98] found that host-
parasite networks can exhibit a nested structure, and scholars have
investigated possible dynamical mechanisms that could lead to its emergence
[99].

####  2.2.3 Spatial networks

From a historical standpoint, following the seminal work by Patterson and
Atmar [21], spatial networks constitute the first class of systems where
nestedness has been extensively studied. The particular class of spatial
networks which has been studied by means of nestedness analysis is species
distribution bipartite networks: such networks are composed of two classes of
nodes, one representing species, and the other one representing habitat
patches (such as islands). In this review, spatial networks will be often
discussed in the Sections concerning distance-based metrics for nestedness
(Section 3.1.2) and null models (Section 3.2), yet surveying all the
mechanisms that have been proposed to explain the nested structure of spatial
networks falls outside the scope of this article.

###  2.3 Socio-economic networks

Figure 2: The adjacency matrices of four economic unipartite networks; their
rows and columns have been sorted by degree. From left to right, the Austrian
banking network; the global network of banks obtained from the Bank of
International Settlements (BIS) locational statistics, the world trade network
and the arm trade network. All these networks exhibit a significant level of
nestedness. Reprinted from [25]. Figure 3: The (bi-)adjacency matrix of the
bipartite country-product network (BACI dataset, year 2010), where the rows
(countries) and columns (products) have been sorted according to the fitness-
complexity algorithm (see Section 3.3.2). The existence of highly-diversified
countries (top rows) contradicts the standard view that the wealthiest
countries should focus on trading few products with a high degree of
specialization [100]; instead, the data show that the most developed countries
tend This finding is the basis for capability-based models that aim to explain
the topology of the country-product network (see Section 4.3.4). Reprinted
from [24].

Nestedness has been long-studied in ecology, at the point that it is widely
regarded as a central structural trait for ecological network analysis. At the
same time, it has recently attracted interest in the analysis of social and
economic systems [24, 29, 25, 32].

Both unipartite and bipartite socio-economic networks can exhibit significant
levels of nestedness. Significant levels of nesteness have been found in
various classes of socio-economic unipartite networks (see Fig. 2 for an
illustration), including: interbank networks [25], the country-country world
trade network [25] and the worldwide arm trade network [25]. Bipartite
networks that exhibit significant nestedness include the country-product
export network [24, 29, 26] (see Fig. 3 for an illustration), manufacturer-
contractor networks [27], firm-location spatial networks [29], firm-user-meme
networks in social media platforms [32].

This is particularly intriguing because it suggests that socio-economic and
ecological systems can exhibit qualitatively comparable structures, which can
be useful both to understand their common robustness properties, and to design
effective strategies to prevent catastrophic events [101].

####  2.3.1 Country-level trade networks

World trade datasets usually feature the volumes of exports of products
between countries over multiple years. From the raw data, one can then build a
country-country trade network or a country-product bipartite network, as
detailed below. We refer to A for the links to publicly available world trade
datasets.

##### Unipartite trade networks

The structure of the International Trade Network has been widely studied, both
from the country-country and from the country-product perspective. Given
publicly available data on the export of products from one country to another,
it is possible to construct unipartite country-country networks where nodes
represent countries, and links between countries represent the existence of a
trade exchange of a product between the two (binary network representation)
[102], or the total volume of export between the two countries (weighted
network representation) [103]. Scholars have investigated several structural
properties of unipartite trade networks, including their community structure
[104], their centralization [105], their clustering coefficient [102].

Importantly, De Benedictis and Tajoli [105] studied the temporal evolution of
the trade network, finding a strong and increasing heterogeneity of the
countries’ number of partners. Squartini et al. [102] found that most of the
structural properties of the binary country-country network can be traced back
to its degree sequence, whereas the same does not hold for the weighted
representation where higher-order structural patterns cannot be explained by
the countries’ total export volumes [103]. König et al. [25] found that the
binary country-country network exhibits a significantly nested structure, and
proposed a network formation model to explain its topology [36, 25] (see
Section 5.3.1). Beyond the widely-studied World Trade network, other
unipartite trade networks have been considered in the literature. For
instance, some scholars [106, 25] have investigated the topology of the global
arm trade network, finding that it exhibits a significantly nested structure.

Besides aggregate trade networks, there is a growing interest in the topology
of the trade networks for specific products [107] and industries [108]. Recent
studies suggest that the trade networks of more sophisticated products are
typically more centralized [109] and nested [107] than those of less complex
products. While positive, the correlation between product complexity (as
determined by node importance metrics, see Section 3.3.2) and trade-network
centralization is far from being perfect [109, 107], which suggests that
complexity and nestedness may provide complementary information on a product.

##### Bipartite trade networks

Another way to look at World Trade data is to study the bipartite country-
product network where countries are connected with the products they export.
While the input data for this analysis are typically weighted, scholars have
introduced procedures to “binarize” the network: for example, one can add a
binary link from country $i$ to product $\alpha$ if and only if the relative
share of the product in the export basket of country $i$ is larger than the
World’s average share [110]. Scholars have investigated the nested structure
of the country-product network [52, 29, 111, 112] (see Section 4.1.1),
proposed generative mechanisms to explain its emergence [52, 51] (see Sections
4.3.4-5.3.4), and investigated its dependence on data regularization
procedures and product aggregation schemes [113]. Besides, a recent stream of
works have introduced and studied ranking algorithms for countries and
products that enhance the nestedness of the country-product matrix [24, 114,
115, 116, 117] (see Sections 3.3.2, 6.1.2).

The nested structure of the country-product network has deep implications for
economic theories. Back in the XIX century, the comparative advantage theory
by Ricardo [118] predicted that countries benefit from specializing on the
products on which they have a comparative advantage. Besides, based on the
found U-shape relationship between metrics for country diversification and
income, Imbs and Wacziarg [119] claimed that “poor countries tend to
diversify, and it is not until they have grown to relatively high levels of
per capita income that incentives to specialize take over as the dominant
economic force.” On the other hand, the empirical organization of the country-
product network reported by recent literature [24, 29] (see Fig. 3) indicates
that, in fact, the most developed countries are highly diversified: they
exhibit diverse export baskets by having a revealed comparative advantage
[120] over a large number of products. By contrast, developing countries are
only competitive in the export of products that are also exported by highly-
diversified countries. Recent predictive schemes [121, 122, 45] based on
network-based ranking algorithms suggest that country diversification is
strongly correlated with the “economic fitness” of a country, and a country
whose economic fitness is larger than that of countries with a similar level
of development tend to economically grow in the future (see Section 4.3.3).

####  2.3.2 Contractor networks

In many economic systems, production is outsourced, which means that a firm
“outsources” a part of its internal activity to an external company [123].
Scholars have identified both benefits and negative effects of outsourcing; we
refer the interested reader to [123] for a review. Importantly for the present
article, one can build a network that connects the firms (“contractors” or
“designers”) to the manufacturing firms (“manufacturers”) that perform parts
of the contractors’ internal activities [124, 27].

Uzzi [124] analyzed the network of resource exchange between New York apparel
firms over almost two years (1990-1991). He was interested in determining
whether the structure of the transaction network can predict firms’ failure.
He found that (1) firms whose transaction volume is more heterogeneously
distributed across the other firms (i.e., more generalist firms) are less
likely to fail than firms that tend to only interact with few other firms
(i.e., more specialized firms); (2) The topology of the partners’ neighborhood
heavily affects the probability that a firm fails: firms that are less likely
to fail have neither too specialist nor too generalist partners.

By analyzing a $15$-year designer-contractor dataset in the New York garment
industry, a later study [28] revealed that the probability of firm failure is
strongly affected by the firm’s contribution to the overall nestedness of the
manufacturer-contractor network (see Section 4.3.1). Besides, Saavedra et al.
[27] found that manufacturer-contractor networks exhibit a significant nested
structure, and proposed a parsimonious model with bipartite cooperation to
explain the emergence of these structures (see Section 5.2.2).

Beyond designer-manufacturer networks, one can study other systems of
contractors that involve a buyer and a seller. For example, Hernández et al.
[125] an 18-month dataset from the Boulogne-sur-Mer fish market. This fish
market has the unique feature that the fish is sold through an auction
directly from the buyers to the sellers, and transactions are daily recorded.
Intriguingly, the aggregate buyer-seller network exhibits a significantly
nested architecture, which excludes the emergence of blocks that would
correspond to “niche” markets [125].

Figure 4: The topology of the US interbank payment network (first quarter of
2004). The figure only shows the undirected links that represent the 75% of
the total transaction flows. The network exhibit a clear core-periphery
structure, with a core of densely interconnected nodes, and a periphery of
nodes that are only connected with the core nodes. This topology can be
considered as a special case of a nested topology (see Section 4.1.3).
Reprinted from [31].

####  2.3.3 Interbank networks

Understanding the topology of interbank networks is critical to assess their
robustness, resilience, and effectiveness. Soramäki et al. [31] built an
interbank transaction network based on the Fedwire Funds Service, a real-time
gross settlement service. The topology of the network is shown in Fig. 4: it
exhibits a clear distinction between a core of densely interconnected nodes,
and a periphery of low-degree nodes that are only connected with nodes that
belong to the core. Besides, the network is disassortative, meaning that high-
degree nodes tend to be connected with lower-degree nodes, on average, than
low-degree nodes (see Section 4.1.2). The network, therefore, exhibits two
properties – core-periphery structure and disassortativity – that are strongly
correlated with nestedness (see Sections 4.1.2-4.1.3); similar structural
properties have been found in diverse interbank transaction and trade networks
by subsequent studies (see [126, 127, 128, 129], for instance).

Importantly, the core-periphery structure of interbank networks reveals
important insights about financial crises: for example, Fricke and Lux [128]
showed that the decline of interbank lendings during the 2008 financial crisis
was mostly due to the core banks reducing their number of active outgoing
links; Kojaku et al. [130] found that in correspondence of the 2008 crisis,
the Italian interbank network transitioned from a structure with multiple
core-periphery structures (see Section 7.3.3) to a bipartite structure [129]
where transactions are mostly established between the core and periphery
banks. The core-periphery structure can be considered as a particular case of
nestedness (see Section 4.1.3), which suggests that interbank networks exhibit
a significant level of nestedness as well. This hypothesis was recently
corroborated by König et al. [25] who found that both an Austrian interbank
network and the global banking network are significantly nested.

####  2.3.4 Spatial networks

In a similar way as spatial ecological networks connect spatial regions with
the species that inhabit them, spatial economic networks connect spatial
regions to the economic activities that are developed in them [29, 30]. Bustos
et al. [29] built a Chilean municipality-industry network by considering an
industry $i$ as present in a given municipality $\alpha$ if at least one firm
classified in industrial classification $i$ declared municipality $\alpha$ as
its tax residence. In this way, approximately $700$ different industries were
connected with Chile’s $347$ municipalities [29]. They found that the
resulting bipartite network exhibits a significantly nested structure, and
exploited this property for link prediction, i.e., to predict the appearance
and disappearance of industries in municipalities (see Section 4.3.2).

In a similar spirit, Garas et al. [30] built a city-firm network where $21$
economic activities were connected with $1,169$ cities in the world; also this
network turned out to be significantly nested. From a node-level perspective,
Gao and Zhou [131] analyzed a bipartite network connecting industries with the
31 Chinese provinces, finding that ranking algorithms that seek to maximize
the adjacency matrix nestedness (like the fitness-complexity algorithm [24])
provide a node score that is highly correlated with province-level
macroeconomic indicators.

####  2.3.5 Communication networks in organizations

In social science, the idea that different topologies of communication
networks lead to different performances of groups of individuals is not
recent. Already in 1941, Leavitt [132] tested the performance of groups of
individuals arranged in different communication topologies in solving puzzles.
He found that a network with a star-like structure (”wheel structure” in
[132]) performed better than more decentralized networks: the presence of a
“generalist” who could be quickly reached by the other nodes seemed to speed
up the problem-solving process. As reminded by Borgatti et al. [133], later
studies have shown that as the complexity of the puzzle increases,
decentralized networks tend to perform better.

This idea has motivated researchers to investigate how the structure of
organizations impacts their performance and ultimate success. Importantly,
organizations are made by the individuals who coordinate and constantly
enhance internal knowledge. Communication networks (with organization members
being nodes and communication events, as a proxy for information exchange,
being links) play an important role in the structure of organizations. This
fact has originated in the implicit knowledge that resides in the
organization, which becomes uncovered by the patterns of communication [134].

Kogut and Zander [134] suggested that economic firms are “social communities
in which individual and social expertise is transformed into economically
useful products and services by the application of a set of higher-order
organizing principles”. Thus, firms exist because of a social community
structured “by organizing principles that are not reducible to individuals”
[134]. Firms are better in sharing and transferring knowledge among
individuals than markets due to a fundamental dilemma: while higher
specialization increases productivity due to the division of labor, it also
increases the costs of communication and coordination among the agents [135].
Extant research has shown that the formal and informal networks of
communications vastly differ [136, 137]. The topology of this network,
therefore, plays a role in determining the global properties of the
organization.

Empirical work has found that intra-firm informal communication networks
exhibit properties compatible with nestedness [138, 43]. This is compatible
with theoretical arguments mimicking how these networks evolve [36]. From a
managerial perspective, an important question for future research is to assess
whether nested communication flows are beneficial or harmful to the
organization’s efficiency.

####  2.3.6 Online communication networks and software development

Online social networks and social media platforms offer us an unprecedented
amount of data on human activity. Often, these data come with fine-grained
temporal information, which allows us to study how network topology varies
over time. Valverde and Solé [139] have analyzed the network structure of
Open-Source software development communities. They found that the system
exhibits a strongly hierarchical structure where “an elite of highly connected
and mutually communicating programmers control the flow of information
generated by the OS community” [139]. Besides, the network is disassortative,
which means that the average degree of the low-degree nodes’ neighbors tends
to be larger than that of the high-degree nodes’ neighbors. Both properties
are compatible with nestedness; these results suggest that communication
networks between online community members might be a future field of
application for nestedness analysis.

A different relevant network for analyzing software development is the network
of dependencies and conflicts between software packages in a given operating
system. The temporal evolution of the modularity of this network has been also
investigated by Fortuna et al. [140] who found that for the Debian GNU/Linux
operating system, both modularity and the number of modules increased over
time.

In the context of social-media analysis, Borge-Holthoefer et al. [32] studied
the temporal evolution of nestedness and modularity for a bipartite user-
hashtag network collected from Twitter. They created the bipartite network by
collecting the memes related to the 2011 civil protests in Spain within a two-
month time window (see [32] for the details). They found that a sharp
transition from a modular to a nested topology occurs in the vicinity of a
critical event – see Section 4.1.4 for details.

More recently, the temporal evolution of topological properties of Twitter
communication networks has been investigated by Bastos et al. [141]. They
focused on the centralization of the user-user communication network (relative
to a specific topic, agriculture) in relation to the different level of
specialization of shared information (as determined by unsupervised text
classification techniques). Intriguingly, they found that a more centralized
topology emerges when discussions become more technical, whereas generic
discussions unfold over decentralized topologies. Their results confirm the
premises of classical diffusion theories (see Chapter 9 in [142]) that posit
that more centralized topologies are more appropriate for the dissemination of
innovations that involve a high level of technical expertise.

###  2.4 Other classes of networks

Beyond ecological and socio-economic systems, other classes of networks have
been found to exhibit nestedness. Kamilar and Atkinson [143] recently analyzed
various datasets on the distribution patterns of cultural traits across
populations of humans, chimpanzees, and orangutans. They found that for humans
and chimpanzees, these patterns are significantly nested, meaning that
“cultures with a small repertoire of traits tend to comprise a proper subset
of those traits present in more complex cultures” [143]. The same does not
hold for orangutans, and we refer to the Discussion section in [143] for a
detailed discussion of the possible reasons behind this discrepancy.

Cantor et al. [144] recently brought nestedness analysis to unipartite
biological networks from six different levels of biological organization
representing gene and protein interactions, complex phenotypes, animal
societies, metapopulations, food webs and vertebrate metacommunities [144].
They found that nestedness emerges at various biological scales, and
emphasized the importance of understanding the basic mechanisms behind its
emergence.

The core-periphery structure has received much attention in brain networks
[145] where it has been found that the separation between temporal core and
periphery changes can be used to predict individual differences in learning
success. As we shall see in Section 4.1.3, a core-periphery topology is a
special case of a nested topology.

Johnson et al. [146] analyzed various unipartite and bipartite networks of
different types, including food webs, brain networks, metabolic networks,
transportation networks and some popular network datasets (like the Zachary’s
Karate Club network [147] and a collaboration network of Jazz musicians
[148]). They found that a number of them exhibit significant nestedness –
their detailed results can be found in the appendix S5 of their article [149].

In principle, any unipartite or bipartite network can be analyzed by means of
nestedness metrics and null models. While, so far, the emergence and
implications of nestedness have been mostly investigated in ecological and,
more recently, socio-economic networks, we envision that they may gain
additional interest from other research areas.

##  3 Observing nestedness: metrics and null models

While perfectly nested networks can be unambiguously defined, they are rarely
found in nature. Yet, many real networks exhibit highly-ordered structures
where many pairs of nodes respect the definition of nestedness. This means
that in such networks, given two nodes $i$ and $j$ such that $k_{i}<k_{j}$,
most of node $i$’s neighbors are also neighbors of node $j$. In these highly
but imperfectly nested structures, the way we measure the level of nestedness
can heavily affect our conclusions on the significance of the pattern and its
relevance. This leads to several questions: how to best measure the degree of
nestedness in real networks that are not perfectly nested? How to compare the
level of nestedness across datasets of different size, density, and degree
distribution? What is the impact of more basic network properties (e.g.,
degree distribution) on the observed levels of nestedness?

This Section tackles these questions by providing an overview of the metrics
(Section 3.1) and null models (Section 3.2) that have been introduced with the
explicit goal to quantify the level of nestedness of a given system. Starting
with the unexpected absences metric by Patterson and Atmar [21], we will
survey various nestedness metrics including the popular nestedness temperature
[22, 70], NODF [150], and spectral radius [83]. Most of these metrics were
originally introduced in the ecological literature, yet their realm of
application has extended to economic and social networks.

In relation to the null models, there has been an intense debate in the
ecological community over which null model should be preferred to infer the
significance of the observed values of nestedness metrics [61, 48, 62]. We
will cover the main strength and weaknesses of the available null models. The
discussion will be further deepened in Section 4.1.1, where we will discuss
the statistical relation between the degree distribution and nestedness.

Besides, as we have pointed out in the Introduction, one can also re-arrange
the rows and columns of a given networks in such a way to minimize the number
of violations of the nestedness condition. Such reshuffling of rows and
columns can be interpreted as a node ranking algorithm, and it has important
implications for the identification of vulnerable species in ecological
systems [71], of competitive countries in international trade [24], and for
the effectiveness of targeted attacks on the network666The role of ranking
algorithm for the identification of structurally important and vulnerable
nodes is discussed in Section 6.1.2. [71, 72]. The results of a quantitative
comparison of existing ranking algorithms for bipartite networks [73] are
presented in Section 3.3.

###  3.1 Metrics to quantify nestedness

In line with Ulrich [48], we classify metrics for nestedness into four main
categories: gap-counting metrics (Section 3.1.1), overlap metrics (Section
3.1.3), distance metrics (Section 3.1.2), and eigenvalue-based metrics
(Section 3.1.4). In principle, all these metrics apply to any binary matrix.
For the sake of generality, unless otherwise stated, the definitions provided
below refer to bipartite binary networks. The corresponding definitions for
unipartite binary networks can be readily obtained by identifying the row-
nodes with the column-nodes. Not all the metrics below have been generalized
to weighted networks, yet we will provide some instances of metrics adopted in
weighted networks777W-NODF [151] and spectral radius [83]: see Sections 3.1.3
and 3.1.4, respectively..

Before defining the metrics, an important caveat that applies essentially to
all of them is that each of them generally depends on basic network properties
such as network size, density, and degree distribution; in order to compare
nestedness metrics across networks of different size and density, performing a
statistical analysis with a null model is a necessary step – this fundamental
aspect is deepened in Section 3.2. To prevent redundancy, we will avoid
repeating this caveat for each of the metrics defined below, yet the conscious
reader needs to always keep it in mind.

####  3.1.1 Gap-counting metrics

Gap-counting metrics build on the observation that the empty and filled
regions of a perfectly nested matrix are perfectly separated, as it is evident
from the illustration in Fig. 1. This implies that there are no ”absences”
(i.e., empty spots) in the filled region, and no ”presences” (i.e., filled
spots) in the empty region. One can, therefore, evaluate the degree of
nestedness of a given network by counting the number of violations of this
property.

##### Unexpected absences and presences

The number of unexpected absences $\mathcal{N}_{0}$ introduced by Patterson
and Atmar [21] counts how many times a node $i$ is not a neighbor of a node
$\alpha$ that has larger degree than its lowest-degree neighbor
$\beta_{min}(i)$ (i.e.,
$k_{\beta_{min}(i)}:=\min_{\alpha:A_{i\alpha}=1}\\{k_{\alpha}\\}$). In
formulae,

$\mathcal{N}_{0}=\sum_{i}\sum_{\alpha}(1-A_{i\alpha})\,\Theta(k_{\alpha}-k_{\beta_{min}(i)}).$
(1)

In this formula, the sum over $\alpha$ is restricted to the pairs such that
$k_{\alpha}>k_{\beta_{min}(i)}$ through the Heaviside function
$\Theta(k_{\alpha}-k_{\beta_{min}(i)})$, where $\Theta(x)=1$ if $x>0$,
$\Theta(x)=0$ if $x\leq 0$. For each contribution to the sum, the
$(1-A_{i\alpha})$ factor excludes node $i$’s neighbors. Importantly, Patterson
and Atmar notice that their nestedness metrics is a sum over the contributions
from all the individual nodes, which implies that one can compare the
contributions to nestedness from different individual nodes. A graphical
illustration of the $\mathcal{N}_{0}$ metric can be found in Fig. 5.

A complementary perspective is offered by the number $\mathcal{N}_{1}$ of
unexpected presences [152] metric which counts how many times a node $i$ is
neighbor of a node $\alpha$ that has smaller degree than its largest-degree
non-neighbor $\beta_{max}(i)$ (i.e.,
$k_{\beta_{max}(i)}:=\max_{\alpha:A_{i\alpha}=1}\\{k_{\alpha}\\}$). In
formulae,

$\mathcal{N}_{1}=\sum_{i}\sum_{\alpha}A_{i\alpha}\,\Theta(k_{\beta_{max}(i)}-k_{\alpha}).$
(2)

A graphical illustration of the $\mathcal{N}_{1}$ metric can be found in Fig.
5.

Figure 5: An example of calculation of $\mathcal{N}_{0}$ (left) and
$\mathcal{N}_{1}$ (right panel). Rows and columns are ordered by degree.
_Left, $\mathcal{N}_{0}$._ We scan each row from right to left. For each row
$i$, we consider the filled spot (1) that corresponds to the column
$\beta_{min}(i)$ with the smallest degree; each zero at the left of such
column, if it corresponds to a column $\alpha$ with degree
$k_{\alpha}>k_{\beta_{min}(i)}$, contributes to $\mathcal{N}_{0}$. _Right,
$\mathcal{N}_{1}$._ We scan each row from left to right. For each row $i$, we
consider the empty spot (0) that corresponds to the column $\beta_{max}(i)$
with the largest degree; each one at the right of such column, if it
corresponds to a column $\alpha$ with degree $k_{\beta_{max}(i)}>k_{\alpha}$,
contributes to $\mathcal{N}_{1}$.

One can also combine unexpected absences and presences into a single
nestedness metric. This was done by Cutler [152], who considered one single
node $i$ of intermediate degree. In line with the definition of nestedness,
absences of node $i$’s neighbors from the neighborhood of nodes with larger
degree are counted as unexpected absences ($U^{A}_{i}$), whereas occurrences
of node $i$’s non-neighbors in the neighborhoods of smaller-degree nodes are
counted as unexpected presences ($U^{P}_{i}$). One chooses the node $i^{*}$
that minimizes the sum of unexpected absences and presences
$U^{T}_{i}=U^{A}_{i}+U^{P}_{i}$; accordingly, the degree of nestedness is
defined as $U:=\min_{i}U^{T}_{i}=U^{T}_{i^{*}}$. The $U$ metric can be
interpreted as the minimum number of steps to convert (either by filling empty
spots or by deleting filled spots) the matrix in hand into a perfectly nested
matrix.

##### Number of departures

For an ordered matrix, the number of departures, $D$, is defined as the number
of times the absence of a node is followed by its presence in the neighborhood
of the next lower-degree node [153]. Simply, the number of departures is the
number of times the $i$th row does not interact with column $\alpha$ but the
$(i+1)$th row ($k_{i+1}<k_{i}$) does. Lomolino [153] estimated the statistical
significance of nestedness for each matrix by comparing the measured $D$
values with those obtained for randomly-ordered matrices. In the
randomization, species distributions are unaltered, but islands are randomly
ordered with respect to isolation and area. He calculated the normalized
number of departures of each ordered matrix as:

$\mathcal{N}=100\,\frac{(R-D)}{R},$ (3)

where $D$ is the number of departures in the ordered matrix and $R$ is the
mean number of departures for randomized networks.

##### Deviations from a perfectly nested matrix

A perfectly nested matrix is one where the filled elements in each row are
found as far to the left as possible, and the filled elements in each column
are found as far to the top as possible. Motived by such perfectly nested
structure, Brualdi and Sanderson [154] construct, for a given adjacency matrix
$\mathsf{A}$, a perfectly nested matrix $\mathsf{P}$ by shifting the filled
elements of $\mathsf{A}$ as far to the left as possible, while keeping their
row fixed. Such shifting procedure generates matrices where each row-node $i$
has the same degree $k_{i}$ as the original matrix $\mathsf{P}$, but the first
$k_{i}$ elements of row $i$ from the left are filled. The discrepancy of a
given matrix $\mathsf{A}$ can then be computed by summing over the rows the
unexpected absences in each row $i$, i.e., the number of zeros observed in the
first $k_{i}$ elements from the left. In formulas,

$\mathcal{D}=\sum_{i}\sum_{\alpha=1}^{k_{i}}(1-A_{i\alpha}).$ (4)

An illustration of the metric is provided in Fig. 6. Brualdi and Sanderson
[154] assessed the statistical significance of the metric by comparing its
observed value with its mean value in randomized networks generated with a
null model that preserves exactly the row-nodes’ and column-nodes’ degree
(Fixed-Fixed model, see Section 3.2.1).

Figure 6: An example of calculation of the number of discrepancies,
$\mathcal{D}$ [154]. From the original matrix (left panel), one constructs a
corresponding perfectly nested matrix (right panel) by shifting, for each row,
all its filled elements to the right. The elements of the observed matrix that
do not match the corresponding ones for the perfectly nested matrix are
interpreted as “discrepancies” (marked in red in the left panel).

####  3.1.2 Distance-based metrics

Distance-based metrics are based on a three-step computation. First, one
determines the ideal line that separates the empty and filled regions of the
matrix in a perfectly nested network. Second, one uses a suitable node-level
ranking algorithm to rearrange the rows and columns of the adjacency matrix in
such a way that its nestedness is maximized. Finally, for the rearranged
matrix, one computes the distance of the unexpected elements (empty elements
in the filled region, and filled elements in the empty region) from the ideal
line. The nestedness temperature of the network is given by the sum of the
contributions from all the unexpected elements of the rearranged matrix:
highly nested networks are characterized by low temperature (see Eq. (5)
below). Note that these metrics penalize more heavily unexpected absences and
presences that are far away from the ideal line. Such assumption was
originally motivated by arguments based on theories of island biogeography
[22], as discussed below.

##### Interpretation in terms of fragmented habitats formation

Distance-based metrics are motivated by considerations based on species
distribution patterns within naturally fragmented habitats [22]. Consider an
original biota that subsequently fragments into a collection of islands due to
natural causes. On each resulting island, there will be some species at larger
risk of becoming extinct. Some species will indeed become extinct, and larger
islands will be left, typically, with more species than smaller islands. The
resulting system can be represented as a species-island bipartite network
where each species is connected with the islands where its individuals are
found.

If the species extinction order is exactly the same in each island, the
resulting species-island network would be perfectly nested: each smaller
island would only include a subset of the species that are found in larger
islands. In this sense, nestedness is a property that signals the existence of
_order_ in the extinction patterns, whereas deviations from a perfectly nested
structure can be interpreted as “statistical noise” [22]. Therefore, Atmar and
Patterson made an explicit connection to statistical physics [155] and
information theory [156]: similarly as a high-energy configuration of a system
with many particles, the unexpected presence or absence of a species from an
island is a “surprising event”.

##### Nestedness temperature and Nestedness Temperature Calculator (NTC)

Figure 7: A graphical illustration of the terms $d$ and $D$ needed in the
temperature calculation [22, 70]. The rows’ and columns’ labels are rescaled
in such a way that the labels range from zero to one. From an unexpected
presence or absence (in the figure, presence A below the line of perfect
nestedness), one draws a straight line of slope $-1$. The distance $d_{ij}$ of
the unexpected element A is then normalized by $D_{ij}$; the nestedness
temperature defined by Eq. (5) is given by all the unexpected elements’
contributions $(d_{ij}/D_{ij})^{2}$. Reprinted from [70].

According to Ulrich [48], the matrix nestedness temperature $T$ [22, 70] is
“by far the most popular metric for quantifying nestedness”. Matrix
temperature depends on both the determination of the line of perfect
nestedness and the matrix packing algorithm (details below), and different
algorithms have been proposed for the temperature computation. The first
algorithm proposed is the Nestedness Temperature Calculator (NTC) [22] which
involves the following three steps:

  1. 1.

Determination of the line of perfect nestedness. For a matrix with connectance
$\rho=0.5$, it is straightforward to identify the diagonal that bisects the
matrix as the line of perfect nestedness (see Fig. 2 in [22]). For a matrix of
connectance different from $0.5$, the NTC software constructs the line of
perfect nestedness geometrically (see Fig. 4 in [22]), whereas the BINMATNEST
algorithm uses a function that determines the shape of the perfectly nested
matrix (see Eq. (6) below).

  2. 2.

Packing the matrix. Atmar and Patterson [22] argued that “for a matrix’s
temperature to be calculated, a matrix must first be packed to a state of
minimum unexpectedness”, and “row and column totals cannot be used as a
reliable guide for packing”. By arranging the elements of a given matrix
before computing the nestedness metric, we are not computing the nestedness
associated with the degree or a specific property, but the maximum possible
degree of nestedness in the system. We discuss the implications of this aspect
and possible methods for packing the matrix in Section 3.3.

  3. 3.

Computing the temperature. All the unexpected presences and absences
contribute to the matrix temperature. The unexpectedness $u_{i\alpha}$ of a
single (present or absent) link $(i,\alpha)$ is given by
$u_{i\alpha}=(d_{i\alpha}/D_{i\alpha})^{2}$, where $d_{i\alpha}$ denotes the
distance of $(i,\alpha)$ from the line of perfect nestedness (see Fig. 7), and
$D_{i\alpha}$ is geometrically defined as explained in Fig. 7. The total
unexpectedness $U$ of the matrix is defined as

$U=\frac{1}{N\,M}\sum_{(i,\alpha)\in\mathcal{U}}\Biggl{(}\frac{d_{i\alpha}}{D_{i\alpha}}\Biggr{)}^{2},$
(5)

where the sum is restricted to the set $\mathcal{U}$ of unexpected element
(i.e., empty elements above and filled elements below the line of perfect
nestedness). The matrix temperature $T$ is defined as $T=100\,U/U_{max}$,
where $U_{max}=0.04145$. A perfectly nested matrix has zero temperature,
whereas a maximally non-nested matrix has a temperature equal to $100$.

Variants of the NTC differ from the NTC in one or more of the three elements
above: line of perfect nestedness determination, packing algorithm, and
temperature computation. Besides, scholars have been also interested in
developing software for a fast computation of the nestedness temperature over
a large number of matrices [157]. Below, we briefly introduce two variants of
the NTC: BINMATNEST and the $\tau$-temperature.

##### BINMATNEST

The BINMATNEST algorithm [70] differ from the NTC in both the isocline
determination procedure and in the packing algorithm. In particular,
Rodríguez-Gironés and Santamaría [70] pointed out the following limitations of
the NTC: the line of perfect nestedness is not uniquely defined, and the
packing of the matrix is not optimal. In particular, as for the line
definition problem, they pointed out that the definition implemented by the
NTC does not identify a single line, but a set of curves [70]. To overcome
this limitation, they defined the following function:

$f(x;p)=\frac{0.5}{N}+\frac{N-1}{N}\Biggl{(}1-\Bigl{(}1-\frac{M\,x-0.5}{M-1}\Bigr{)}\Biggr{)}.$
(6)

The function depends on a parameter, $p$, that can be tuned to match the
desired level of connectance $\rho$; the resulting line of perfect nestedness
obtained in real networks is essentially indistinguishable from those obtained
by the NTC (see Fig. 2 in [70]). The packing algorithm implemented by the
BINMATNEST algorithm and its relation with that implemented by the NTC is
discussed in Section 3.3.

#####  $\tau$-temperature

The $\tau$-temperature [158] differs from the NTC and the BINMATNEST algorithm
in how the temperature is computed. Once the adjacency matrix is packed by a
given algorithm, the $\tau$-temperature of the matrix is proportional to the
Manhattan distance [158]

$\displaystyle D=\sum_{i,\alpha}A_{i\alpha}\,(i+\alpha).$ (7)

The $\tau$-temperature is given by the ratio between $D$ and the Manhattan
distance observed in randomized networks that preserve the link density of the
original network. Similarly as the Atmar and Patterson’s temperature, the
smaller the $\tau$-temperature, the higher the matrix’s degree of nestedness.
The $\tau$-temperature turns out to be positively correlated with the
nestedness temperature $T$, yet such correlation is far from being perfect
[158].

####  3.1.3 Overlap metrics

Overlap metrics are motivated by the definition of nestedness in terms of
nodes neighborhoods – more specifically, by the property that in perfectly
nested networks, the neighborhoods of nodes with lower degree is included in
the neighborhoods of nodes with larger degree. Based on this consideration,
one can then attempt to measure nestedness by evaluating how often neighbors
of lower-degree nodes are also neighbors of larger-degree nodes.

##### Wright and Reeves’ overlap-based metrics

In the context of species-island spatial networks, Wright and Reeves [159]
build metrics for nestedness on the intuition that in a perfectly-nested
network, if a species is found on an island, then it should be also found on
richer islands. One can therefore quantify nestedness by aggregating the
overlaps between the neighborhoods of pairs of islands. By introducing the
overlap $O_{\alpha\beta}=\sum_{i}A_{i\alpha}\,A_{i\beta}$, they defined the
$N_{c}$ metric as [159]

$\mathcal{N}_{c}=\sum_{(\alpha,\beta)}O_{\alpha\beta}=\frac{1}{2}\sum_{i}k_{i}\,(k_{i}-1)=\frac{N}{2}(\braket{k_{i}^{2}}-\braket{k_{i}}).$
(8)

where $O_{\alpha\beta}=\sum_{i}A_{i\alpha}\,A_{i\beta}$. Wright and Reeves
[159] introduce an additional nestedness metric $C$ by normalizing $N_{c}$ as
follows:

$C=\frac{\mathcal{N}_{c}-\mathbb{E}[\mathcal{N}_{c}]}{\mathcal{N}_{c}^{(max)}-\mathbb{E}[N_{c}]},$
(9)

where $\mathbb{E}[\mathcal{N}_{c}]$ is the expected value of $\mathcal{N}_{c}$
in randomized networks and $\mathcal{N}_{c}^{(max)}$ is the maximum value that
can be attained by $\mathcal{N}_{c}$. Wright and Reeves [159] compute
$\mathbb{E}[\mathcal{N}_{c}]$ based on a Equiprobable-Proportional null model
(see Section 3.2.1) where the probability that a given species is found on a
given island is proportional to the number of species in that island,
obtaining $\mathbb{E}[O_{\alpha\beta}]=k_{\alpha}\,k_{\beta}/N$. Hence, one
gets

$\mathbb{E}[\mathcal{N}_{c}]=\frac{1}{N}\sum_{(\alpha,\beta)}k_{\alpha}\,k_{\beta}=\frac{1}{2\,N}\sum_{\alpha,\beta}k_{\alpha}k_{\beta}=\frac{\braket{k}^{2}}{2\,N}.$
(10)

It is also possible to compute the maximum value $\mathcal{N}_{c}^{(max)}$
which is achieved when $O_{\alpha\beta}=\min\\{k_{\alpha},k_{\beta}\\}$. One
thus obtains [159]

$\mathcal{N}_{c}^{(max)}=\sum_{\alpha,\beta}k_{\beta}\,\Theta(k_{\alpha}-k_{\beta})=\sum_{\beta}k_{\beta}\,(\beta-1).$
(11)

Wright and Reeves [159] observed that the $C$ index ”is free of strong
dependence on the size of the presence-absence matrix, so that it is possible
to compare the relative nestedness of different datasets”. On the other hand,
Brualdi and Sanderson [154] notice that as the $N_{c}$ metric is entirely
determined by the row-column’s degrees (see Eq. (8)), it is of no use if we
wish to compare its observed value with its value in randomized networks that
preserve exactly the network degree sequence (see also Section 4.1.1).

##### Nested Overlap and Decreasing Fill (NODF)

Given a pair of row nodes $(i,j)$ of the same class such that $k_{i}>k_{j}$,
we expect their number of common neighbors
$O_{ij}=\sum_{\alpha}A_{i\alpha}\,A_{j\alpha}$ to be equal to $k_{j}$ for a
perfectly nested network, and smaller than $k_{j}$ a network that is not
perfectly nested. One can then define the row-NODF $\mathcal{N}^{R}$ as [150]

$\mathcal{N}^{R}=\sum_{(i,j)}\frac{O_{ij}}{k_{j}}\Theta(k_{i}-k_{j}),$ (12)

where $\Theta$ denotes the Heaviside function: $\Theta(x)=1$ if $x>0$,
$\Theta(x)=0$ if $x\leq 0$. This metric is maximal when $O_{ij}=k_{j}$ for all
pairs $(i,j)$ such that $k_{j}<k_{i}$. In the same way, one can the define the
column-NODF $\mathcal{N}^{C}$ as [150]

$\mathcal{N}^{C}=\sum_{(\alpha,\beta)}\frac{O_{\alpha\beta}}{k_{\beta}}\Theta(k_{\alpha}-k_{\beta}).$
(13)

The degree of nestedness is quantified by the total NODF:

$\eta=\frac{\mathcal{N}^{R}+\mathcal{N}^{C}}{\frac{N\,(N-1)}{2}+\frac{M\,(M-1)}{2}}.$
(14)

##### S-NODF

We present here the metric introduced by Bastolla et al. [50] to facilitate
the analytic computation of the impact of network structure on the co-
existence of species in mutualistic systems. We refer to this metric as stable
NODF (S-NODF) because it is a simple variant of NODF, yet it is more stable
with respect to small perturbations of the data, as we shall discuss below.

The definition of rows’ nestedness $\eta^{R}$ reads [50]

${\eta}^{R}=\sum_{(i,j)}\frac{O_{ij}}{\min{\\{k_{i},k_{j}\\}}}.$ (15)

This definition888Note that in the original paper [50], there was a typo such
that the summation symbol appeared both in the numerator and in the
denominator. differs from the one provided by NODF because it also includes
the contribution of pairs of nodes with the same values of degree. In other
words,

$\eta^{R}=\mathcal{N}^{R}+\sum_{(i,j)}\frac{O_{ij}}{k_{j}}\,\delta(k_{i},k_{j}),$
(16)

where $\delta(k_{i},k_{j})$ denotes the usual Kronecker delta:
$\delta(k_{i},k_{j})=1$ if $k_{i}=k_{j}$, $\delta(k_{i},k_{j})=0$ otherwise.
Compared to the NODF contribution $\mathcal{N}^{R}$, $\eta^{R}$ avoids
penalizing pairs of rows with the same degree. The soundness of including
pairs of rows with the same degree can be understood through the following
example. Suppose that, in a mutualistic network, two pollinators $i$ and $j$
have a degree of $24$ and $25$, respectively, and suppose that they have $18$
common neighbors (plants). This pair $(i,j)$ contributes to $\mathcal{N}^{R}$
with a contribution equal to $\mathcal{N}_{ij}=O_{ij}/k_{i}=18/24=0.75$.
However, suppose that a new interaction is observed between $i$ and a plant
that does not interact with $j$. In the updated network, both $i$ and $j$ have
a degree equal to $25$, and their contribution to NODF drops from $0.75$ to
zero: a small perturbation of the dataset can lead to a large variation in the
pairwise contributions to NODF.

By contrast, in the example above, the contribution to $\eta^{R}$ is only
marginally affected by the pollinator $i$’s new interaction: when $i$’s degree
increases from $24$ to $25$, the contribution
$\eta_{ij}=O_{ij}/\min\\{k_{i},k_{j}\\}$ to $\eta^{R}$ decreases from
$18/24=0.75$ to $18/25=0.72$, but it remains substantially larger than zero.
For pairs of nodes of similar degree, the pairwise contributions to S-NODF are
more stable with respect to small perturbations of node degree as compared to
the pairwise contributions to the original NODF.

One can compute analogously the columns nestedness; Bastolla et al. [50]
defined the overall degree of nestedness $\eta$ as:

$\eta=\frac{{{\eta}^{R}}+{{\eta}^{C}}}{2}.$ (17)

This nestedness index ranges from zero to one, where one corresponds to a
perfectly nested network; it is highly correlated with NODF [50], yet it has
the advantage of being more stable with respect to small structural
perturbations. Differently from Eq. (17), one can normalize
$\eta^{R}+\eta^{C}$ by the total number of pairs, as it was done for the
original NODF (see Eq. (14)). This leads to the alternative definition:

$\eta=\frac{{{\eta}^{R}}+{{\eta}^{C}}}{\frac{N\,(N-1)}{2}+\frac{M\,(M-1)}{2}}.$
(18)

We argue that the definition of $\eta$ provided by Eq. (18) should be
preferred to that by Eq. (17), especially when the number of rows is
substantially different than the number of columns.

##### JDM-NODF

Johnson et al. [146] considered a different normalization of nodes’ pairwise
overlap as compared to NODF and S-NODF. For a unipartite network, they defined
the total nestedness as

$\eta=\frac{1}{N^{2}}\sum_{i,j}\frac{O_{ij}}{k_{i}\,k_{j}}.$ (19)

In a similar way as in [160], we refer to this metric as JDM-NODF after its
inventors. This expression corrects a misprint of the metric introduced by
Bastolla et al. [50] (see footnote 8 above), and it allows us to estimate the
contribution $\eta_{i}$ of each node to the global level of nestedness:

$\eta_{i}=\frac{1}{N}\sum_{j}\frac{O_{ij}}{k_{i}\,k_{j}}.$ (20)

##### W-NODF

The weighted NODF (W-NODF) [151] metric is specifically tailored to weighted
networks. To assess the degree of nestedness of the columns of a weighted
bipartite network, one compares the weight $w_{i\alpha}$ of each link
$(i,\alpha)$ of a given column-node $\alpha$ with the weights $w_{i\beta}$ of
the links between column-nodes of higher degree ($\beta$ such that
$k_{\beta}>k_{\alpha}$) and the same partner $i$. The columns’ W-NODF
$\mathcal{N}^{C,W}$ is larger if the weights $w_{i\alpha}$ tend to be smaller
than the corresponding weights $w_{i\beta}$ for higher-degree column-nodes
$k_{\beta}>k_{\alpha}$ The definition is the following [151]

$\mathcal{N}^{C,W}=\sum_{(\alpha,\beta)}\frac{K_{\alpha\beta}}{k_{\alpha}}\,\Theta(k_{\beta}-k_{\alpha}),$
(21)

where $K_{\alpha\beta}$ denotes the number of $\alpha$’s weighted links with
lower weights than the links between higher-degree column-nodes and the same
row-node:

$K_{\alpha\beta}=\Theta(k_{\beta}-k_{\alpha})\,\sum_{i}A_{i\alpha}\,A_{i\beta}\,\Theta(w_{i\beta}-w_{i\alpha}).$
(22)

One can define an analogous weighted NODF $\mathcal{N}^{R,W}$ for the rows,
and then define the total weighted NODF $\eta^{W}$

$\eta^{W}=\frac{\mathcal{N}^{R,W}+\mathcal{N}^{C,W}}{\frac{N\,(N-1)}{2}+\frac{M\,(M-1)}{2}}.$
(23)

This equation is analogous to Eq. (14), with the difference that the rows’ and
columns’ contributions depends not only on which pairs of nodes interact, but
also on the weights of such interactions.

##### Normalizing overlap metrics based on null models

While one can in principle compare the observed values of any nestedness
metrics with the values observed in randomized networks obtained with a given
null model through standard statistical methods (like the $z$-score and
$p$-value, see Section 3.2), scholars have also incorporated null-models
effects directly into the overlap-based nestedness metrics. This has been done
by including a (multiplicative or additive) normalization term which is
typically determined by the expected values of the metrics under a suitable
null model. The $C$ metric by Wright and Reeves described above (see Eq. (9))
is an example of a normalized metric; we describe here analogous
normalizations for overlap metrics.

Based on the JDM-NODF metric defined by Eq. (19), Johnson et al. [146]
calculated the expected nestedness $\eta_{CM}$ of a random unipartite network
with expected degree sequence equal to the original network’s degree sequence
$\\{k_{1},\dots,k_{N}\\}$, by posing $A_{ij}=k_{i}\,k_{j}/(N\braket{k_{i}})$
in Eq. (19). We readily obtain $\eta_{CM}=\braket{k^{2}}/(N\braket{k}^{2})$;
if one is interested in capturing the nestedness that cannot be explained by
the degree sequence, it is therefore useful to consider the normalized JDM-
NODF

$\eta=\frac{\tilde{\eta}}{\eta_{CM}}=\frac{\braket{k}^{2}}{N\,\braket{k^{2}}}\sum_{i,j}\frac{O_{ij}}{k_{i}\,k_{j}}.$
(24)

Such metric is used to reveal the relation between nestedness and degree-
degree correlations in synthetic and real networks (see Section 4.1.2).

In a similar spirit but with a different methodology, Solé-Ribalta et al. [40]
considered a variant of NODF that compares the observed level of nestedness
(as determined by a variant of the NODF function defined by Eq. (14)) with the
expected nestedness under a suitable null model. In formulas, their normalized
nestedness metric is given by

$\widetilde{\mathcal{N}}=\frac{2}{N+M}\Biggl{\\{}\sum_{i,j}\frac{O_{ij}-\braket{O_{ij}}}{(N-1)\,k_{j}}\,\Theta(k_{i}-k_{j})+\sum_{\alpha,\beta}\frac{O_{\alpha\beta}-\braket{O_{\alpha\beta}}}{(M-1)\,k_{\beta}}\,\Theta(k_{\alpha}-k_{\beta})\Biggr{\\}}.$
(25)

Solé-Ribalta et al. [40] evaluated the expected row-row overlap
$\braket{O_{ij}}$ and column-column overlap $O_{\alpha\beta}$ as
$\braket{O_{ij}}=\braket{O_{ji}}=k_{i}\,k_{j}/M$ and
$O_{\alpha\beta}=k_{\alpha}\,k_{\beta}/N$, respectively999The two expected
values $\braket{O_{ij}}=\braket{O_{ji}}=k_{i}\,k_{j}/M$ is obtained by and
$O_{\alpha\beta}=k_{\alpha}\,k_{\beta}/N$ are obtained with the PE and EP null
model, respectively. In the PE (EP) model, the probability that a row-column
pair of nodes interact is proportional to the degree of the row-node (column-
node) – see Section 3.2.1 for details.. The behavior of this function deviates
from that of the original NODF for dense matrices where the expected pairwise
overlaps with the largest-degree nodes tend to be large and, as a result, the
respective contributions to $\widetilde{\mathcal{N}}$ tend to be small [40].

####  3.1.4 Eigenvalue-based metrics

What can the eigenvalues of the network’s adjacency matrix tell us about
nestedness? The last metric for nestedness considered here is the _spectral
radius_ [83], which builds upon graph-theoretical results on the spectral
properties of the adjacency matrix of bipartite networks [82, 161]. The
spectral radius $\rho(\mathsf{A})$ of a network is simply defined as the
dominant eigenvalue of the network’s adjacency matrix $\mathsf{A}$ [2].
Staniczenko et al. [83] considered $\rho(\mathsf{A})$ as a metric to quantify
nestedness. This interpretation is motivated by the two following theorems:

  * 1.

Consider all the connected bipartite networks composed of $S$ nodes and $E$
edges. The network with the largest spectral radius is a perfectly nested
network. This theorem has been proved by Bell et al. [82].

  * 2.

Consider all the connected bipartite networks composed of $N$ row-nodes, $M$
column-nodes, and $E$ edges. The network with the largest spectral radius is a
perfectly nested network. This theorem has been proved by Bhattacharya et al.
[161].

While the number of row-nodes and column-nodes is allowed to vary in the first
theorem (provided that their sum is equal to $S$), the second theorem
considers all networks with a fixed number of both row- and column-nodes.
Therefore, if perfectly nested structures lead to the largest spectral radius
for bipartite networks, the spectral radius $\rho(\mathsf{A})$ can be used to
quantify the degree of nestedness of a given network: the larger
$\rho(\mathsf{A})$, the more nested the network. The advantage of
$\rho(\mathsf{A})$ is that it can be computed in short time through well-
established techniques such as the power-method [162, 11]. Besides, one can
readily apply it to weighted networks – in that case, one simply needs to
measure the spectral radius of the weighted adjacency matrix.

While maximal $\rho(\mathsf{A})$ is associated with a perfectly nested
structure, it remains to be determined whether deviations from the maximal
$\rho(\mathsf{A})$ should be deemed as statistically significant or not. To
address this question, Staniczenko et al. [83] defined the $p$-value of a
network under a given null model as the probability that a network randomized
under that null model exhibits a larger $\rho(\mathsf{A})$. Such definition
depends critically on the null model that is chosen for the randomization. For
unweighted bipartite networks, Staniczenko et al. [83] considered three null
models of different degree of conservativeness (both a model that preserves
the degree sequence and two models that do not, see Section 3.2.1). For
weighted bipartite networks, Staniczenko et al. [83] consider an additional
null model that shuffles the weight values in the adjacency matrix
$\mathsf{A}$ but not their position.

###  3.2 Including a null model

Given a network and a structural pattern of interest, one is typically
interested in assessing its statistical significance: is the observed
structural pattern compatible with that observed in randomized networks which
preserve (a small number of) interesting macroscopic properties of the
original network? To address this question for nestedness, scholars have
introduced various null models and statistical tests, and applied them to the
nestedness metrics introduced in Section 3.1.

How to choose the null model has been widely debated in the ecology
literature. Back in the 70s, among the first scholars who attempted to infer
the significance of structural patterns in ecological networks, Sale [75]
analyzed networks where species are connected with the resources they use, and
he generated synthetic random networks by keeping fixed the number of
resources used by each species, and allowing the number of species using a
resource to vary (Fixed-Equiprobable model, see Section 3.2.1). Connor and
Simberloff [65] used a null model that preserves exactly species’ and islands’
degrees in spatial networks, in the same spirit as the popular configuration
model [163, 164, 165]. In 1982, Gilpin and Diamond [77] used a null model
which preserves, on average, the species’ and islands’ degree; their model
might be considered as a precursor of the popular Chung-Lu model [166].

A variety of additional randomization procedures have been introduced in the
80s and 90s in the ecological literature [60, 48]; the basics of such models
are provided in Section 3.2.1. More recently, Squartini and Garlaschelli [167]
contributed to the significance assessment problem by introducing a framework
to compute analytically the expected properties of networks with a given
expected degree sequence. In the same vein as the computation of thermodynamic
properties in statistical mechanics [168], their calculation is based on
constructing a maximum-entropy ensemble of networks with expected degree
sequence equal to the original network’s degree sequence (see Section 3.2.2).
This statistical-physics approach has been exploited recently to assess the
significance of nestedness in economic [112], and ecological [169] networks.

####  3.2.1 Nine basic classes of randomization procedures

When randomizing a given bipartite adjacency matrix, one has essentially two
possible choices to make – one for the row-nodes and one for the column-nodes
– about the preservation of the individual nodes’ degree. In line with Gotelli
[60], for both row-nodes and column-nodes, we consider three options: (1)
preserving exactly the individual nodes’ degree (the degree is _fixed_); (2)
preserving on average the nodes’ degree (the interaction probability is
_proportional_ to degree); (3) not preserving the nodes’ degree, and assuming
that the all the nodes have the same probability to interact with the nodes of
the other guild (the pairwise interactions are _equiprobable_). As the choice
among such three options can be made independently for rows and columns, we
have $3^{2}=9$ resulting classes of null models (see Table 4).

We emphasize that as soon as one has chosen the properties to keep fixed while
randomizing the rest, there are multiple alternative possible implementations
for the resulting model. Surveying all the possible implementations falls out
of the scope of this review, but we shall provide the main ideas of some of
them. It is also worth noticing that scholars have started investigating more
nuanced scenarios where one can “tune” the level of discrepancy of row-nodes’
and column-nodes’ degree (with respect to the observed degrees) in a
continuous manner [64]. These recent developments are not included in this
review; nevertheless, they demonstrate that research on null models is still
active in ecology, and consensus on the answers to fundamental questions
(e.g., which null model is more suitable for a given network and a given
structural pattern?) has yet to be achieved.

| Column Equiprobable | Column Fixed | Column Proportional
---|---|---|---
Row Equiprobable | EE | EF | EP
Row Fixed | FE | FF | FP
Row Proportional | PE | PF | PP
Table 4: Nine basic classes of randomization procedures, corresponding to nine
different null models. Each randomization procedure depends on two independent
choices. The first choice is whether to preserve the row-nodes’ degree. The
three possible options are to not preserve it (Row Equiprobable), to preserve
it exactly (Row Fixed), or to preserve it on average (Row Proportional). The
second choice is whether to preserve the column-nodes’ degree. Again, the
three possible options are to not preserve it (Column Equiprobable), to
preserve it exactly (Column Fixed), or to preserve it on average (Column
Proportional). Each pair of choices leads to a specific randomization
procedure (see the main text for a detailed explanation of each of them). This
Table is inspired by Table 2 in [60].

Figure 8: An illustration of a popular implementation [170, 165] of the Fixed-
Fixed null model which randomizes the network by preserving exactly the nodes’
degree. One randomly selects two links of the network $(a,b)$ and $(c,d)$; the
two selected links are replaced by two new links, $(a,d)$ and $(b,c)$, if
these two links did not exist before. In terms of the adjacency matrix, such
swap corresponds to a swap of “checkerboard units” [171], where the initial
and final configurations of the depicted 2x2 matrix are both checkerboard
units.

Below, we provide details for the nine basic null models of Table 4, we
provide some of the alternative names that have been used in the literature,
and we point to some of the papers that have used them.

  * 1.

Row Equiprobable – Column Equiprobable (EE) models. All interactions are
equiprobable, independently of the row-nodes’ and column-nodes’ degree. In a
possible randomization procedure, the $E$ original links are re-assigned to
randomly selected pairs $(i,\alpha)$ of nodes; the probability that pair
$(i,\alpha)$ is filled with a link is given by $1/(N\,M)$ [60]. Alternative
names for this model are: SIM1, R00 [60, 48], Type I model [23]. In ecology,
scholars who have used this null model include: Atmar and Patterson [22],
Gotelli [60]. In the graph-theoretical language, the EE model generates
Erdős–Rényi graphs [11, 10].

  * 2.

Row Equiprobable – Column Fixed (EF) models. The column-nodes’ degree sequence
$\\{k_{\alpha}\\}$ is kept fixed, whereas their partners are chosen at random.
In a possible randomization procedure, for each column $\alpha$, the
$k_{\alpha}$ original links are re-assigned to randomly selected row-nodes;
the probability that node $i$ is chosen as a partner is given by $1/N$ [60].
An alternative name for this model is SIM3 [60]. In ecology, scholars who have
used this null model include Gotelli [60].

  * 3.

Row Equiprobable – Column Proportional (EP) models. The probability that a
pair of nodes interact is proportional to the column-node degree, whereas all
row-nodes are equiprobable. In a possible randomization procedure, the $E$
original links are re-assigned to randomly selected pairs $(i,\alpha)$ of
nodes; the probability that pair $(i,\alpha)$ is filled with a link is given
by $k_{\alpha}/(N\,E)$ [60]. An alternative name for this model is SIM6 [60].
In ecology, scholars who have used this null model include Gotelli [60].

  * 4.

Row Fixed – Column Equiprobable (FE) models. The row-nodes’ degree sequence
$\\{k_{i}\\}$ is kept fixed, whereas their partners are chosen at random. In
the randomization procedure, for each row $i$, the $k_{i}$ original links are
re-assigned to randomly selected column-nodes; the probability that node
$\alpha$ is chosen as a partner is given by $1/M$ [60]. Alternative names for
this model are: SIM2, R0, Random0 [60]. In ecology, scholars who have used
this null model include: Sale [75], Inger and Colwell [76], Winemiller and
Pianka [172], Patterson and Atmar [21], Gotelli [60].

  * 5.

Row Fixed – Column Fixed (FF) models. The row-nodes’ and column-nodes’ degree
are exactly preserved. Alternative names for this model are: SIM9 [60]. In
ecology, scholars who have used this null model include: Connor and Simberloff
[65], Diamond and Gilpin [173], Brualdi and Sanderson [154], Gotelli [60]. A
popular randomization procedure101010Alternative randomization procedures have
been introduced in the literature. We refer the interested reader to [174,
170, 175, 176, 177, 178] for various randomization procedures and their
validation; to Appendix F of the book [9] for a general overview in ecology.
to keep a network’s degree sequence fixed is based on pairwise link swapping
(see [174, 165] and Fig. 8). In the network science language, the FF model is
equivalent to the popular _configuration model_ [11].

  * 6.

Row Fixed – Column Proportional (FP) models. The row-nodes’ degree sequence
$\\{k_{i}\\}$ is kept fixed, whereas their partner column-nodes are chosen
with probability proportional to their degree. In a possible randomization
procedure, for each row $i$, the $k_{i}$ original links are re-assigned
column-nodes randomly selected with probability $k_{\alpha}/E$ [60].
Alternative names for this model are: SIM4 [60]. In ecology, scholars who have
used this null model include: Coleman et al. [179], Graves and Gotelli [180],
Gotelli [60].

  * 7.

Row Proportional – Column Equiprobable (PE) models. The probability that a
pair of nodes interact is proportional to the row-node degree, whereas all
column-nodes are equiprobable. In a possible randomization procedure, the $E$
original links are re-assigned to randomly selected pairs $(i,\alpha)$ of
nodes; the probability that pair $(i,\alpha)$ is filled with a link is given
by $k_{i}/(M\,E)$ [60]. An alternative names for this model is SIM7 [60]. In
ecology, scholars who have used this null model include Gotelli [60].

  * 8.

Row Proportional – Column Fixed (PF) models. The column-nodes’ degree sequence
$\\{k_{\alpha}\\}$ is kept fixed, whereas their partner row-nodes are chosen
with probability proportional to their degree. In a possible randomization
procedure, for each column $\alpha$, the $k_{\alpha}$ original links are re-
assigned to row-nodes randomly selected with probability given by $k_{i}/E$
[60]. Alternative names for this model are: SIM5, R1, Random1 [60]. In
ecology, scholars who have used this null model include: Abele and Patton
[181], Connor and Simberloff [65], Patterson and Atmar [21], Gotelli [60].

  * 9.

Row Proportional – Column Proportional (PP) models. The probability that a
pair of nodes interact is proportional to both nodes’ degrees. In a possible
randomization procedure, the $E$ original links are re-assigned to randomly
selected pairs $(i,\alpha)$ of nodes; the probability that pair $(i,\alpha)$
is filled with a link is given by $k_{i}\,k_{\alpha}/E^{2}$ [60]. An
alternative name for this class of models is SIM8 [60]. In Bascompte et al.’s
implementation [23], the probability that a matrix element $A_{i\alpha}$ is
filled is given by $(k_{i}+k_{\alpha})/2$ – the resulting model is referred to
as Type II model [23]. In ecology, scholars who have used this class of null
models include: Gilpin and Diamond [77], Gotelli [60], Bascompte et al. [23],
among many others. Beyond ecology, randomization procedures that preserve, on
average, the network’s degree sequence are popular in the network science
literature. Among the null models that belong to the PP family, we find the
popular Chung-Lu model [166], the maximum-entropy models that are detailed in
Section 3.2.2, generalized hypergeometric ensembles [182].

The careful reader may have noticed that interchanging the roles of row-nodes
and column-nodes is equivalent to swapping pairs of classes of null models
that fall out of Table 4’s diagonal. In other words, if we transpose the
original adjacency matrix of the network, the effect of EP models acting on
$\mathsf{A}^{T}$ is equivalent to the effects of the corresponding PE models
acting on $\mathsf{A}$. For this reason, the PE and EP models can be seen as
equivalent; nevertheless, in line with previous works [60, 64], we preferred
to present separately pairs of models that are equivalent upon transposition
of the adjacency matrix, thereby implicitly assuming that the assignment of
the nodes to $\mathsf{A}$’s rows and columns is fixed111111For an ecological
bipartite network where the assignment of the nodes to the $\mathsf{A}$’s rows
and columns is fixed (e.g., a mutualistic network where $\mathsf{A}$’s rows
reprent insects and columns represent plants), there are ecological reasons to
randomize differently the two groups of nodes. For example, in a plant-
pollinator network, plants might be subject to many more phenotypical
constraints than insect pollinators, thereby restraining their degree of
specialization. Instead, insect pollinators might exhibit a higher flexibility
to change their diet. In a similar fashion, for spatial networks, varying the
richness of a species or modifying its spatial distributions correspond to
different ecological assumptions..

##### Which null model to choose?

When analyzing a collection of empirical networks, the choice of a null model
critically affects the fraction of networks that result as “significantly
nested”. Scholars have pointed out that while applying the EE model is the
simplest way to randomize a given network, assuming equiprobable interactions
might lead to highly unrealistic random networks. Ulrich [48] summarizes this
discontent by pointing out that “there is growing acceptance that null models
that do not consider species-specific differences and variability among sites
should not be used in biogeographic studies [66, 61, 183, 184] and even in
analyses of interaction matrices [185, 186, 187]”. Based on their results,
Joppa et al. [67] argue that “loose constraints invariably lead to the
conclusion of significant nestedness”, and that such loosely-constrained null
models “create consumers that differ in how generalized their diets are and
this confounds the conclusion”. In other words, there is agreement that the EE
model is sensitive to Type I errors: it can detect a significant nestedness in
networks when there is none [62, 160].

On the other hand, the FF model is the most conservative model, as it
preserves exactly both the row-nodes’ and the column-nodes’ degree. Both the
FF and the PP model set out to address the following natural question: are
networks still significantly nested when one constrains the degree sequence to
be the same (exactly or on average) as that of the original network? The use
of a more conservative null model substantially mitigates the fraction of
networks that are found as ”significantly nested”. Yet, the FF model is more
heavily affected by Type II errors [61]; we will come back to this point in
Section 4.1.1.

Another potential issue with the randomization procedures described above
(except for the FF model) is that they might generate “degenerate matrices”
where some nodes have a degree equal to zero. To overcome this potential
shortcoming, one can reject the degenerate networks (as done by the Swappable-
Swappable model [83, 160]), or perform the swapping between two matrix
elements only if it does not cause one of the nodes’ degree to drop to zero
(as done by the Cored-Cored model [160]).

Finally, using randomized networks to generate random networks has two
additional limitations: (1) it might be computationally slow when one attempts
to preserve exactly the nodes’ degree; (2) it relies on an arbitrary choice on
the number of independent realizations of the randomization procedure. We
would not face those two problems if we were able to compute analytically the
expected values of the structural properties of interest. In Section 3.2.2, we
will see that this is made possible by a compelling analogy with the problem
of computing the average value of macroscopic observables in statistical
mechanics.

####  3.2.2 Computing the expected nestedness: maximum-entropy approach

Null models based on network randomization have the disadvantage that the
results based on them depend on the number of performed independent
randomizations. Increasing the number of randomizations might make the results
more robust, but substantially increase the computational time, especially for
large networks. To overcome these limitations, a recent stream of literature
[167, 182] has provided theoretical frameworks to analytically compute the
expected properties of random networks with a set of fixed macroscopic
properties, for network properties that can be expressed in terms of the
adjacency matrix $\mathsf{A}$. In particular, Squartini and Garlaschelli [167]
introduced a maximum-entropy framework to analytically calculate the expected
value of network structural properties that can be expressed in terms of the
network’s adjacency matrix $\mathsf{A}$.

In the maximum-entropy framework, one calculates the expected value of the
network properties over a maximum-entropy ensemble of networks which
preserves, on average, some network properties – the degree sequences, in all
the cases considered here. This relieves us of running numerical simulations,
which makes the null-model expectations faster to be computed and independent
of the choice on the number of independent realizations of the adopted
randomization procedure. Importantly, Squartini and Garlaschelli’s framework
has been also generalized to weighted [188, 189] and bipartite networks [112].
The maximum-entropy method for unipartite networks has been applied to the
country-country export network [102] and to the interbank network [190]. Their
generalization to bipartite networks has been applied to assess the
significance of nestedness in bipartite World Trade networks [112] and
mutualistic networks [169] (see Section 4.1.1). We provide here the basic
ideas behind the method, and we refer the interested reader to [167, 112, 169]
for all the details.

##### Maximum-entropy approach in unipartite networks

In the maximum-entropy approach [167], we are interested in computing the
expected value of a given observable property $\Omega$ of the network over a
maximum-entropy ensemble of graphs with a given set of constrained properties.
Let us denote the value of observable $\Omega$ in the observed network
$\mathcal{G}^{*}$ by $\Omega^{*}$, the value of $\Omega$ in a generic network
$\mathcal{G}$ as $\Omega(\mathcal{G})$. Let us denote by
$\boldsymbol{\mathcal{C}}$ the vector of constrained properties of the
maximum-entropy ensemble that we will construct. In the following, the
constrained property is the complete network degree sequence; in this case,
the vector $\boldsymbol{\mathcal{C}}$ has $N$ elements, and
$\mathcal{C}_{i}=k_{i}^{*}$.

In Squartini and Garlaschelli’s framework [167], one seeks to find a
probability distribution $P(\mathcal{G})$ over the ensemble
$\\{\mathcal{G}\\}$ of possible random graphs that maximizes the entropy

$S[P(\mathcal{G})]=-\sum_{\mathcal{G}}P(\mathcal{G})\log{(P(\mathcal{G}))}$
(26)

under the constraints

$\begin{split}&\sum_{\mathcal{G}}P(\mathcal{G})=1,\\\
&\sum_{\mathcal{G}}P(\mathcal{G})\,k_{i}(\mathcal{G})=k_{i}^{*}\,\,\,\,\text{for
all}\,\,\,i\in\\{1,\dots,N\\}.\end{split}$ (27)

Basically, we aim to maximize the entropy of the network probability
distribution while keeping fixed the average nodes’ degree.

The problem is analogous to the entropy maximization in statistical mechanics
[168] where, given a system with a large number of microscopic constituents,
one seeks to maximize the entropy of the probability distribution over the
allowed microscopic configurations while keeping fixed the average total
energy of the system. Therefore, we know from statistical mechanics that the
solution of the problem is given by the canonical distribution

$P(\mathcal{G})=\frac{\exp{(-H(\mathcal{G},\boldsymbol{\theta}))}}{Z(\boldsymbol{\theta})},$
(28)

where $\boldsymbol{\theta}=\\{\theta_{1},\dots,\theta_{N}\\}$ is a vector of
$N$ Lagrange multipliers, and

$H(\mathcal{G},\boldsymbol{\theta})=\boldsymbol{\theta}\cdot\boldsymbol{k}(\mathcal{G})=\sum_{i}\theta_{i}\,k_{i}(\mathcal{G}).$
(29)

is the Hamiltonian of the system, and
$Z(\boldsymbol{\theta}):=\sum_{\mathcal{G}^{\prime}}\exp{(-H(\mathcal{G}^{\prime},\boldsymbol{\theta}))}$
is the partition function. The optimal Lagrange multipliers
$\boldsymbol{\hat{\theta}}$ can be found by first noticing that the expected
value of $A_{ij}$ in the maximum-entropy ensemble is given by

$\braket{A_{ij}}=\frac{e^{-\theta_{i}-\theta_{j}}}{1+e^{-\theta_{i}-\theta_{j}}};$
(30)

by enforcing the constraint
$\braket{\boldsymbol{k}(\mathcal{G^{\prime}})}=\boldsymbol{k}$, we obtain the
equation:

$\sum_{j\neq
i}\frac{\exp{(-\hat{\theta}_{i}-\hat{\theta}_{j})}}{1+\exp{(-\hat{\theta}_{i}-\hat{\theta}_{j})}}=k_{i}^{*}\,\,\,\,\text{for
all}\,\,\,i\in\\{1,\dots,N\\}.$ (31)

Eq. (31) corresponds to a system of $N$ equations that has a unique solution
$\boldsymbol{\hat{\theta}}$. We refer the interested reader to to [167] for
the full derivation of these equations.

Topological observables can be considered as functions $\Omega(\mathsf{A})$ of
the network’s adjacency matrix. By denoting as $\mathsf{A}^{(exp)}$ the matrix
whose element $A^{(exp)}_{ij}=\braket{A_{ij}}(\hat{\theta})$, we obtain the
expected value of observable $\Omega$ in the maximum-entropy ensemble as
$\Omega(\mathsf{A}^{(exp)})$. One can also compute the standard deviation of
observable $\Omega$ in the maximum-entropy ensemble as

$\sigma[\Omega]\simeq\sqrt{\sum_{i,j}\Biggl{(}\sigma^{*}[A^{(exp)}_{ij}]\,\frac{\partial\Omega[\mathsf{A}]}{\partial
A_{ij}}\Bigg{|}_{A_{ij}=A^{(exp)}_{ij}}\Biggr{)}^{2}},$ (32)

where $\sigma^{*}[A^{(exp)}_{ij}]=\sqrt{A_{ij}^{(exp)}\,(1-A_{ij}^{(exp)})}$
(see Eq. B31 in [167] and its derivation).

##### Maximum-entropy approach in bipartite networks

The framework for bipartite networks [112, 169] is conceptually analogous.
Differently from unipartite networks, one needs two sets $\theta^{R}$ and
$\theta^{C}$ of Lagrange multipliers for row-nodes and column-nodes,
respectively. The canonical distribution is given by

$P(\mathcal{G})=\frac{\exp{(-H(\mathcal{G},\boldsymbol{\theta}^{R},\boldsymbol{\theta}^{C}))}}{Z(\boldsymbol{\theta}^{R},\boldsymbol{\theta}^{C})},$
(33)

where $\boldsymbol{\theta}^{R}=\\{\theta^{R}_{1},\dots,\theta^{R}_{N}\\}$ is
the vector of Lagrange multipliers for the $N$ row-nodes,
$\boldsymbol{\theta}^{C}=\\{\theta^{C}_{1},\dots,\theta^{C}_{M}\\}$ is the
vector of Lagrange multipliers for the $M$ column-nodes, $Z$ is the
normalization factor, and the Hamiltonian function is given by

$H(\mathcal{G},\boldsymbol{\theta}^{R},\boldsymbol{\theta}^{C})=\sum_{i}\theta^{R}_{i}\,k_{i}(\mathcal{G^{\prime}})+\sum_{\alpha}\theta^{C}_{\alpha}\,k_{\alpha}(\mathcal{G^{\prime}}),$
(34)

Again, one obtains the expected values of the adjacency matrix elements as