2.1 Structural Metrics
Structural metrics are a well-known area in the conventional analysis of graphs. They are also used to explain stability—or the lack of it—in a network, and determine how viruses spread through a network under node/link removal [
10]. Preliminary robustness analysis is carried out by considering the following basic network properties:
average
nodal
degree
\((\langle k\rangle )\),
average
shortest
path
length
\((\langle l\rangle )\),
diameter (
D) and
assortative
coefficient (
r) [
2]. In this sense, networks with higher
\(\langle k\rangle\) are considered better-connected on average and, consequently, are likely to be more robust (i.e. there are more chances to establish new connections). In regards to
\(\langle l\rangle\), it is calculated as an average of all the shortest paths between all the possible origin–destination vertex pairs of the network. A network is more robust if
\(\langle l\rangle\) is at its lowest as it is likely to lose fewer connections.
D is the longest of all the shortest paths between pairs of nodes, thus one would want the diameter of networks to be low. The
r coefficient lies within the range [–1, 1] and it defines two types of networks.
Disassortative networks with
r < 0 have an excess of links connecting nodes of dissimilar degrees. The opposite properties apply to
assortative networks with
r > 0 that have an excess of links connecting nodes of similar degrees [
11]. As can be found in [
4], such networks exhibit greater vulnerability to certain types of targeted attacks.
Based on \(\langle k\rangle\), the heterogeneity (σ
k
) is a coefficient of variation of the connectivity. σ
k
is defined as the standard deviation of the \(\langle k\rangle\) divided by the \(\langle k\rangle\). The lower σ
k
value translates to higher network robustness. The Efficiency (ε) as the averaged sum of the reciprocal (multiplicative inverse) of the shortest paths is also defined. The greater the ε value, the greater its robustness is. Vertex
connectivity (κ) represents the smallest number of nodes that must be removed to disconnect the network. The same definition can be applied to edge
connectivity (ρ) when considering links instead of nodes. The clustering
coefficient
\((\langle C\rangle )\) captures the presence of triangles formed by a set of three nodes, and compares the number of triangles to the number of connected triples.
In addition, structural metrics also use the adjacency and Laplacian matrices to abstract and calculate the robustness of the networks. The
symmetry
ratio (SR) is calculated as the quotient between the distinct eigenvalues of the network adjacency matrix and the diameter
D. Networks with low SR are considered more robust to random failures or targeted attacks. The
largest
eigenvalue
or
spectral
radius (
λ
1) is the largest nonzero eigenvalue of the adjacency matrix of a network [
10]. Generally, networks with high values of λ
1 have a small
D and higher node distinct paths. The
λ
1 metric also provides information on network robustness [
11] and captures the virus propagation properties of networks defining an epidemic threshold of node infection [
12].
Algebraic
connectivity (
λ
2) is defined as the second smallest Laplacian eigenvalue.
λ
2 measures how difficult breaking the network into different components is. Higher λ
2 values indicate better robustness [
13]. Networks with identical
λ
2 can be compared using
natural
connectivity (
\(\overline{\lambda }\)). The
\(\overline{\lambda }\) metric characterizes the redundancy of alternative paths by quantifying the weighted number of closed walks of all lengths. In addition,
\(\overline{\lambda }\) is expressed as the average of the eigenvalues of the adjacency matrix, where a higher value indicates a more robust network. [
14].
Effective
graph
resistance (EGR), can be written as a function of nonzero Laplacian eigenvalues. The EGR metric measures the number of paths between two nodes and their length. The smaller the EGR value is, the more robust the network [
15].
The
graph
diversity (GD) is related to the number of nodes shared with the shortest path considering all possible paths between two nodes. This metric is equal to one when paths do not share any common point of failure (node or link). The total graph diversity (TGD) is the average of all effective path diversity (EPD) over all paths. Consequently, calculating this metric requires significant computational resources. Larger TGD indicates greater robustness [
16].
The
weighted
spectrum (WS) metric is based on the eigenvalues (
λ
i
) of the normalized Laplacian matrix and the
N-cycle of a graph. Different values of
N indicate different topology properties to be analyzed e.g.
N = 3 is associated to the clustering coefficient, meanwhile
N = 4 is related to the number of disjoint paths in a network. The network robustness is calculated as
W′−
W, where
W denotes the default WS of the original graph and
W′ denotes the WS of the resulting graph after link or nodal failures [
17].
The
percolation
limit or percolation threshold (
ρ
c
) returns the critical fraction of nodes that need to be removed before the network disintegrates. The
degree
diversity is taken into account to calculate the percolation limit, as can be seen in [
3]. Hence, the higher degree diversity is, the higher the percolation limit is. Then, a higher
ρ
c
indicates the fraction of vertices that can be removed without disconnecting the network is higher, which means the network is more robust. The
number
of
spanning
trees (NST) counts all possible spanning trees that exist for a graph. It has been proven that the number of spanning trees can be written as a function of the unweighted Laplacian eigenvalues [
3].
The
average
two-
terminal
reliability (ATTR) delivers the probability of connectivity between a randomly chosen node pair [
18]. ATTR is one when the network is fully connected; otherwise ATTR is the number of node pairs in every connected component divided by the total number of node pairs in the network. ATTR also gives the fraction of node pairs that are connected to each other [
19]. At failure scenarios, the higher the average two-terminal reliability is, the higher the robustness is.
The last structural metric is
viral
conductance (VC), where the robustness is measured with respect to virus spread [
20]. This metric is measured by considering the area under the curve that provides the fraction of infected nodes in steady-state for a range of epidemic intensities. The lower the VC in a network, the more robust, with respect to virus spread, it is. However, as this work is focused on random failures and targeted attacks, the VC metric is not evaluated.
2.2 Centrality Metrics
This group of metrics attempts to identify which elements in a network are the most important or central [
4]. Consequently, they could help disseminate information in the network faster, stopping epidemics, and protecting the network from breaking. These metrics also define the network centralization as a measure of how central the most central node is in relation to how central all the other nodes are [
21]. Centralization, which is a key characteristic of a network, can be used to measure network robustness as the differences between the centrality of the most central node and that of all others [
21]. In general, the most central network is the most robust i.e. if the network has more nodes with similar centrality values, there are then several spots to attack when centrality metrics are used to select the elements to be removed.
A wide number of centrality metrics has been proposed to identify the most central nodes in networks. However, the following are the most common: degree
centrality, eigenvector
centrality, closeness
centrality, betweenness
centrality and spreaders. In degree and eigenvector centralities the importance of a node is given in terms of its neighbors, whereas in closeness and betweenness centralities the importance is related to the path lengths.
Degree
centrality (
d
c
) is the simplest measure of nodal centrality, and is determined by the number of neighbors connected to a node [
22]. The larger the degree, the more important the node is. However, if a node with a high nodal degree fails, potentially higher numbers of connections are also prone to being affected. In many real networks only a small number of nodes have high degrees. Accordingly,
eigenvalue
centrality (
e
c
) is based on the notion that a node should be viewed as important if it is linked to other important nodes [
22]. The
e
c
is proportional to the sum of the centrality scores of its neighbors, where the centrality corresponds to the largest eigenvector of the adjacency matrix. Thus,
e
c
can take a large value either by the node being connected to many other nodes or by it being connected to a small number of important nodes.
With
closeness
centrality (
c
c
) the nodal importance is measured by how close a node is to other nodes [
22]. It is based on the length of the shortest path between a given node and all other nodes in the network. An important node is typically close to the other node if it can reach the whole network more quickly than non-close nodes.
Betweenness
centrality (
b
c
) is when the number of shortest paths that pass through a given node is counted [
22]. A node may have a high betweenness centrality while being connected to only a small number of other vertices (not necessarily important/central). This is due to the fact that nodes that act as bridges between groups of other nodes typically have high
b
c
. Thus, nodes with high
b
c
play a broker role in the network and are important in communication and information diffusion [
22]. Similar to
b
c
, the
link
betweenness
centrality (
l
c
) can be also calculated as the degree to which a link makes other connections possible.
Centrality metrics also take into account measures in epidemic scenarios where the best spreaders of an epidemic do not correspond to the most central nodes. Instead, the most efficient spreaders are those located within the core of the network according to a
k-shell decomposition analysis [
23]. This metric is not evaluated in this work as it is focused on random and targeted attacks.
2.3 Functional Metrics
This set of metrics quantifies the variation of the performance of a network in response to multiple failures by focusing on the Quality of Service (QoS) parameters of the established connections.
Elasticity (
E), the
quantitative
robustness
metric (QNRM) and the
qualitative
robustness
metric (QLRM) measure the robustness based on a single QoS parameter such as the throughput, the number of blocked connections or the established connections as a function of
\(\langle l\rangle\), respectively, [
6,
24]. The higher these metric values are, the more robust the network is. Using the
R-
value, the network robustness is given by an arbitrary topological vector and a weight vector. The topological vector components take into consideration one or more QoS parameters, network properties or any other structural robustness metric e.g. hop-count, average shortest path length
\((\langle l\rangle )\), maximum nodal degree (
k
max
) or algebraic connectivity (
λ
2). The weight vector components reflect the importance of the topological vector for network service. The higher the
R-
value, the greater the robustness is [
25].
Endurance (ξ) is also calculated by one or more QoS parameters (e.g. delay) or topological metrics (e.g. size of the largest connected component). In contrast to the
R-
value, ξ places greater importance on perturbations affecting low percentages of elements in a network. ξ is normalized to the interval [0, 1], where ξ = 1 denotes the non-existence of robustness, whereas ξ = 0 is correlated to the maximum possible degree of robustness [
26]. The last functional metric is
R*-
value which is the
R-
value computed via a normalized eigenvector or principal component (PC). The PC gives dimension and non-arbitrary weights to each of the robustness metrics. Without failures the
R*-
value is set to one and can take values in the interval [0, +∞) when failures are considered [
27]. A graphical representation of the
R*-
value is called the robustness surface (
Ω), and enables a visual assessment of network robustness variability [
27] to be made.