Definition of nestedness
We first give an informal definition of nestedness and later a mathematical one. The neighbourhood of a vertex is the set of vertices that it is connected to. Then, an unipartite network is said to be nested if for each vertex, its neighbourhood contains the neighbourhoods of vertices which have lower degree (
König and Tessone 2011). For bipartite networks, a related definition applies, with the caveat that the neighbours must be of the same class (
Bascompte et al. 2003). In abstract terms, a nested graph may be thought as easy to identify: A graph is nested if, when its nodes are sorted by descending degree, the adjacency matrix is step-wise. This means that the adjacency matrix of a perfectly nested network can be divided into two well-differentiated regions: an upper-left with the existing edges and a lower-right region without any (cf. Fig.
2, top left).
For a proper mathematical characterisation of nestedness we briefly recapture the nomenclature for graphs. The adjacency matrix,
A, characterises the topology of a graph object
G. A non-zero entry in the adjacency matrix,
a
ij
≠0, indicates an edge between the two vertices
i and
j. Each vertex has a degree,
k
i
, which is the number of neighbours it is connected to. The total number of edges is
e and the total number of vertices is
n.
N is the set of all vertices and
E is the set of all edges. A unipartite graph can be decomposed by the concept of degree partition (
Mahadev and Peled 1995):
With the concept of degree partition a nested unipartite graph can be expressed as follows (
Mahadev and Peled 1995):
Concluding, we call a graph nested if its adjacency matrix, ordered by descending degree, is step-wise and if we can find a degree partition separating its set of vertices into an independent and a dominating set.
As a generalisation, bipartite graphs have two disjoint vertex sets U and V. In particular, each edge connects a vertex in the set U with one in set V, but not two vertices within the same set. A bipartite graph can analogously be decomposed into one degree partition for each of the two sets U and V as we have shown it for unipartite graphs. Without loss of generality we can separate a bipartite graph into independent sets and a dominating set within each of the two disjoint degree partitions U and V independently.
Nestedness can be now formally expressed as a local (pairwise) concept between two vertices.
In general, real-world networks will not be fully nested: either missing edges within or unexpected edges outside the expected structure will likely occur. By looking at the adjacency matrix the former appear as holes, whereas the latter appear as scattered dots. The number of these violations to the nested condition serve indeed as a straightforward quantification of the quality of the nested structure. In the following we will quantify the total number as well as the density of these violations.
Each term in the summation of Eq.
3 is equal to one for vertices
ℓ connected to the lowest degree node, but not connected to the larger degree node.
Now, counting the number of violations normalised by its maximum possible value, it is possible to derive a global measure for the density of violations in the entire network.
While the previous holds for undirected networks, it can be trivially extended to directed ones.
Detection and quantification of nestedness
In this section we briefly discuss methods most commonly used for quantifying nestedness in graphs. A naive approach to quantify the degree of nestedness is to compare the actual observed network with a perfectly nested one. The more the focal graph deviates from the perfectly nested graph, the less nested it actually is. And indeed, many methods of nestedness detection pick up the concept of deviation with respect a nested null model.
For example,
Graph Edit Distance (GED) (
Sanfeliu and King-Sun 1983) is such a measure for similarity between two networks. It counts the number of atomic operations (i.e. link rewiring) that are necessary to transform one network into another. However, it is evident that GED does not scale well on network size because of the combinatorial growth in the possible sequence of operations. It is, thus, for the practitioner impractical to use such method on most situations of interest (
Neuhaus et al. 2006).
Another method using a similarity measure is the NTC (Nestedness Temperature Calculator). The matrix temperature
T is a measure of how uniform is the distribution of edges across the adjacency matrix and is computed in three steps (
Rodríguez-Gironés and Santamaría 2006). First, a parametric isocline (representing perfect order) is created separating the regions in the adjacency matrix with and without edges. Second, the adjacency matrix is reordered by permuting rows and columns in a way that it maximises the packing of edges in the upper-left part of the adjacency matrix. Third, the distances of the holes remaining above and unexpected entries below the isocline that still deviate from the perfect order. Then, the matrix temperature is the sum of these distances. Unfortunately, the NTC is dependent on a normative concept of a global null model (
Ulrich et al. 2009), an arbitrary isocline (
Guimarães and Guimarães 2006) and has no unique solution (
Rodríguez-Gironés and Santamaría 2006).
The two approaches mentioned above result impractical because the number of possible permutations becomes extremely large in typical networks, therefore it is impossible to compute them all. With the NTC, for example, we have to find the one configuration that leads us to the maximum packing among
n!
m! others (in absence of duplicated rows and columns), (
Rodríguez-Gironés and Santamaría 2006)). NTC uses a heuristic approach to reach optimal packing but it does not attempt to solve this problem (
Rodríguez-Gironés and Santamaría 2006)). Having these concepts in mind we will discuss in the following the three most commonly used measures for nestedness, which are BINMATNEST, NODF, and FCM. For a more comprehensive discussion please refer to Ulrich et al. (
2009).
Binary matrix nestedness temperature calculator (BINMATNEST)
The method BINMATNEST is based on NTC and uses a genetic algorithm for reordering rows and columns so that the packing of the edges in the upper-left part of the adjacency matrix increases, aiming at minimising the matrix temperature. Before starting, BINMATNEST orders columns and rows in a descending order and removes empty and completely filled ones. On this matrix the genetic algorithm is encoded by two so-called
chromosomes, one accounting for the rows and columns. These chromosomes indicate the position that a focal row (or column) of the original matrix should take in a proposed solution. The genetic algorithm generates
offsprings based on the well-performing solution by cross-breeding the chromosomes. A more exhaustive explanation can be found in Rodríguez-Gironés and Santamaría (
2006).
If all edges are in the upper left corner the temperature is minimum (
T→0). If all edges are equally distributed in the matrix the temperature is maximum (
T→100, an arbitrary value). The normalised temperature of the adjacency matrix is given by the following expression Flores et al. (
2012):
$$ BINMATNEST = \frac{100 - T}{100} $$
(6)
If B
I
N
M
A
T
N
E
S
T=1 (0) the matrix temperature will be minimal T=0 (resp. maximal T=100). BINMATNEST is limited to connected graphs for which it computes the p-values of an ensemble of random graphs having the same size and density.
Nestedness metric based on overlap and decreasing filling (NODF)
NODF was developed for bipartite networks of ecological systems (
Almeida-Neto et al. 2008) but it is applicable to unipartite networks, too. This method is independent of row and column order since it computes the paired nested degree for each pair of both columns and rows. However, in contrast to BINMATNEST this method does not reshuffle the matrix. The nestedness for the whole matrix is the sum of nestedness degrees of all paired rows and columns normalised by the number of all pairs. The NODF metric assigns a value
\(M_{ij}^{H}\) to each neighbouring pair of vertices (
i,
j):
$$ M_{ij}^{H} = \left\{ \begin{array}{lr} 0, & \text{if}\ k_{i} = k_{j}\\ \frac{o_{ij}}{min(k_{i}, k_{j})}, & \text{otherwise } \end{array} \right.. $$
(7)
The total number of common edges among the two vertices
i and
j is given by
o
ij
. The procedure is carried out for columns (
\(M_{ij}^{P}\)) and rows (
\(M_{ij}^{A}\)) in an analogous procedure. Finally, the total nestedness for square matrices is then given by Saavedra et al. (
2011) for all columns
P and all rows
A:
$$ \text{NODF} = \frac{{\sum\nolimits}^{P}_{i<j}M_{ij} + {\sum\nolimits}^{A}_{i<j}M_{ij}}{\frac{P(P-1)}{2} + \frac{A(A-1)}{2}}. $$
(8)
For unipartite graphs the number of columns P and rows A is identical.
An advantage of NODF is its independence of matrix shape because it goes through both rows and columns (
Saavedra et al. 2011) and of the exact matrix order. However, this method fails in quantifying nestedness for perfectly nested graphs according to their mathematical definition when network density is either low or high, because all terms involving vertices with the same degree cancel each other out.
Fitness-Complexity Metric (FCM)
FCM ranks vertices in an iterative and non-linear process (
Tacchella et al. 2012). The iteration process couples a fitness term to a complexity term. Since FCM was solely developed for bipartite networks, we will not compare it to the above-mentioned methods in this contribution.
Benchmark graphs
For comparing sensitivity and reliability among different nestedness detection methods we require a solid benchmark framework. A benchmark graph must allow the modification of important network characteristics in a controlled manner, which are network density, degree distribution, extent of nestedness, etc. In particular, we look for a synthetic backbone graph, which has a deterministic profile and keeps the degree distribution constant, and has stylised properties similar to those found in real-world systems.
A common way of creating nested networks is through
threshold graphs (
Chvátal and Hammer 1977;
Mahadev and Peled 1995): for which, sequentially, new vertices are added; with probability
p the vertex is isolated, and with the complementary probability 1−
p it gets connected to all other existing vertices. All nested networks can be generated with finite probability by means of a threshold graph. However, for the purpose of this paper, threshold graphs are unsuited because the ensemble of graphs created is too diverse: Even for a given value of
p, the degree distribution is stochastic and the level of fluctuations cannot be neglected. These fluctuations are stronger in the important case of very low density networks (low values of
p), where the size of the dominating set is highly variable from realisation to realisation.
An alternative approach would be to provide a fixed degree sequence, which would make the threshold graph deterministic. However, it would imply the selection of a vector of values, determining the degree sequence.
To avoid these drawbacks, we resort on a generation process that generates deterministic degree distributions for a given parameter set and which is computationally efficient. In refs. König and Tessone (
2011); König et al. (
2014) it was shown that a network formation process where agents aim at maximising their centrality, naturally generates nested graphs with a single exogenous parameter
α that influences the topology of the generated graphs fundamentally. This network formation process has two contrasting dynamics, edge creation and edge severance. First, the edge creating dynamics allows each vertex to create an edge to the most central vertex in its second-order neighbourhood (i.e. the neighbours of its own neighbours) with a probability
α. Second, each vertex may severe the edge to the least central neighbour in its first-order neighbourhood with the complementary probability (1−
α).
Regardless of the specific system for which this model was intended, the resulting networks are fully nested, with the parameter
α controlling the network density. By changing
α we can tune a nested graph between two limiting cases. On the one hand, we obtain a star topology for
α→0 and, on the other hand, we obtain a fully-connected graph for
α→1. A first-order phase transition exists at the critical value
α=1/2 (
König and Tessone 2011). For finite networks, by increasing
α the matrix filling (i.e. the network density
γ
d
) increases monotonically. Typically, non trivial nested topologies exist for |
α−1/2|∝1/
n. The benchmark graphs are nested by definition for every value of
α∈[0,1]. The degree partition for the set of independent nodes is given by König et al. (
2014)
$$ n_{k} = \frac{1-2\alpha}{1-\alpha}\left(\frac{\alpha}{1-\alpha} \right)^{k} $$
(9)
In this paper we utilise this scheme for creating the benchmark networks as a starting point. After creating a nested component, this structure is
weakened by random rewiring of edges. We use a randomisation process which keeps the degree sequence constant: First, a vertex is chosen at random (with equal probability). Then, an edge originated in this vertex is randomly chosen for removal and the focal vertex is connected to another one to which it was not already connected to. By doing so, we preserve the degree distribution with respect to in-degree. The total number of rewired edges
e
rew
is given by
e
rew
=
ρ
rew
·
n in the sense that the higher is
ρ
rew
, the more edges are randomly rewired. If this vertex is isolated or if it is connected to all vertices in the network, nothing happens. This process can be seen as an abstract representation of a model where the emergent network has some degree of nestedness (
Bardoscia et al. 2013).
In absence of rewiring (i.e. ρ
rew
→0) the graph is almost perfectly nested and, thus, we expect that any quantification of nestedness should remain close to its maximum. Increasing the amount of rewired links such quantification should decrease monotonically. How fast such changes are detected is an indication of the sensitivity of the method. It is worth noticing that most real world networks in the literature involve what could be termed as small network sizes (i.e. few hundred nodes). While the results we present are for network of this order of magnitude, the results do not change qualitatively for larger ones.
The above-mentioned benchmark model is for unipartite graphs, which have an adjacency matrix with the identical number of rows and columns. However, with a trivial extension we can generalise it for bipartite graphs. Upon creating a benchmark graph of size n
a
for a unipartite case, the number of columns is extended to n
b
(n
b
>n
a
) and the same rewiring process as described above was performed. The asymmetric number of vertices for the two sets of vertices makes it possible to investigate bipartite benchmarks, whose adjacency matrices do not necessarily have the identical number of rows and columns.