# Structural Robustness of Complex Networks:
A Survey of A Posteriori Measures

Yang Lou, Lin Wang, and Guanrong Chen Yang Lou is with the Graduate School of
Information Science and Technology, Osaka University, Suita, Osaka 565-0871,
Japan, and also with the Department of Computer Science, National Yang Ming
Chiao Tung University, Hsinchu 300, Taiwan (e-mail: felix.lou@ieee.org).Lin
Wang is with the Department of Automation, Shanghai Jiao Tong University,
Shanghai 200240, China, and also with the Key Laboratory of System Control and
Information Processing, Ministry of Education, Shanghai 200240, China (e-mail:
wanglin@sjtu.edu.cn).Guanrong Chen is with the Department of Electrical
Engineering, City University of Hong Kong, Hong Kong, China
(e-mail:eegchen@cityu.edu.hk).This research was supported in parts by the
National Natural Science Foundation of China (Nos. 62002249, 61873167), the
Foundation of Key Laboratory of System Control and Information Processing,
Ministry of Education, China (No. Scip202103), and the Hong Kong Shun Hing
Education and Charity Fund (No. 1886992).Citation: Y. Lou, L. Wang, and G.
Chen, “Structural Robustness of Complex Networks: A Survey of A Posteriori
Measures,” IEEE Circuits and Systems Magazine, Volume 23, Issue 1;
doi:10.1109/MCAS.2023.3236659 (2023)  (Corresponding author: Lin Wang)

###### Abstract

Network robustness is critical for various industrial and social networks
against malicious attacks, which has various meanings in different research
contexts and here it refers to the ability of a network to sustain its
functionality when a fraction of the network fail to work due to attacks. The
rapid development of complex networks research indicates special interest and
great concern about the network robustness, which is essential for further
analyzing and optimizing network structures towards engineering applications.
This comprehensive survey distills the important findings and developments of
network robustness research, focusing on the a posteriori structural
robustness measures for single-layer static networks. Specifically, the a
posteriori robustness measures are reviewed from four perspectives: 1) network
functionality, including connectivity, controllability and communication
ability, as well as their extensions; 2) malicious attacks, including
conventional and computation-based attack strategies; 3) robustness estimation
methods using either analytical approximation or machine learning-based
prediction; 4) network robustness optimization. Based on the existing
measures, a practical threshold of network destruction is introduced, with the
suggestion that network robustness should be measured only before reaching the
threshold of destruction. Then, a posteriori and a priori measures are
compared experimentally, revealing the advantages of the a posteriori
measures. Finally, prospective research directions with respect to a
posteriori robustness measures are recommended.

###### Index Terms:

Complex network, malicious attack, functionality robustness, robustness
measure, optimization

##  I Introduction

Network robustness has various meanings in different scenarios for different
concerns. In this article, it refers to the ability of a network to sustain
its normal functionality when a fraction of the network fail to work due to
attacks. Today, malicious attacks widely exist in many engineering and
technological facilities and processes, which degrade or even destroy certain
network functions, typically through destructing the network structural
connectivity thereby disabling the network to continue its functioning. It is
therefore crucial to strengthen the network robustness against such attacks
and failures[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]. The study of network
robustness generally includes measuring and evaluation, attacking and
defending, as well as topological optimization[12, 13, 14]. The concerned
damage caused by attacks and failures is typically the degeneration or
destruction of network functions, such as connectivity[15, 12, 14],
controllability[16, 17, 18], data transmission and communication abilities[19,
20], and so on. Among these functions, network connectivity is fundamental and
essential to support other functions, although good connectivity does not
necessarily guarantee good performance of a certain function on the network.
In this regard, the subject of network connectivity, controllability, and
communication robustness is of fundamental and practical importance, which has
been extensively investigated with applications to, for example, the fields of
nervous systems[21], wireless sensor networks[22], power grids[23], and
transportation networks[24, 25], among many others. This survey article
focuses on measuring the network structural robustness with respect to network
functions, in particular the network connectivity, controllability and
communication ability against destructive attacks. This survey only discusses
the robustness of single-layer networks with static connections, since the
structural robustness is not the main issue for networks with dynamic and
temporal connections.

Measuring is the first step in analyzing and optimizing the network
robustness. There are quite many network robustness measures. In this paper,
robustness measures are categorized into two classes according to whether
attack simulations are needed for the measurement, namely, the a priori
measures that do not require attack simulations and the a posteriori measures
that require so.

A priori measures are generally quantified by certain indicative network
features that can be calculated without performing attack simulations,
including: 1) topological measures, e.g., binary connectivity[26],
efficiency[27], betweenness centrality[28], and clustering coefficient[29]; 2)
adjacency matrix-based spectral measures, e.g., spectral radius[30], spectral
gap[31], natural connectivity[32]; and 3) Laplacian matrix-based spectral
measures, e.g., algebraic connectivity[33], effective resistance[34], and the
number of spanning trees[35]. A priori measures require only one-time
calculation and usually have lower time and computational complexities
comparing to a posteriori measures[14, 13].

A posteriori measures, on the other hand, are quantified by the sequence of
values that record the concerned functionality of the remaining network after
a sequence of node- or edge-attacks, typically removal attacks. The ratios of
largest connected components (LCC)[15], driver nodes (DN)[16, 17] and
communicable node pairs (CNP)[19, 20] are the most widely-used measures for
the connectivity, controllability, and communication ability, respectively. In
turn, the robustness of connectivity, controllability, and communication
ability is quantified by a sequence of values that record the corresponding
remaining measures after a sequence of node- or edge-attacks, respectively. A
network is considered to be more robust if it can maintain higher values of
the fractions of nodes in LCC and CNP, but lower fractions of DN, throughout
the attack process.

Figure 1: General framework for a priori and a posteriori measures of network
robustness. A priori measures perform one-time calculations to evaluate the
network robustness, where PM represents an a priori measure; while a
posteriori measures require an iterative process to gain the robustness.

A priori measures are easy-to-access and predictive; while a posteriori
measures are iteratively calculated after each of the sequence of (simulated)
attacks, which are usually time-consuming especially for large-scale networks.
However, the predictive a priori measures have limited scopes of
applications[36]. Moreover, the a posteriori measures are effective when the
attack process is terminated by a specific criterion, whereas the a priori
measures do not consider the stopping criteria. Therefore, the time-consuming
but precise a posteriori measures remain to be the main approach for real-
world applications today.

The general framework of a priori and a posteriori measures is shown in Fig.
1, which shows that a priori measures evaluate the network robustness in a
straightforward one-time process; while a posteriori measures require an
iterative process until the stopping criterion is met. It is clear that a
posteriori measures could have different options on the configuration of
stopping criteria and attack strategies, while this is invalid for a priori
measures.

With desirable robustness measure(s) chosen and used as the objective(s) to
optimize, network robustness can be enhanced by model design[37, 38, 39, 40,
41], edge addition[42, 14], or edge rewiring[43, 44, 45, 46, 47, 13, 48, 49,
50]. In so doing, whether or not a modification of the network structure can
enhance the robustness has to be evaluated, usually by using a posteriori
robustness measures that usually requires attack simulations.

Other than attack simulations, network robustness can also be estimated using
both analytical and computational methods without iterative calculation.
Analytical approximations are applicable when the a prior knowledge of the
concerned network is available and the attack strategy can be well modeled[51,
52, 53], e.g., random attacks. In contrast, computational methods are
generally data-driven and thus applicable to any attack methods with or
without a specific pattern[54, 55, 56].

In the literature, some general survey papers emphasizing more on a priori
measures of network robustness are available[14, 12], but there does not seem
to be any that specifically emphasizes on the a posteriori measures. To fill
the gap, this article presents a survey of the a posteriori measures of
network robustness, including definitions, computation, applications, and
optimization. The main contributions of this survey are summarized as follows:

  * 1)

The a posteriori robustness measures are summarized and compared, from the
perspectives of network functionality, attack strategies, robustness
performance prediction, and structural optimization.

  * 2)

A threshold of network destruction is proposed, which suggests a more
practical robustness measure of the functionality, especially when a network
has been severely destructed.

  * 3)

Both a posteriori and a priori robustness measures are experimentally compared
on a series of directed and undirected network examples. It is found from
simulations that a posteriori measures have broader applicability.

  * 4)

Some possible future research directions with respect to network robustness
are suggested.

The remainder of this article is organized as follows. Section II reviews the
a posteriori measures of network robustness, from the perspectives of network
functionality, malicious attacks, robustness performance prediction, and
optimization. Section III introduces a threshold of network destruction.
Section IV experimentally compares a posteriori and a priori measures. Section
V presents some prospective research directions with respect to a posteriori
robustness measures of complex networks. Section VI concludes the survey.

##  II A Posteriori Measures for Network Robustness

Network robustness can be defined differently with different practical
meanings in graph theory, control systems, communication networks, biological
structures, transportation frameworks, etc.[57, 58, 59, 60, 61, 62]. On the
one hand, it is possible to consider different robustness measures for the
same network. On the other hand, the same measure might be applied to
different scenarios, for example to both power grids[63] and food webs[64],
where the main concern is the remaining largest connected components after
suffering attacks, and the attacks can be physical or cyber destruction to
power stations in power grids or extinction of species in food webs.

Here, the focus is on the ability of a network to sustain its specific
function(s) when a fraction of the network fail to work due to attacks. Random
failures and malicious attacks[65] occur on nodes or edges, or both, in the
form of removal or malfunctioning, under different conditions. In
implementation, the consequence of attacking a node could be either removal or
malfunctioning (without removal), while that of attacking an edge is only edge
removal in typical cases. When a node is attacked and removed, all of its
connected edges will also be removed; while under edge-attacks, no nodes will
be removed.

The remainder of this section is organized as follows. Subsection II-A reviews
the a posteriori robustness measures from three commonly concerned network
functions: connectivity, controllability, and communication ability. Some
extensions of these measures will be discussed in Subsection II-B. Various
attack strategies and robustness estimation methods are reviewed in Subsection
II-C and Subsection II-D, respectively. Finally, Subsection II-E presents some
robustness optimization technicians based on a posteriori measures.

###  II-A Network Functions

A posteriori measures iteratively calculate specifically concerned network
function(s) after each occurrence of attacks. The general form of a posteriori
robustness measures is as follows:

$R=\frac{1}{K}\sum_{i=1}^{K}{w_{i}\cdot f(i)}\,,$ (1)

where $f(i)$ represents the residual functionality of the remaining network
after a number (or proportion) of $i$ objects (either nodes or edges) have
been attacked; $K$ represents the total number of attacks; $w_{i}$ represents
the weight of $f(i)$ in calculating $R$. When different network functions are
concerned, such as the connectivity, controllability or communication ability,
to be discussed below, $f(\cdot)$ will be specified accordingly. The weighting
parameter $w$ is usually considered as a parameter for normalization, such
that the robustness performances of different-sized networks can be compared.
However, these weights also shift the importance of the attacks in the attack
sequence, which is often overlooked.

Figure 2: [color online] Widely-used a priori and a posteriori robustness
measures of the three network functions.

Figure 2 shows the widely-used a priori and a posteriori robustness measures
of the three network functions. The details of a posteriori measures are
summarized in the following.

####  II-A1 Connectivity Robustness

The connectivity of an undirected network means that there is at least one
path between any pair of nodes. For a directed network, it is strongly
connected if there is at least one directed path from any node to an other
node, while it is weakly connected if its underlying undirected network is
connected.

LCC is the most commonly-used a posteriori measure for connectivity
robustness. Under a sequence of node-malfunctioning failures or removals, the
connectivity robustness is evaluated by calculating the remaining LCC after
each attack[15], formulated as follows:

$R_{1}=\frac{1}{N}\sum_{i=0}^{N-1}{n_{L}(i)}=\frac{1}{N}\sum_{i=0}^{N-1}{\frac{N_{L}(i)}{N}}\,,$
(2)

where $n_{L}(i)$ and $N_{L}(i)$ represent the proportion and the number of
nodes in the remaining LCC after a total number of $i$ nodes have been
attacked. Specifically, $f(i)=N_{L}(i)$ measures the remaining connectivity
and $w_{i}=1/N$ is the uniform weight, assuming that the malfunctioned nodes
are still counted as a part of the $N$-node networks.

In contrast, if the attacked nodes are removed from the network, its
connectivity robustness is calculated by

$R_{2}=\frac{1}{N}\sum_{i=0}^{N-1}{\frac{N_{L}(i)}{N-i}}\,,$ (3)

where $w_{i}=1/(N-i)$ means that the $i$th attacked nodes have been removed
from the network. Compared to Eq. (2), $w_{i}=1/(N-i)$ assigns higher weights
to the later attack stages as $i$ increases. Different weighting parameters
$w_{i}$ also change the range of robustness measure, where $R_{1}\in[0,0.5]$
but $R_{2}\in[0,1]$.

The measure shown in Eq. (2) for network robustness under node-attacks can be
extended to edge-attacks[44], as follows:

$R_{1}^{e}=\frac{1}{M+1}\sum_{i=0}^{M}{n^{e}_{L}(i)}=\frac{1}{M+1}\sum_{i=0}^{M}{\frac{N^{e}_{L}(i)}{N}}\,,$
(4)

with the superscript $e$ indicating edge-attacks, where the denominator
remains $N$ under the assumption that the number of nodes is unchanged during
edge-attacks.

When the values $n_{L}(i)$ or $n^{e}_{L}(i)$ are plotted, a curve is obtained,
which is called the connectivity curve. A higher $R_{1}$, $R_{2}$, or
$R^{e}_{1}$ value indicates an overall better connectivity robustness against
attacks.

####  II-A2 Controllability Robustness

Controllability robustness reflects how well a networked system is in
maintaining its controllable state. Consider a general linear time-invariant
(LTI) networked system, $\dot{{\bf x}}={\bf A}{\bf x}+{\bf B}{\bf u}$, where
${\bf{x}}\in\mathbb{R}^{N}$ and ${\bf{u}}\in\mathbb{R}^{b}$ are the state
vector and control input, respectively, and ${\bf A}\in\mathbb{R}^{N\times N}$
and ${\bf B}\in\mathbb{R}^{N\times b}$ are constant matrices of compatible
dimensions. Conceptually, this LTI system is state controllable if and only if
there exists a control input $\bf{u}$ that can drive the system state $\bf{x}$
from any initial state to any target state in the state space within finite
time. A commonly-used criterion is that the LTI system is state controllable
if and only if the controllability matrix ${\bf C}=[{\bf B}\ {\bf AB}\ {\bf
A}^{2}{\bf B}\ \cdots{\bf A}^{N-1}{\bf B}]$ has a full row-rank[66]. The
concept of structural controllability is a slight generalization of the state
controllability, to deal with two parameterized matrices ${\bf A}$ and ${\bf
B}$, in which the parameters characterize the structure of the underlying
system in the sense that if there are specific parameter values ensuring the
system to be state controllable then the system is structurally controllable.

When considering a network of many LTI systems, the node system with control
input is called a driver node (DN). Network controllability is investigated
from two aspects: 1) to gain the full control of the entire dynamical system,
one aims to determine how many and which nodes to control[16, 17]; 2) for each
single node, the aim is to determine the dimension of its controllable
subspace[67, 68].

Define the density of DNs by $n_{D}=\frac{N_{D}}{N}$, where $N_{D}$ is the
minimum number of DNs needed to retain a full control of the network, which
can be calculated using either the minimum inputs theorem (MIT)[16] for
directed networks or the exact controllability theorem (ECT)[17] for both
directed and undirected networks, defined as follows:

$N_{D}=\begin{cases}\text{max}\\{1,N-|E^{*}|\\},&\text{using
MIT\cite[cite]{[\@@bibref{}{Liu2011N}{}{}]}},\\\
\text{max}\\{1,N-\text{rank}(A)\\},&\text{using
ECT\cite[cite]{[\@@bibref{}{Yuan2013NC}{}{}]}},\\\ \end{cases}$ (5)

where $|E^{*}|$ represents the number of edges in the maximum matching
$E^{*}$, which is a basic concept in classical graph theory[16]. Under node-
attacks, the controllability robustness is measured by

$R_{3}=\frac{1}{N}\sum_{i=0}^{N-1}{n_{D}(i)}=\frac{1}{N}\sum_{i=0}^{N-1}{\frac{N_{D}(i)}{N^{\prime}}}\,,$
(6)

where $n_{D}(i)$ and $N_{D}(i)$ represent the density and number of DNs needed
to retain the network controllability after a total of $i$ nodes have been
attacked; $N^{\prime}$ can be set to either $N^{\prime}=N-i$ or
$N^{\prime}=N$, depending on specific preference, namely whether or not an
attacked node still belongs to the network depends on the situation under
consideration. Usually, attacked nodes are assumed to be malfunctioned (but
still in the system) in connectivity robustness measures, but will be removed
from the network in controllability robustness measures.

Similarly, controllability robustness under edge-attacks is measured by

$R^{e}_{3}=\frac{1}{M+1}\sum_{i=0}^{M}{n^{e}_{D}(i)}=\frac{1}{M+1}\sum_{i=0}^{M}{\frac{N^{e}_{D}(i)}{N}}\,,$
(7)

where $M$ is the number of edges in the network. When the values $n_{D}(i)$ or
$n^{e}_{D}(i)$ are plotted, a curve is obtained, which is called the
controllability curve. A lower $R_{3}$ or $R^{e}_{3}$ value represents a more
robust controllability against attacks.

Different from considering the density of DNs, the control centrality measures
the control ability of a single node in a directed network[68], defined by
$c^{(j)}_{c}=C^{(j)}_{c}/N$, where $C^{(j)}_{c}=\text{rank}_{g}({\bf
C}^{(j)})$ is the generic dimension of the controllable subspace of node $j$
that can be calculated according to the Hosoe theorem[67]; ${\bf C}$
represents the controllability matrix. Under this measure, the greater the
$c^{(j)}_{c}$ value is, the more “powerful” the node $j$ is as a DN.

The expected robust control centrality (ERCC)[69, 70] is a control centrality-
based robustness measure for node-attacks, defined as follows:

$R_{4}^{(j)}(i)=E[C_{c}^{(j)}(i)]\,,$ (8)

where $C_{c}^{(j)}(i)$ represents the control centrality of node $j$ after a
total number of $i$ nodes have been attacked; $E[\cdot]$ is the statistical
expectation. The generic robust control centrality (GRCC)[69, 70] is a
generalization of ERCC, defined as follows:

$R_{4}^{e,(j)}(\\{e\\})=E[C_{c}^{(j)}(\\{e\\})]\,,$ (9)

where $C_{c}^{(j)}(\\{e\\})$ represents the control centrality of node $j$
after a set of edges $\\{e\\}$ have been removed, under either node- or edge-
attacks. Both ERCC and GRCC measure the significance of a single node in
controlling part of the system, under random node- and edge-attacks,
respectively.

The reachability-based controllability robustness[71, 52] is also a control
centrality-based robustness measure. Given a fixed number of $H$ controllers
that can be pinned anywhere (“free control” mode), the controllability
robustness is calculated by

$R_{5}=\frac{1}{N}\sum_{i=0}^{N-1}{\sum_{j=1}^{H}}{\frac{c_{c}(j)}{N^{\prime}}}\,,$
(10)

where $\sum_{j=1}^{H}{c_{c}(j)}$ represents the dimension of the controllable
subspace by the given $H$ DNs. During the attack, these DNs can be freely set
in the remaining network, as long as the control centrality is maximized.
Again, $N^{\prime}=N-i$ or $N$, depending on the specific situation under
consideration.

In the case that the given external controllers are fixedly pinned at a set of
given nodes (“fixed control” mode)[52], the controllability robustness is also
measured using Eq. (10), where however $\sum_{j=1}^{H}{c_{c}(j)}$ counts the
dimension of the controllable subspace by the given $H$ fixed controllers.

####  II-A3 Communication Robustness

Different from the a priori measures of general connectivity robustness, which
are either spectral measures or topological features, the a priori measures of
communication robustness are more comprehensive. For example, the
$r$-robustness[72, 73, 74] based on reachability, and the comprehensive
measure proposed in[75] consisting of three indices, including edge
betweenness centrality, number of edge cut-sets, and node Wiener impact[76].
Nevertheless, the a posteriori measures for connectivity robustness remain
useful for measuring communication robustness[77].

The CNP-based robustness measure is a widely-used a posteriori measure for
communication robustness, defined as follows[19]:

$R_{6}=\frac{1}{N}\sum_{i=0}^{N-1}{\sum_{j=1}^{\Gamma(i)}}{\frac{{S_{j}\choose
2}}{{N\choose 2}}}\,,$ (11)

where $\Gamma(i)$ represents the number of connected components in the
remaining network after a total of $i$ nodes have been attacked; $S_{j}$
represents the number of nodes in the $j$th connected component;
${S_{j}\choose 2}$ represents the number of communicable node pairs, while
${N\choose 2}$ is the number of all possible node pairs. When ${S_{j}\choose
2}={N\choose 2}$, the network is fully connected, thus each pair of nodes are
communicable; while for the networks that are not fully connected, the number
of communicable node pairs should be less than the all possible node pairs,
namely ${S_{j}\choose 2}<{N\choose 2}$.

The following simplified communication robustness[20] provides a simpler CNP-
based measure:

$R_{7}=\frac{1}{N}\sum_{i=0}^{N-1}{\sum_{j=1}^{\Gamma(i)}}{\frac{{S_{j}^{2}}}{{N^{2}}}}\,,$
(12)

which ignores the non-dominant terms in Eq. (11) but keeps only the dominant
ones. The computation complexities of both measures are the same, $O(NM)$.

When the CNP values are plotted, a curve is obtained, which is called the
communication curve. Apparently, higher values of $R_{6}$ or $R_{7}$ represent
better communication robustness against attacks.

###  II-B Variants of Robustness Measures

Based on the fundamental a posteriori robustness measures presented in
Subsection II-A, several variants have been developed with different concerns.

####  II-B1 Rank-based Measure

Before being attacked, the initial proportions of LCC for all connected
networks are the same, namely $n_{L}(0)=1$. In contrast, the initially
required proportion of DNs to fully control a network varies from case to
case. This inequality of initial controllability may influence the measurement
of robustness.The rank-based controllability measure offers an alternative to
diminish this influence, which is defined by

$R_{8}=\frac{1}{N}\sum_{i=0}^{N-1}{r_{D}(i)}\,,$ (13)

where $r_{D}(i)$ is the rank of the controllability matrix after a total of
$i$ nodes have been attacked. Lower ranks are assigned to the networks that
possess better controllability.

Figure 3 shows an illustrative example, where net1 requires a larger initial
proportion of DNs than net2. The controllability curve of net1 is flatter than
that of net2. Under two different measures, $R_{3}$ returns that net2 has
better controllability robustness than net1, but $R_{8}$ returns that they
have same performance. Clearly, $R_{8}$ diminishes the influence of the
initial states.

Figure 3: [color online] Example of two different controllability robustness
measures. $R_{3}$ and $R_{8}$ are calculated using Eqs. (6) and (13),
respectively.

####  II-B2 Combinatorial Measure

Although connectivity robustness has a certain positive correlation with
controllability robustness and communication robustness, they actually have
very different measures and objectives. In general, good connectivity is the
prerequisite for good controllability and communication ability, but the
former does not guarantee the latter in general.

Considering connectivity robustness and controllability robustness together,
adjustment is necessary since better robustness means maximization Eq. (2) but
minimization Eq. (6). To unify them (e.g., both being maximization), a
combinatorial measure can be defined using either the opposite of
$n_{D}(i)$[78], as follows:

$R_{9}=\frac{1}{N}\sum_{i=0}^{N-1}(1-n_{D}(i))\,,$ (14)

or the reciprocal of $n_{D}(i)$[79], as follows:

$R_{10}=\frac{1}{N}\sum_{i=0}^{N-1}\frac{n_{L}(i)}{n_{D}(i)}\,.$ (15)

Maximizing $R_{9}$ is equivalent to minimizing $R_{3}$, while maximizing
$R_{10}$ is equivalent to either maximizing $R_{1}$, or minimizing $R_{3}$, or
maximizing $R_{1}$ and minimizing $R_{3}$ together.

####  II-B3 Averaged Measure

All the above-mentioned a posteriori robustness measures, except for ERCC and
GRCC[69, 70], are calculated based on a specific attack sequence, namely, each
robustness value is one-to-one corresponding to a specific attack sequence. If
network robustness is required to be measured by a number of repeated
simulations, or several different attack sequences are required to be
considered, then the averaged robustness measure can be applied, which is
defined as follows:

$R_{11}=\frac{1}{P\cdot Q}\sum_{p=1}^{P}\sum_{q=1}^{Q}R_{p,q}\,,$ (16)

where $R_{p,q}$ represents the network robustness measured under the $p$-th
repeated simulation using the $q$-th attack strategy; $P$ is the number of
repeated attack simulations; $Q$ is the number of different attack strategies.
After averaging, a robustness value will not be corresponding to a specific
attack strategy or sequence.

####  II-B4 Other Measures

When cascading failure-based attacks are considered, the robustness measure
can be slightly modified, as follows:

$R_{12}=\frac{1}{N}\sum_{h=1}^{H}f(h)\,,$ (17)

where $H$ is the required number of attacks to achieve the attack task, for
example, a significant destruction of functionality[80, 81, 82, 83, 84]. Here,
$H\leq N$ implies that it is not always necessary to attack all nodes in order
to destroy the network functions.

When the community structure is concerned, the community robustness can also
be calculated using Eq. (1), where $f(i)$ could be either the community
integrity that counts the number of remaining nodes in the community[85], or
the normalized mutual information[86].

It is noted that this survey paper focuses on reviewing the robustness
measures of the networks with static connection, whereas the networks with
dynamic and temporal connections are not discussed. This is because the
robustness measures of dynamic and temporal networks have very different
characteristics and applications. For example, the robustness of a temporal
network is measured by calculating the relative loss of efficiency caused by
attacks[87], as follows:

$R_{13}=1-\frac{\Delta{\epsilon}}{\epsilon_{0}}\,,$ (18)

where $\epsilon_{0}$ represents the global efficiency of the temporal network
within a given time window, and $\Delta{\epsilon}$ represents the efficiency
loss caused by attacks. Although it may be regarded as an a posteriori
measure, it has a different form from Eq. (1) that performs iterative attack-
and-evaluation operations.

###  II-C Attack Strategies

From the attacker’s perspective, searching for the most destructive attacking
sequence is a desirable task, which can also help the defender in considering
how to design a best possible network topology with the strongest robustness.
Therefore, attack strategy is also a focal topic in the study of network
robustness.

For a given network, a priori measures return a single deterministic value
about the network robustness, which will not change when different attack
strategies or different numbers (rounds) of attacks are applied. In contrast,
a posteriori measures are able to reflect different robustness performances
when attack strategies (or attack sequences) vary. The issue of network
robustness within different contexts has been extensively investigated, with
many edge- and node-attack strategies proposed to destruct the network
functions, regarding the connectivity, controllability, communication ability,
and so on.

Random attacks remove or malfunction randomly-selected objects (nodes or
edges), while targeted attacks aim at attacking deliberately-selected objects,
for example, the highest-degree node or the largest-betweenness edge. Given an
importance measure $g$ for either nodes or edges, targeted attacks perform
sequential attacks to object $j$, with $\operatorname*{arg\,max}g$, meaning
that object $j$ is the most important according to measure $g$.

####  II-C1 Degree- and Betweenness-based Attack Strategies

For targeted attacks, it is assumed that the targeted object is more important
than the others in maintaining the network functionality. The most frequently-
used measures of importance are the degree centrality and betweenness
centrality, for both nodes and edges. In fact, the maximum degree-based
targeted attack (MDTA) and maximum betweenness-based targeted attack (MBTA)
are the most widely-used strategies.

To integrate multiple importance measures into one, weights and probabilities
may be considered:

$p_{j}=\sum_{i}\alpha_{i}\times\frac{g_{i,j}}{\sum_{j=1}^{K}{g_{i,j}}}\,,$
(19)

where $p_{j}$ is the probability of attacking object $j$; $\alpha_{i}$ is the
weight for importance measure $g_{i}$; $g_{i,j}$ is the importance measure
$g_{i}$ for object $j$. For example,
$p_{j}=\alpha_{1}\times\frac{k_{j}}{\sum_{j=1}^{K}{k_{j}}}+\alpha_{2}\times\frac{b_{j}}{\sum_{j=1}^{K}{b_{j}}}$
represents a combination of degree and betweenness, where $k_{j}$ and $b_{j}$
are the degree and the betweenness of node $j$; weights $\alpha_{1}$ and
$\alpha_{2}$ adjust the distributions of different features, which can be set
manually[88], or with $\alpha_{2}$ being replaced by $1-\alpha_{1}$[89].

Similarly, three parameters can be used[90] to control the weights of degree,
betweenness and harmonic closeness, respectively. Attacking the highest-
betweenness node inside the LCC makes MBTA more destructive in the later
stages of the attack process[91]. These measures have also been used in some
strategies to attack interdependent networks[92, 93, 89, 94, 90], networks of
networks[95, 96], and weighted networks[97].

Both MDTA and MBTA are not only destructive to connectivity robustness, but
also effectively degrade other network functions such as controllability and
communication ability[80, 81, 98, 19].

####  II-C2 Topology-based Attack Strategies

Beside degree and betweenness, commonly-used measures of importance include
closeness[99], Katz centrality[100], neighborhood similarity[101], branch
weighting[102], structural holes[103], and so on. However, ranking the
importance of nodes or edges is practically intractable for large-scale
networks, since most measures cannot guarantee that removing the targeted
object will globally and consistently cause the greatest damage to the
network.

The hierarchical structure of a directed network enables the random upstream
(or downstream) attack to the network controllability, which results in a more
destructive attack strategy than random attacks[68]. The module-based attack
strategy[104, 105] aims at attacking the nodes with inter-community edges that
are crucial to maintain the connectivity among communities. Practically, the
removal costs for different nodes are not the same, so attack strategies could
also be designed to minimize the total costs[106].

Given an $N$-node network, which is subject to node-attacks, there are $N!$
possible attack sequences in total. Thus, it is quite possible to have
different or even opposite conclusions for network robustness depending on
some topological issues. For example, it is observed that homogeneous networks
are more robust than heterogeneous networks against random attacks, MDTA, and
MBTA[107]. Also, when the attack strategy aims at removing the three-level
tree structures (including random, maximum- and minimum-degree nodes)[108],
homogeneous networks are more robust than heterogeneous networks. However, if
one aims at removing approximately the longest simple path from a network,
then homogeneous networks are more vulnerable than heterogeneous
networks[109]. Moreover, for networks with special topological features, the
efficiencies of different attack strategies are also different; for example,
MDTA causes greater damages to local-world networks[110] with larger local-
world sizes, while networks with smaller local-world sizes show better
robustness regarding both connectivity and controllability[111].

####  II-C3 Damage-based Attack Strategies

The concept of “damage”[112] in network connectivity helps to evaluate and
guide attacks. The damage of a specific node is quantified by the change of
the LCC size, before and after attacking the node. Therefore, it is natural
that an efficient greedy attack strategy can be formed by sequentially
attacking the node whose removal or malfunctioning will cause the greatest
damage to the network[112]. With damage as the importance measure, the most
destructive node-removal sequence can be searched by solving a combinatorial
optimization problem, using genetic algorithm[113], memetic algorithm[114], or
other advanced optimization tools.

Different from the damage of connectivity, the damage of controllability is
defined based on the categorization of edges or nodes. An edge or node is
critical if and only if its removal increases the number of needed DNs;
otherwise, it is non-critical[16, 51, 115]. The damage of controllability
helps to form effective attack strategies, where critical edges or nodes will
be removed with the highest priority[51, 115].

Damage-based attack strategies are intuitive and the maximal destruction is
guaranteed for every single attack. However, they have two clear
disadvantages: 1) the maximal destruction of a series of continuous attacks
cannot be guaranteed; 2) the computational cost of calculating the damage is
not negligible.

####  II-C4 Computational Intelligence-based Attack Strategies

Searching for a desirable attack sequence from the large number of possible
choices is an NP-hard combinatorial optimization problem[116, 117].
Evolutionary algorithms have been applied to dealing with this problem, such
as genetic algorithms[118], artificial bee colony algorithm[119], Tabu search
algorithm[120, 121], and other metaheuristic algorithms[122, 123]. Candidate
attack sequences referred to as individuals form a population, which are
evolved towards the optimal destruction of networks. Moreover, machine
learning techniques have been increasingly used to explore optimal attack
strategies on large-scale networks. Ensemble learning is employed to estimate
node importance, where node damage (see Subsection II-C3) is used for training
the model, such that nodes with higher damages can be identified, thus an
efficient attack strategy can be designed[124]. The minimal set of critical
nodes is identified using graph attention networks[125], which is then used to
effectively disintegrate a complex network[126]. Such an attack strategy can
be successful based on deep reinforcement learning[127]. A sequential attack
process can also be modeled by a Markov decision process, whereas deep
reinforcement learning[128, 129] can be used to find optimal attack
sequences[130, 131, 132]. Recently, a combination of convolutional neural
networks (CNN) and graph neural networks (GNN)[133, 134, 135] has been used
for measuring the node importance in virus spreading models[136].

The computational intelligence-based attack strategies require a non-
negligible or even substantial amount of computational cost in the stages of
robustness evaluation and model training. The difference is that evolutionary
algorithm-based strategies aim at finding the most destructive attack sequence
for the given networks, while machine learning-based strategies also pursue
the generalizability to unknown data, for which greater computational cost is
needed in the training stage.

###  II-D Robustness Performance Prediction

Evaluating a posteriori measures by attack simulations is generally very time-
consuming. In case that the exact robustness values are not required,
approximated values can be estimated by either analytical or computational
methods. In so doing, the time complexity is either constant for analytical
methods[53] or increasing significantly slower than that of attack simulations
for computational methods[54].

####  II-D1 Analytical Approximation

Analytical approximations require full knowledge of the network structure and
the applied attack strategy that can be well-modeled[51, 137], such as random
attacks. Given the network adjacency matrix, the controllability configuration
and critical edges can be found, so that the controllability curve under
random edge-attacks can be approximated based on the uniformly-random
decreasing process of critical edges[51]. This analytical method is applicable
to approximating the controllability robustness[51], as shown in Eq. (7), and
the reachability-based controllability robustness[52], as shown in Eq. (10),
under random edge-attacks.

For random-graph networks, based on the fact that the generation mechanism is
essentially the same as the random edge-removal process from a fully-connected
network in a reverse manner, a precise approximation can be designed. The
given random-graph networks are classified as either “dense”, “median”, or
“sparse”. Then, the hybrid approximation method uses different prior knowledge
to approximate the controllability curves[53]. In comparison, the approach of
[53] performs significantly better in predicting the controllability curves of
random-graph networks under random edge-attacks; while its disadvantage is
clear that it is applicable only to the above-mentioned scenario.

####  II-D2 Machine Learning-based Prediction

Machine learning algorithms, such as linear regression, random forest, and
neural networks, have been successfully applied to predicting the number of
DNs under random or targeted edge-attack, such that the controllability curves
can be fitted[138].

During the network robustness optimization processes, calculating the exact
robustness values may not be required for every generation. Therefore, fast
estimation can be used to improve the efficiency. For example, in Refs.[49,
50], three algorithms, including radial basis function[139], inverse distance
weighting[140] and least-squares[141], form a surrogate ensemble for
estimating connectivity robustness values; attack simulations are
intermittently performed for obtaining real robustness values, which are used
for simultaneously evaluation and updating the surrogates. The computational
time of optimization can be significantly reduced by using such a surrogate
ensemble[49, 50].

The CNN-based prediction approach treats complex network data as gray-scale
images[54], thereby fast approximating the robustness performance against
different attacks in an end-to-end manner. Prior knowledge is useful for pre-
processing and filtering, which is utilized to build an improved
predictor[55], showing lower prediction errors. A limitation of this
straightforward approach is that it cannot deal with the situation where the
network size is significantly different from the input size of the CNN[142].
Graph representation learning[133, 134, 135], which is specifically designed
for processing graph data, provides a solution to overcome this problem[143].
In graph representation learning, the raw complex network data ($N\times N$)
are compressed and unified to lower-dimensional representations ($W\times U$,
with $W<N$ and $U\ll N$); thus, not only the input size problem is solved but
also the topological features can be better extracted and utilized.

###  II-E Robustness Optimization

It is crucial to understand the relationship between the network structure and
its functionality robustness. Generally, dense homogeneous networks have
better robustness than spare heterogeneous ones, regarding the network
connectivity, controllability, and communication ability. However, it is also
possible that well-designed heterogeneous networks have better robustness than
homogeneous networks[38]. For general heterogeneous networks, it is known that
onion-like structures that possess higher assortativity coefficients are
robust against attacks[144, 15, 43, 145, 146]. Given suitable robustness
measure(s) as the objective(s), network robustness can be optimized using
evolutionary algorithms[147, 148].

Figure 4 shows a general flowchart of using evolutionary algorithms for
network robustness optimization. Rewiring is the most widely-used strategy to
perform disturbances onto the network structure, while in some specific
applications adding edges is more cost-effective. Constraints such as degree
preservation for all nodes guarantee some given prerequisites. After one or
several edge rewiring operations, whether the disturbance enhances the
robustness has to be evaluated by using either a priori or a posteriori
measures. Here, within the focus of this survey, only the latter is discussed.

Figure 4: Flowchart of network robustness optimization using evolutionary algorithms.  TABLE I: Summary of using heuristic algorithms to optimize network robustness. Work | Measure | Algorithm | Constraint |  | Attack
---
Object
Schneider, et al.[15] | Eq. (2) | random rewiring |  | degree preservation
---
for each node
node
Herrmann, et al.[144] | Eq. (2) | Monte Carlo-based algorithm |  | degree distribution
---
preservation
node
Buesser, et. al.[149] | Eq. (2) | simulated annealing |  | degree preservation
---
for each node
node
Zeng and Liu[44] | Eq. (2) | hybrid greedy algorithm |  | degree preservation
---
for each node
node and edge
| Peixoto and
---
Bornholdt[150]
Eq. (2) |  | BFGS[151] and
---
other swarm-based algorithms
| average degree
---
preservation
node
Cao, et al.[152] | Eq. (2) | strategies of adding edges | N/A | node
Zhou and Liu[153] | Eq. (2) | memetic algorithm |  | degree preservation
---
for each node
node
Xiao, et al.[78] | Eq. (14) | dynamic optimization |  | degree preservation
---
of each node
node
Bai, et al.[154] | Eq. (2) | hill-climbing search |  | degree preservation
---
for each node
node
Yang, et al.[155] | Eq. (2) |  | greedy bypass
---
rewiring algorithm
| preserving both the
---
degree distribution and
community structure
node
Tang, et al.[156] | Eq. (17) | memetic algorithm |  | degree preservation
---
for each node
node
Ma, et al.[157] | Eq. (2) and Eq. (4) | edge-replenishment strategy |  | keep the total numbers
---
of nodes and edges
node and edge
Sun, et al.[158] | Eq. (2) | tabu search |  | degree preservation
---
for each node
node
Tang, et al.[82] | Eq. (17) | memetic algorithm |  | degree preservation
---
for each node
node
Park and Hahn[159] | Eq. (2) |  | greedy bypass
---
rewiring algorithm
N/A | node
Wang and Liu[160] |  | 2 objectives:
---
Eq. (2) and cooperation
(fraction of cooperators)
| multi-objective
---
evolutionary algorithm
| degree preservation
---
for each node
node
Wang and Liu[161] | community integrity[85] | genetic algorithm |  | degree distribution
---
preservation
node
Wang, et al.[86] |  | normalized mutual
---
information[86]
simulated annealing |  | degree distribution
---
preservation
node
Wang and Liu[79] |  | 2 objectives:
---
Eq. (15) and cooperation
(fraction of cooperators)
| multi-objective
---
evolutionary algorithm
| degree preservation
---
for each node
node
Rong and Liu[162] | Eq. (2) | heuristic algorithm |  | degree preservation
---
for each node
node
Gunasekara, et al.[147] |  | Eq. (2) and two
---
spectral measures
| multi-objective
---
evolutionary algorithm
| N/A
---
node
Liu, et al.[163] | Eq. (2) | evolutionary algorithm | N/A | node
Liu, et al.[148] |  | Eq. (2) and Eq. (4)
---
| multi-objective
---
evolutionary algorithm
| degree preservation
---
for each node
node and edge
Qiu, et al.[22] | Eq. (2) | multi-population co-evolution |  | degree preservation
---
for each node
node
Cai, et al.[25] |  | 2 objectives:
---
1) maximize algebraic
connectivity
2) minimize the
number of removed edges
| NSGA-II, NSGA-III,
---
and MODPSO
N/A | edge
Wang, et al.[49] | Eq. (2)* |  | surrogate-assisted
---
evolutionary algorithm
| degree preservation
---
for each node
node
Wang, et al.[50] | Eq. (2)* |  | surrogate-assisted
---
multi-objective
evolutionary algorithm
| degree preservation
---
for each node
node and edge
Lou, et al.[164] | Eq. (6) |  | random edge rectification
---
| average degree
---
preservation
node and edge
Lou, et al.[48] | Eq. (6) |  | random rewiring
---
| average degree
---
preservation; and
underlying-topology
preservation
node
* with the assistance of surrogates and assortativity

Table I summarizes 29 methods on network robustness optimization. The most
common scenario of these methods is to use evolutionary algorithms to optimize
network robustness under node-attacks measured by Eq. (2), where the degree
(or both in- and out-degrees) for each node remains unchanged during the
optimization process. Extensions of this common scenario include considering
different measures, using advanced algorithms, imposing different constraints
of topology disturbances, and targeting different objects. Since a single
measure sometimes cannot fully reflect the network robustness[60, 20],
multiple robustness measures are usually considered, which are simultaneously
optimized by using multi-objective optimization algorithms[147, 148, 50].

##  III Measuring Network Destruction

It is observed that a posteriori measures not only have intuitively clear
meanings for a network function, as discussed in Subsection II-A, but also
have clearer descriptions about the network robustness, as introduced in
Section IV. One significant disadvantage of a posteriori measures, however, is
that their calculations are generally time-consuming. Nevertheless, in some
applications, this can be (partially) solved by using analytical and
computational methods, as discussed in Subsection II-D.

Here, another common shortcoming of a posteriori measures is addressed. The
calculation of most a posteriori measures is based on the entire process from
attacking the first object to ending the attack at the last object.
Practically, if a network has been severely destructed or malfunctioned,
measuring its functionality will have no meaning. Also, complete disconnection
of networks may not always be important in many applications. for example,
when cascading failures are concerned, as shown in Eq. (17), complete
disconnection is unnecessary to attempt. Therefore, it is not always necessary
to attack all nodes or edges for measuring the network robustness.

Clearly, determining when to stop attacking or whether a network is severely
destructed or malfunctioned is application-dependent. For example, the
robustness of food webs is widely measured by $R50$, which is the proportion
of species (nodes) that has to be removed to cause the extinction of $50\%$ of
the species in the food web[165, 166, 64].

Different from the Molloy–Reed criterion[167], which states that a network
will lose its giant component if $\langle k^{2}\rangle/\langle k\rangle>2$ is
reached, here a new measure of network destruction is proposed, based on the
change of the number of connected components (NCC)[168]. Specifically, for the
a posteriori measure $f(\cdot)$ that considers the network destruction, Eq.
(1) can be rewritten as

$R_{14}=\frac{1}{T+1}\sum_{i=0}^{T}{w_{i}\cdot f(i)}\,,$ (20)

where $T$ ($T<N$) is the counted number of removed objects before the
threshold of “severe destruction” is reached. Here, the threshold integer $T$
separates the attack process into two parts: before $T$ is reached, the
network is considered as normal; after $T$ is reached, the network is deemed
breakdown. Network robustness will be measured only before this threshold is
reached. In the literature about node-attacks, $T$ is set to be $0.5N$
in[127], $0.05N$ in[169], or less than $0.2N$ in[107]. All are user-defined
fixed integers.

In this paper, instead of setting $T$ to be a fixed value, the network
destruction is considered from the perspective of NCC, which changes non-
monotonically during the attack process. In general, there is a clear turning
point in the curve of NCC. For a connected network, its initial NCC is 1. The
value of NCC increases as nodes and edges are being attacked. During the
targeted attack process, the isolated nodes (generated due to attacks) will
never be removed until there are only isolated nodes left in the residual
network, since connected nodes are always targets if they exist. Therefore,
the turning point of the NCC tendency curve can be used as the indicator of
severe network destruction, namely, when this turning point appears, it means
that there are only isolated nodes left in the residual network. This
indicator of destruction is studied from a general perspective but not for a
specific application. Note that removing isolated nodes is possible in any
step of random attacks; hence, it is not suitable to use this turning point as
the indicator of destruction.

The number of DN is non-decreasing and the numbers of LCC and CNP are non-
increasing. Moreover, stagnation of DN, LCC, and CNP may occur frequently;
therefore, it is difficult if not impossible to determine the network
destruction using the changes of DN, LCC, or CNP.

Let $D(i)$ denote the NCC values after a total of $i$ nodes have been
attacked, where $D(i)\in[1,N]$ and $i\in[0,N-1]$. The turning point of $D(i)$
is calculated by

$T=\underset{i}{\operatorname*{arg\,max}}~{}{D(i)}\,.$ (21)

In attack simulations, $T$ can be determined when $D(i)<D(i-1)$ is
successively detected for $\lfloor pN\rfloor$ times. Then, $T=i-\lfloor
pN\rfloor$, where $p$ is a small decimal. It is empirically observed that the
determination of $T$ is insensitive to the change of $p$. Set $p=0.05$ in the
simulation, which means that when $D(i)<D(i-1)$ is successively detected for
$\lfloor 0.05N\rfloor$ times, one has $T=i-\lfloor 0.05N\rfloor$.

Equation (21) can also be applied to edge-attacks. Since NCC will not decrease
under edge-attacks, $T=i-\lfloor pN\rfloor$ can be determined when
$D(i)=D(i-1)$ is successively detected for $\lfloor pN\rfloor$ times.

Figures 5 and 6 show the attack simulation results under node MDTA and edge
MBTA, respectively.

Here, a total of 10 synthetic network models are simulated, including the
Erdös–Rényi (ER) random-graph[170], Newman–Watts small-world (SW-NW)[171],
Watts–Strogatz small-world (SW-WS)[29], random triangle (RT)[98], random
hexagon (RH)[172], extremely homogeneous (EH)[164], Barabási–Albert (BA)
scale-free[173, 174], generic scale-free (SF)[175], onion-like generic scale-
free (OS)[15], q-snapback (QS)[39, 176] networks. In all simulations, the
network size is set to $N=1000$ with $\langle k\rangle=10$. Four network
functions are measured, that is, controllability robustness, connectivity
robustness, communication robustness, and the number of connected components.
The resultant values are normalized, so they are all in $[0,1]$.

Figure 5: [color online] Network robustness in terms of the number of
connected components ($n_{NCC}$), controllability ($n_{D}$), connectivity
($n_{L}$), and communication ability ($n_{CM}$), together with the threshold
of destruction $T$. Here, $\delta$ represents the portion of nodes removed
from the network. Node MDTA is implemented. Figure 6: [color online][color
online] Network robustness in terms of the number of connected components
($n_{NCC}$), controllability ($n_{D}$), connectivity ($n_{L}$), and
communication ability ($n_{CM}$), together with the threshold of destruction
$T$. Here, $\delta$ represents the portion of edges removed from the network.
Edge MBTA is implemented.

As can be seen from Fig. 5, all the vertical green lines well match the
turning points of the controllability curves (blue dashed curves). In
contrast, for the connectivity and communication curves (brown and black
dashed curves), the vertical green lines appear consistently later than the
turning points of these curves. This means that, under node MDTA, Eq. (21)
suggests a good threshold for the network destruction in terms of
controllability robustness, but not for connectivity and communication
robustness. In contrast, as shown in Fig. 6, the vertical green lines match
the turning points of the connectivity and communication curves better than
the controllability curves. This implies that, under edge MBTA, Eq. (21)
suggests a good threshold for connectivity and communication robustness, but
not for the controllability robustness. This means that there is no turning
point in the controllability curve under edge MBTA; the turning point only
appears under node MDTA.

TABLE II: Comparison of robustness performance under two measure schemes: complete disconnection (CD) and threshold-based disconnection (TD). Numbers in parentheses represent the corresponding ranks of robustness.  | Node MDTA | Edge MBTA
---|---|---
| Controllability
---
Robustness
| Connectivity
---
Robustness
| Communication
---
Robustness
$T$ |  | Controllability
---
Robustness
| Connectivity
---
Robustness
| Communication
---
Robustness
$T$
ER |  | CD
---
TD
| 0.247 (2)
---
0.155 (3)
| 0.476 (3)
---
0.534 (6.5)
| 0.331 (3.5)
---
0.372 (6.5)
891 |  | 0.390 (6)
---
0.286 (4)
| 0.835 (4.5)
---
0.991 (2)
| 0.806 (4.5)
---
0.983 (2)
381
| SW-
---
NW
| CD
---
TD
| 0.248 (3)
---
0.146 (2)
| 0.474 (4)
---
0.538 (1.5)
| 0.331 (3.5)
---
0.376 (4)
881 |  | 0.361 (3)
---
0.269 (3)
| 0.834 (6.5)
---
0.985 (5)
| 0.808 (3)
---
0.971 (5)
406
| SW-
---
WS
| CD
---
TD
| 0.259 (4)
---
0.159 (4)
| 0.473 (5)
---
0.537 (3.5)
| 0.330 (5)
---
0.375 (5)
881 |  | 0.372 (4)
---
0.234 (1.5)
| 0.834 (6.5)
---
0.998 (1)
| 0.806 (4.5)
---
0.995 (1)
347
RT |  | CD
---
TD
| 0.302 (7)
---
0.190 (6)
| 0.459 (7)
---
0.533 (8)
| 0.326 (7)
---
0.378 (3)
861 |  | 0.376 (5)
---
0.302 (6)
| 0.830 (8)
---
0.964 (6)
| 0.801 (6.5)
---
0.936 (6)
426
RH |  | CD
---
TD
| 0.292 (6)
---
0.178 (5)
| 0.464 (6)
---
0.538 (1.5)
| 0.327 (6)
---
0.379 (2)
861 |  | 0.344 (2)
---
0.294 (5)
| 0.836 (2.5)
---
0.918 (8)
| 0.812 (2)
---
0.892 (8)
455
EH |  | CD
---
TD
| 0.227 (1)
---
0.132 (1)
| 0.478 (2)
---
0.536 (5)
| 0.332 (2)
---
0.372 (6.5)
891 |  | 0.327 (1)
---
0.234 (1.5)
| 0.836 (2.5)
---
0.986 (4)
| 0.813 (1)
---
0.975 (4)
411
BA |  | CD
---
TD
| 0.443 (8)
---
0.288 (8)
| 0.418 (8)
---
0.534 (6.5)
| 0.307 (8)
---
0.393 (1)
782 |  | 0.424 (7)
---
0.372 (8)
| 0.841 (1)
---
0.936 (7)
| 0.800 (8)
---
0.896 (7)
446
SF |  | CD
---
TD
| 0.783 (10)
---
0.601 (10)
| 0.205 (10)
---
0.376 (10)
| 0.149 (10)
---
0.273 (10)
545 |  | 0.632 (10)
---
0.610 (10)
| 0.778 (10)
---
0.829 (10)
| 0.669 (10)
---
0.718 (10)
465
SO |  | CD
---
TD
| 0.768 (9)
---
0.589 (9)
| 0.215 (9)
---
0.380 (9)
| 0.156 (9)
---
0.276 (9)
564 |  | 0.615 (9)
---
0.588 (9)
| 0.781 (9)
---
0.839 (9)
| 0.676 (9)
---
0.733 (9)
460
QS |  | CD
---
TD
| 0.286 (5)
---
0.207 (7)
| 0.484 (1)
---
0.537 (3.5)
| 0.333 (1)
---
0.369 (8)
901 |  | 0.448 (8)
---
0.361 (7)
| 0.835 (4.5)
---
0.989 (3)
| 0.801 (6.5)
---
0.978 (3)
381

Table II shows the comparison of robustness performance under two measure
schemes, namely the complete disconnection (CD) scheme as described by Eq. (1)
and the threshold-based disconnection (TD) scheme as described by Eq. (20). In
the table, the numbers in parentheses represent the corresponding ranks of
robustness. It is clear that, under different schemes, the robustness
performance can be measured very differently. The TD robustness measures are
recommended (or even necessary) to use for the following reasons: 1) the
resultant ranks are unique, such that the robustness measures can be
distinguished for different networks; 2) the TD measures require much fewer
numbers of attacks to measure the robustness and thus requires less
computational time.

##  IV Comparison between A Priori and A Posteriori Measures

Now, experimental results on a priori and a posteriori measures are compared
under 3 different node-attack strategies, namely exhaustive attack (EXA)[164],
MDTA, and MBTA.

EXA averages the robustness values of a given $N$-node network over all the
$N!$ possible node-attack sequences. Note that any intentional attack (e.g.,
MDTA, MBTA) is a particular case of the exhaustive attacks. Since the sample
size of $N!$ becomes enormous as $N$ increases, only $N=4$ is tested here,
which well serves for the purpose of demonstration. Figs. 7 and 8 show the
topologies of the 4-node directed and undirected networks, respectively.

Figure 7: Twelve four-node directed networks: (A) fully-connected (FUL); (B)
weak fully-connected (WKF); (C) loop (LOP); (D) ring-shaped non-loop (RIN);
(E) cactus (CTS); (F) star-shaped out (SSO); (G) star-shaped in (SSI); (H)
star-shaped random (SSR); (I) directed chain (DCH); (L) chain-shaped (UCH);
(K) disconnected (DIS); and (L) isolated (ISO).  Figure 8: Six four-node
undirected networks: (A) fully-connected (FUL); (B) loop (LOP); (C) star-
shaped (STR); (D) cactus (CTS); (E) undirected chain (CHA); (F) isolated
(ISO).

Four a posteriori measures are simulated together, namely the connectivity
robustness measured by Eq. (2), controllability robustness measured by Eq.
(6), communication robustness measured by Eq. (12), and connectivity
robustness measured by NCC, which is defined as follows:

$R_{15}=\frac{1}{N}\sum_{i=0}^{N-1}{N_{NCC}(i)}\,,$ (22)

where $N_{NCC}(i)$ represents the number of connected components after a total
of $i$ nodes have been attacked.

###  IV-A A Priori Measures

A priori measures are quantified by specific network features that can be
calculated without performing attack simulations. A priori measures require
only one-time calculation and they usually have lower time and computational
complexities compared to a posteriori measures[13, 14].

Four topological a priori measures are compared with a posteriori measures for
both directed and undirected networks, namely efficiency (EFF)[177], node
betweenness (NB)[28], edge betweenness (EB)[28], and clustering coefficient
(CC)[29].

Spectral measures are widely used to measure network connectivity robustness
for undirected networks[13]. Here, 3 adjacency matrix-based spectral measures,
namely spectral radius (AS-SR)[30], spectral gap (AS-SG)[31] and natural
connectivity (AS-NC)[32] measures, and 3 Laplacian matrix-based spectral
measures, namely algebraic connectivity (LS-AC)[33], number of spanning trees
(LS-NS)[35], and effective resistance (LS-ER)[34], are compared with a
posteriori measures for measuring undirected networks.

###  IV-B Attack Simulations

TABLE III: Robustness ranks of the 12 directed 4-node networks, using 4 a posteriori measures and 4 a priori measures.  | Directed 4-Node
---
Networks
FUL | WKF | LOP | RIN | CTS | SSO | SSI | SSR | DCH | UCH | DIS | ISO
A Posteriori Measures | EXA |  $R_{1}$ (Eq.(2)) | 1.5 | 1.5 | 3.5 | 3.5 | 5 | 8 | 8 | 8 | 8 | 8 | 11 | 12
$R_{15}$ (Eq.(22)) | 1.5 | 1.5 | 3.5 | 3.5 | 5 | 8 | 8 | 8 | 8 | 8 | 11 | 12
$R_{3}$ (Eq.(6)) | 1.5 | 1.5 | 3 | 4.5 | 4.5 | 10.5 | 10.5 | 8 | 6 | 9 | 7 | 12
$R_{7}$ (Eq.(12)) | 1.5 | 1.5 | 3.5 | 3.5 | 5 | 7 | 7 | 7 | 9.5 | 9.5 | 11 | 12
MDTA |  $R_{1}$ (Eq.(2)) | 3.5 | 3.5 | 7 | 3.5 | 3.5 | 10 | 3.5 | 10 | 3.5 | 8 | 10 | 12
$R_{15}$ (Eq.(22)) | 3.5 | 3.5 | 7 | 3.5 | 3.5 | 10 | 3.5 | 10 | 3.5 | 8 | 10 | 12
$R_{3}$ (Eq.(6)) | 2.5 | 2.5 | 6 | 2.5 | 5 | 11 | 7.5 | 10 | 2.5 | 9 | 7.5 | 12
$R_{7}$ (Eq.(12)) | 3.5 | 3.5 | 7 | 3.5 | 3.5 | 9.5 | 3.5 | 9.5 | 3.5 | 8 | 11 | 12
MBTA |  $R_{1}$ (Eq.(2)) | 2.5 | 2.5 | 6.5 | 2.5 | 6.5 | 6.5 | 2.5 | 10.5 | 9 | 6.5 | 10.5 | 12
$R_{15}$ (Eq.(22)) | 2.5 | 2.5 | 6.5 | 2.5 | 6.5 | 6.5 | 2.5 | 10.5 | 9 | 6.5 | 10.5 | 12
$R_{3}$ (Eq.(6)) | 1.5 | 1.5 | 5 | 3.5 | 3.5 | 10 | 7 | 11 | 7 | 9 | 7 | 12
$R_{7}$ (Eq.(12)) | 2.5 | 2.5 | 6 | 2.5 | 8 | 6 | 2.5 | 10 | 9 | 6 | 11 | 12
A Priori Measures | EFF | 1 | 2 | 3 | 5 | 4 | 10 | 10 | 8 | 7 | 10 | 6 | 12
NB | 2.5 | 10 | 11 | 5.5 | 9 | 2.5 | 2.5 | 5.5 | 8 | 2.5 | 7 | NA
EB | 2.5 | 8 | 11 | 5 | 10 | 2.5 | 2.5 | 6 | 9 | 2.5 | 7 | NA
CC | 1.5 | 1.5 | 8.5 | 8.5 | 4 | 8.5 | 8.5 | 8.5 | 8.5 | 8.5 | 3 | 8.5
TABLE IV: Robustness ranks of the 6 undirected 4-node networks, using 4 a posteriori measures and 10 a priori measures.  | Undirected 4-Node
---
Networks
FUL | LOP | STR | CTS | CHA | ISO
A Posteriori Measures |  EXA |  $R_{1}$ (Eq.(2)) | 1 | 2 | 4.5 | 3 | 4.5 | 6
$R_{15}$ (Eq.(22)) | 1 | 2 | 4.5 | 3 | 4.5 | 6
$R_{3}$ (Eq.(6)) | 1 | 4 | 5 | 2 | 3 | 6
$R_{7}$ (Eq.(12)) | 1 | 2 | 4 | 3 | 5 | 6
MDTA |  $R_{1}$ (Eq.(2)) | 1 | 2 | 5 | 3.5 | 3.5 | 6
$R_{15}$ (Eq.(22)) | 1 | 2 | 5 | 3.5 | 3.5 | 6
$R_{3}$ (Eq.(6)) | 1 | 4 | 5 | 2.5 | 2.5 | 6
$R_{7}$ (Eq.(12)) | 1 | 2 | 5 | 3.5 | 3.5 | 6
MBTA |  $R_{1}$ (Eq.(2)) | 1 | 2.5 | 5 | 2.5 | 4 | 6
$R_{15}$ (Eq.(22)) | 1 | 2.5 | 5 | 2.5 | 4 | 6
$R_{3}$ (Eq.(6)) | 1.5 | 4 | 5 | 1.5 | 3 | 6
$R_{7}$ (Eq.(12)) | 1 | 2 | 5 | 3 | 4 | 6
A Priori Measures | EFF | 1 | 2.5 | 4 | 2.5 | 5 | 6
NB | 1 | 2.5 | 4 | 2.5 | 5 | NA
EB | 1 | 2.5 | 4 | 2.5 | 5 | NA
CC | 1 | 4.5 | 4.5 | 2 | 4.5 | 4.5
AS-SR | 1 | 3 | 4 | 2 | 5 | 6
AS-SG | 1 | 2 | 4 | 3 | 5 | 6
AS-NC | 1 | 3 | 4 | 2 | 5 | 6
LS-AC | 1 | 2 | 3.5 | 3.5 | 5 | 6
LS-NS | 1 | 2.5 | 4.5 | 2.5 | 4.5 | 6
LS-ER | 1 | 2 | 4 | 3 | 5 | NA

Tables III and IV show the robustness ranks of different 4-node networks,
where equal robustness share the same ranks. Intensive simulations show the
following general results:

1) A posteriori measures return different values when different attack
strategies are applied, while a priori measures return a unique value for the
network under different attacks. This suggests that a priori measures are not
capable of distinguishing the network robustness under different attacks;
while a posteriori measures are capable of capturing even tiny robustness
difference of a network under different attacks.

2) Most measures can reflect the basic fact that fully-connected networks
possesses the best robustness, followed by connected networks, then
disconnected networks, and lastly isolated networks, which possess the worst
robustness. This means that both a posteriori and a priori measures can
generally reflect the robustness of networks, regardless of the attack
strategies.

3) For the 12 directed networks, no measure can distinguish all of them with
different robustness values; whereas for the 6 undirected networks, the
measures described by Eq. (6) under EXA, Eq. (12) under EXA and MBTA, as well
as the 3 adjacency matrix-based spectral measures, all return 6 distinguished
robustness values. This suggests that the robustness measures for directed
networks remain a challenging research topic for future investigation. It is
also intuitively clear that different directed networks may possess the same
robustness performance, which are impossible to distinguish.

4) The two connectivity robustness measures, $R_{1}$ in Eq. (2) and $R_{15}$
in Eq. (22), return identical robustness values (ranks) in all the cases for
both directed and undirected networks, indicating that these two measures are
highly-correlated. It is worth mentioning that $R_{1}$ has been widely used
for robustness measure, while $R_{15}$ is rarely used. As can be seen from
Section III, more useful information can be dug out from NCC, which may be
underestimated as compared to LCC.

5) CC cannot provide distinguished robustness values for different networks in
many cases; while NB, EB, and LS-ER cannot measure the isolated networks. In
contrast, the a posteriori measures are able to return different robustness
values for all networks. This suggests a wider applicability of the a
posteriori measures.

The advantages of a posteriori measures, which are summarized from the
experimental comparisons shown in Tables III and IV, are as follows:

1) A posteriori measures have intuitively clear meanings for each network
function and each attack strategy, while a priori measures always return a
unique robustness value for a given network.

2) A posteriori measures can provide more robustness information about the
given networks. For example, although the 3 adjacency-spectral measures can
return distinguished robustness values for different undirected networks, as
shown in Table IV, they disagree with the assertion that LOP is more
robustness than CTS. In contrast, a posteriori measures tell much more useful
information: LOP is more robustness than CTS with respect to $R_{1}$,
$R_{15}$, and $R_{7}$, but CTS is more robustness than LOP with respect to
$R_{3}$ under EXA and MDTA; two networks are equally robust under MBTA with
respect to $R_{1}$ and $R_{15}$.

3) It is clear that the spectral measures provide better indicators than the
topological measures, but the former can only be applied to undirected
networks. Moreover, NB, EB, and LS-ER cannot even be calculated for isolated
networks. In contrast, a posteriori measures can be applied to any network,
and provide better indicators to network robustness, thus have a wider
applicability.

##  V Prospective Research Directions

Some prospective research directions are summarized from four aspects: 1)
exploring better weighting methods and termination criteria for Eq. (1); 2)
designing more efficient and precise analytical and computational estimation
methods; 3) performing more efficient robustness optimization; and 4)
exploring more real-world applications.

###  V-A Weighting the Attacks

The currently widely-used a posteriori robustness measures assign unique
weights for each single attack in the attack sequence, assuming equal
contributions of all the remaining network functionalities to the calculation
of the overall robustness. As shown in Eq. (1), when $w_{i}=1/N$, it means
that $f(i)$ and $f(j)$ ($j\neq i$) are equally important to the overall
network robustness. Although the importance of attacking nodes $i$ and $j$ can
be partially reflected by the different values of $f(i)$ and $f(j)$, this is
clearly insufficient in many scenarios.

Practically, the removal or malfunction of some nodes will cause greater
damages than other nodes. If such important nodes are attacked at the very
beginning, the robustness measure should be different from the scenario that
these important nodes can be protected until the later stages. The robustness
measure can be delicately adjusted for different applications, by setting
proper configuration of $w_{i}$. Meanwhile, if important nodes can be attacked
at the beginning, more credits should be assigned to the attack strategy;
otherwise, it means that the attack strategy is less efficient.

Moreover, the network robustness under different attack strategies can be
weighted, depending on the specific situation and concern. Weighting values
can be added into Eq. (16), where its current form implies uniform weights for
different attack strategies. In practice, if the probabilities of a network
suffering different attacks are different, then it is meaningful to impose
different weights to them.

Possible realistic weighting methodologies include decaying weights,
importance-based weights, adaptive weights, etc.

###  V-B Termination Criteria

A realistic threshold of destruction is introduced in Section III, which gives
an alternative threshold to the conventional settings, such as the Molloy–Reed
criterion[167] and the fixed-proportion threshold. However, there still lacks
a systematic investigation on the determination of the time when a networked
system is deemed breakdown thereby the attack process can be terminated. The
destruction of networks can be investigated from the perspectives of
topological structures, network functions, or both.

To determine proper termination criteria, analytical and theoretical studies
can be carried out, for example, further development of the Molloy–Reed
criterion[167], percolation theory[178], and so on. Empirical studies such as
the realistic threshold introduced in Section III can also be further
investigated. Moreover, machine learning techniques may be utilized for
solving this problem more effectively from a data-scientific perspective,
based on both real-world networks and synthetic models. For example, given
real-world data of network destruction as training data, machine learning can
be used to estimate whether a given network is considered breakdown, or when
it would be breakdown, under attacks.

###  V-C Robustness Estimation

It is important to precisely and cost-efficiently approximate various
robustness of large-scale networks.

The existing analytical approximations are applicable only to very limited
specific issues of complex networks, e.g., controllability robustness under
random or critical edge-attacks[51, 52, 53]. Considering Eq. (6) as the
controllability robustness measure, attacking a single node (or edge) may
either increase the number of DN by 1, or it does not change the number of DN
at all. Thus, the maximum damage to the network controllability is limited. In
contrast, when Eq. (2) is used to study the connectivity robustness, the range
of damages caused by each attack to LCC could vary from 0 to $N-1$, namely
with all possibilities. Therefore, predicting the connectivity robustness is
much more uncertain and challenging than predicting the controllability
robustness, either analytically or computationally[179].

In this direction, if the pattern of malicious attacks can be well modeled
using mathematics and statistics tools, then analytical approximation methods
are recommended; but if there is no such a pattern (neither random not
specifically targeted), then analytical methods are inapplicable while
computational techniques are effective.

A comprehensive investigation of analytical approximation to robustness is
needed, where some potential research topics include: 1) modeling more
intrinsic attacks other than random or degree-based attacks; 2) exploring the
relationships between the topological features and the robustness performance,
where if direct relationships cannot be revealed then indirected relationships
may be explored, for example some critical points (e.g., turning points) of
the robustness curve might be estimated using topological features, so that a
robustness curve can be fitted based on these critical points. As for
computational approaches, not only the state-of-the-art machine learning
techniques can be developed and applied, but also prior knowledge and
theoretical findings can be used to further improve the prediction
performances.

###  V-D Robustness Optimization

Network robustness optimization via topological rewiring is NP-hard[180]. The
development of evolutionary algorithms helps in effectively resolving this
difficult problem. Robustness optimization for large-scale complex networks is
higher-dimensional and computational expensive in general. In this regard,
dimension reduction can be archived by applying graph embedding or using
GNN[133, 134, 135], which not only compress higher-dimensional network data
into lower-dimensional representations, but also extract structural features
for further processing. As for the computational expenses in robustness
evaluation, surrogate models are advantageous for improving the search
efficiency and capability[49, 50]. Robustness estimation techniques, as
introduced in Subsection V-C, can provide even better estimation tools than
the commonly-used surrogates methods in evolutionary computation.

Since the thriving development of evolutionary computation has provided useful
approaches for complex networks to evolve towards more robust structures, the
key issue in this research direction is how to substantially reduce the
computational cost of robustness evaluation. Although surrogates and easy-to-
access indicators (such as assortativity coefficient) have been employed, the
runtime of optimization remains high in many real-world applications[49, 50].

Fast and precise estimation methods, both analytical and computational, can be
applied to further reduce the runtime. Since real evaluations of robustness
are inevitable, the ratio and arrangement between the real evaluations and the
estimations should be investigated, such that the cost-efficiency can be
maximized. Moreover, instead of using adjacency matrices as the chromosomes,
better network representations may be explored, such that the feasibility of
robustness optimization in the lower-dimensional representation domain (other
than the higher-dimensional topological domain) can be explored.

###  V-E Real-world Applications

The study of network robustness not only has been extended to many different
network types, including weighted networks[97], network of networks[181, 95,
182, 96], interdependent networks[92, 183, 94, 89, 184], and multiplex
networks[185, 186], but also has been applied to more and more real-world
applications, for example land and air transport networks[187, 188, 24, 189,
25, 190, 191, 192, 193, 194], wireless sensor networks[77, 22, 195], power
grids[196, 23, 197], Internet of Things[198], and so on.

Together with the development of realistic robustness measures, fast and
precise robustness estimation, and cost-efficient optimization techniques, it
is expected that these findings and the developed techniques can significantly
extend and facilitate broader applications of real-world network problems in
the near future.

##  VI Conclusions

The rapid development of complex networks research demands effective measures
on various types of network robustness, especially for practical a posteriori
measures.

This survey presents a summary and overview of the comprehensive network
robustness research development, focusing on the a posteriori robustness
measures. Specifically, the a posteriori robustness measures are reviewed from
four perspectives, namely the network functionality, malicious attacks,
robustness estimation, and network robustness optimization. Moreover, a
practical threshold of network destruction due to attacks is introduced.
Network robustness is suggested to be measured only before the threshold of
destruction is reached, thereafter the network is deemed breakdown and so
further measuring its functionality is not meaningful anymore. Extensive
simulations confirm that the proposed threshold is suitable for certain
functional robustness under some specific attack strategies. Thereby, further
systematic investigation is recommended for determining network destruction
with respect to a posteriori measures.

Moreover, experimental comparisons of a posteriori and a priori measures on
directed and undirected example networks are performed and analyzed. Compared
to a priori measures, the advantages of a posteriori measures are obvious: 1)
a posteriori measures have intuitively clear meanings for every network
function and attack strategy; 2) a posteriori measures provide more useful
robustness information; and 3) a posteriori measures have wider applicability.

Finally, some prospective research directions with respect to a posteriori
robustness measures are suggested, including weighting and termination of a
posteriori measures, analytical and computation-based robustness estimation
methods, robustness optimization techniques, and some potential real-world
applications.

## References

  * [1] A.-L. Barabási, _Network Science_. Cambridge University Press, 2016.
  * [2] M. E. Newman, _Networks: An Introduction_. Oxford University Press, 2010.
  * [3] R. Cohen and S. Havlin, _Complex Networks: Structure, Robustness and Function_. Cambridge university press, 2010\.
  * [4] G. Chen, X. Wang, and X. Li, _Fundamentals of Complex Networks: Models, Structures and Dynamics_ , 2nd ed. John Wiley & Sons, 2014.
  * [5] D. S. Callaway, M. E. Newman, S. H. Strogatz, and D. J. Watts, “Network robustness and fragility: Percolation on random graphs,” _Physical Review Letters_ , vol. 85, no. 25, p. 5468, 2000.
  * [6] P. Holme, B. J. Kim, C. N. Yoon, and S. K. Han, “Attack vulnerability of complex networks,” _Physical Review E_ , vol. 65, no. 5, p. 056109, 2002\.
  * [7] B. Shargel, H. Sayama, I. R. Epstein, and Y. Bar-Yam, “Optimization of robustness and connectivity in complex networks,” _Physical Review Letters_ , vol. 90, no. 6, p. 068701, 2003.
  * [8] A. Bashan, Y. Berezin, S. Buldyrev, and S. Havlin, “The extreme vulnerability of interdependent spatially embedded networks,” _Nature Physics_ , vol. 9, pp. 667–672, 2013.
  * [9] S. Iyer, T. Killingback, B. Sundaram, and Z. Wang, “Attack robustness and centrality of complex networks,” _PLoS One_ , vol. 8, no. 4, p. e59613, 2013\.
  * [10] X. Yuan, S. Shao, H. E. Stanley, and S. Havlin, “How breadth of degree distribution influences network robustness: comparing localized and random attacks,” _Physical Review E_ , vol. 92, no. 3, p. 032122, 2015.
  * [11] A. K. Dey, Y. R. Gel, and H. V. Poor, “What network motifs tell us about resilience and reliability of complex networks,” _Proceedings of the National Academy of Sciences_ , vol. 116, no. 39, pp. 19 368–19 373, 2019.
  * [12] W. Ellens and R. E. Kooij, “Graph measures and network robustness,” _arXiv preprint arXiv:1311.5064_ , 2013.
  * [13] H. Chan and L. Akoglu, “Optimizing network robustness by edge rewiring: A general framework,” _Data Mining and Knowledge Discovery_ , vol. 30, no. 5, pp. 1395–1425, 2016.
  * [14] S. Freitas, D. Yang, S. Kumar, H. Tong, and D. H. Chau, “Graph vulnerability and robustness: A survey,” _IEEE Transactions on Knowledge and Data Engineering_ , 2022, doi:10.1109/TKDE.2022.3163672 (online published).
  * [15] C. M. Schneider, A. A. Moreira, J. S. Andrade, S. Havlin, and H. J. Herrmann, “Mitigation of malicious attacks on networks,” _Proceedings of the National Academy of Sciences_ , vol. 108, no. 10, pp. 3838–3841, 2011.
  * [16] Y.-Y. Liu, J.-J. Slotine, and A.-L. Barabási, “Controllability of complex networks,” _Nature_ , vol. 473, no. 7346, pp. 167–173, 2011.
  * [17] Z. Z. Yuan, C. Zhao, Z. R. Di, W.-X. Wang, and Y.-C. Lai, “Exact controllability of complex networks,” _Nature Communications_ , vol. 4, p. 2447, 2013.
  * [18] L. Xiang, F. Chen, W. Ren, and G. Chen, “Advances in network controllability,” _IEEE Circuits and Systems Magazine_ , vol. 19, no. 2, pp. 8–32, 2019.
  * [19] Y. Lu, Y. Zhao, F. Sun, and R. Liang, “Measuring and improving communication robustness of networks,” _IEEE Communications Letters_ , vol. 23, no. 12, pp. 2168–2171, 2019.
  * [20] B. Mburano, W. Si, and W. X. Zheng, “A comparative study on the variants of r metric for network robustness,” in _International Symposium on Networks, Computers and Communications (ISNCC)_. IEEE, 2021, pp. 1–6.
  * [21] G. Yan, P. E. Vértes, E. K. Towlson, Y. L. Chew, D. S. Walker, W. R. Schafer, and A.-L. Barabási, “Network control principles predict neuron function in the caenorhabditis elegans connectome,” _Nature_ , vol. 550, no. 7677, p. 519, 2017.
  * [22] T. Qiu, J. Liu, W. Si, and D. O. Wu, “Robustness optimization scheme with multi-population co-evolution for scale-free wireless sensor networks,” _IEEE/ACM Transactions on Networking_ , vol. 27, no. 3, pp. 1028–1042, 2019\.
  * [23] Z. Chen, J. Wu, Y. Xia, and X. Zhang, “Robustness of interdependent power grids and communication networks: A complex network perspective,” _IEEE Transactions on Circuits and Systems II: Express Briefs_ , vol. 65, no. 1, pp. 115–119, 2017.
  * [24] C. Yang, J. Mao, X. Qian, and P. Wei, “Designing robust air transportation networks via minimizing total effective resistance,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 20, no. 6, pp. 2353–2366, 2018.
  * [25] Q. Cai, S. Alam, H. Ang, and V. Duong, “A braess’s paradox inspired method for enhancing the robustness of air traffic networks,” in _2020 IEEE Symposium Series on Computational Intelligence (SSCI)_. IEEE, 2020, pp. 798–805.
  * [26] R. Diestel, _Graph Theory_. Springer Nature, 2017.
  * [27] V. Latora and M. Marchiori, “A measure of centrality based on network efficiency,” _New Journal of Physics_ , vol. 9, no. 6, p. 188, 2007.
  * [28] L. C. Freeman, “A set of measures of centrality based on betweenness,” _Sociometry_ , pp. 35–41, 1977.
  * [29] D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘small-world’ networks,” _Nature_ , vol. 393, no. 6684, pp. 440–442, 1998.
  * [30] P. Van Mieghem, D. Stevanović, F. Kuipers, C. Li, R. Van De Bovenkamp, D. Liu, and H. Wang, “Decreasing the spectral radius of a graph by link removals,” _Physical Review E_ , vol. 84, no. 1, p. 016101, 2011.
  * [31] F. D. Malliaros, V. Megalooikonomou, and C. Faloutsos, “Fast robustness estimation in large social graphs: Communities and anomaly detection,” in _SIAM International Conference on Data Mining_. SIAM, 2012, pp. 942–953.
  * [32] J. Wu, B. Mauricio, Y.-J. Tan, and H.-Z. Deng, “Natural connectivity of complex networks,” _Chinese Physics Letters_ , vol. 27, no. 7, p. 078902, 2010.
  * [33] M. Fiedler, “Algebraic onnectivity of graphs,” _Czechoslovak Mathematical Journal_ , vol. 23, no. 2, pp. 298–305, 1973.
  * [34] D. J. Klein and M. Randić, “Resistance distance,” _Journal of Mathematical Chemistry_ , vol. 12, no. 1, pp. 81–95, 1993.
  * [35] S. K. Butler, _Eigenvalues and Structures of Graphs_. University of California, San Diego, 2008.
  * [36] K. Yamashita, Y. Yasuda, R. Nakamura, and H. Ohsaki, “On the predictability of network robustness from spectral measures,” in _2019 IEEE 43rd Annual Computer Software and Applications Conference (COMPSAC)_ , vol. 2. IEEE, 2019, pp. 24–29.
  * [37] Z. Sha and J. H. Panchal, “Towards the design of complex evolving networks with high robustness and resilience,” _Procedia Computer Science_ , vol. 16, pp. 522–531, 2013.
  * [38] X.-Y. Yan, W.-X. Wang, G. Chen, and D.-H. Shi, “Multiplex congruence network of natural numbers,” _Scientific Reports_ , vol. 6, p. 23714, 2016.
  * [39] Y. Lou, L. Wang, and G. Chen, “Toward stronger robustness of network controllability: A snapback network model,” _IEEE Transactions on Circuits and Systems I: Regular Papers_ , vol. 65, no. 9, pp. 2983–2991, 2018\.
  * [40] Y. Hayashi, “A new design principle of robust onion-like networks self-organized in growth,” _Network Science_ , vol. 6, no. 1, pp. 54–70, 2018.
  * [41] Y. Lou, L. Wang, and G. Chen, “Enhancing controllability robustness of q-snapback networks through redirecting edges,” _Research_ , vol. 2019, no. 7857534, 2019.
  * [42] A. Beygelzimer, G. Grinstein, R. Linsker, and I. Rish, “Improving network robustness by edge modification,” _Physica A: Statistical Mechanics and Its Applications_ , vol. 357, no. 3-4, pp. 593–612, 2005.
  * [43] Z.-X. Wu and P. Holme, “Onion structure and network robustness,” _Physical Review E_ , vol. 84, no. 2, p. 026106, 2011.
  * [44] A. Zeng and W. Liu, “Enhancing network robustness against malicious attacks,” _Physical Review E_ , vol. 85, no. 6, p. 066130, 2012.
  * [45] V. H. Louzada, F. Daolio, H. J. Herrmann, and M. Tomassini, “Smart rewiring for network robustness,” _Journal of Complex Networks_ , vol. 1, no. 2, pp. 150–159, 2013.
  * [46] C. M. Schneider, N. Yazdani, N. A. Araújo, S. Havlin, and H. J. Herrmann, “Towards designing robust coupled networks,” _Scientific Reports_ , vol. 3, no. 1, pp. 1–7, 2013.
  * [47] L. Bai, Y.-D. Xiao, L.-L. Hou, and S.-Y. Lao, “Smart rewiring: Improving network robustness faster,” _Chinese Physics Letters_ , vol. 32, no. 7, p. 078901, 2015.
  * [48] Y. Lou, S. Xie, and G. Chen, “Searching better rewiring strategies and objective functions for stronger controllability robustness,” _IEEE Transactions on Circuits and Systems II: Express Briefs_ , vol. 68, no. 6, pp. 2112–2116, 2021.
  * [49] S. Wang, J. Liu, and Y. Jin, “Surrogate-assisted robust optimization of large-scale networks based on graph embedding,” _IEEE Transactions on Evolutionary Computation_ , vol. 24, no. 4, pp. 735–749, 2020.
  * [50] ——, “A computationally efficient evolutionary algorithm for multiobjective network robustness optimization,” _IEEE Transactions on Evolutionary Computation_ , vol. 25, no. 3, pp. 419–432, 2021.
  * [51] P. Sun, R. E. Kooij, Z. He, and P. Van Mieghem, “Quantifying the robustness of network controllability,” in _International Conference on System Reliability and Safety (ICSRS)_. IEEE, 2019, pp. 66–76.
  * [52] P. Sun, R. E. Kooij, and P. Van Mieghem, “Reachability-based robustness of controllability in sparse communication networks,” _IEEE Transactions on Network and Service Management_ , vol. 18, no. 3, pp. 2764–2775, 2021.
  * [53] Y. Lou, L. Wang, S. Xie, and G. Chen, “Approximating the controllability robustness of directed random-graph networks against random edge-removal attacks,” _International Journal of Control Automation and Systems_ , 2023, (In Press).
  * [54] Y. Lou, Y. He, L. Wang, and G. Chen, “Predicting network controllability robustness: A convolutional neural network approach,” _IEEE Transactions on Cybernetics_ , vol. 52, no. 5, pp. 4052–4063, 2022.
  * [55] Y. Lou, Y. He, L. Wang, K. F. Tsang, and G. Chen, “Knowledge-based prediction of network controllability robustness,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 33, no. 10, pp. 5739–5750, 2022.
  * [56] Y. Lou, R. Wu, J. Li, L. Wang, C.-B. Tang, and G. Chen, “Classification-based prediction of network connectivity robustness,” _Neural Networks_ , vol. 157, pp. 136–146, 2023.
  * [57] A.-L. Barabási and Z. N. Oltvai, “Network biology: Understanding the cell’s functional organization,” _Nature Reviews Genetics_ , vol. 5, no. 2, pp. 101–113, 2004.
  * [58] H. Kitano, “Biological robustness,” _Nature Reviews Genetics_ , vol. 5, no. 11, pp. 826–837, 2004.
  * [59] S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D.-U. Hwang, “Complex networks: Structure and dynamics,” _Physics Reports_ , vol. 424, no. 4-5, pp. 175–308, 2006.
  * [60] J. Liu, M. Zhou, S. Wang, and P. Liu, “A comparative study of network robustness measures,” _Frontiers of Computer Science_ , vol. 11, no. 4, pp. 568–584, 2017.
  * [61] A. Logins, Y. Li, and P. Karras, “On the robustness of diffusion in a network under node attacks,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 34, no. 12, pp. 5884–5895, 2022.
  * [62] ——, “On the robustness of cascade diffusion under node attacks,” in _The Web Conference_ , 2020, pp. 2711–2717.
  * [63] L. Cuadra, S. Salcedo-Sanz, J. Del Ser, S. Jiménez-Fernández, and Z. W. Geem, “A critical review of robustness in power grids using complex networks concepts,” _Energies_ , vol. 8, no. 9, pp. 9211–9265, 2015.
  * [64] M. Bellingeri and A. Bodini, “Threshold extinction in food webs,” _Theoretical Ecology_ , vol. 6, no. 2, pp. 143–152, 2013.
  * [65] S. Wandelt, W. Lin, X. Sun, and M. Zanin, “From random failures to targeted attacks in network dismantling,” _Reliability Engineering & System Safety_, vol. 218, p. 108146, 2022.
  * [66] C.-T. Chen, _Linear System Theory and Design_ , 3rd ed. Oxford University Press, 1998.
  * [67] S. Hosoe, “Determination of generic dimensions of controllable subspaces and its application,” _IEEE Transactions on Automatic Control_ , vol. 25, no. 6, pp. 1192–1196, 1980.
  * [68] Y.-Y. Liu, J.-J. Slotine, and A.-L. Barabási, “Control centrality and hierarchical structure in complex networks,” _PLoS One_ , vol. 7, no. 9, p. e44459, 2012.
  * [69] U. Usman, “Optimal driver set selection based on robustness of controllability,” Master’s thesis, Shanghai Jiao Tong University, 2020.
  * [70] U. Usman, A. Mahmood, and L. Wang, “Robust control centrality,” _2019 Chinese Control Conference (CCC)_ , pp. 5486–5491, 2019.
  * [71] D. Parekh, D. Ruths, and J. Ruths, “Reachability-based robustness of network controllability under node and edge attacks,” in _International Conference on Signal-Image Technology and Internet-Based Systems_. IEEE, 2014, pp. 424–431.
  * [72] H. J. LeBlanc, H. Zhang, X. Koutsoukos, and S. Sundaram, “Resilient asymptotic consensus in robust networks,” _IEEE Journal on Selected Areas in Communications_ , vol. 31, no. 4, pp. 766–781, 2013.
  * [73] J. Zhao, O. Yağan, and V. Gligor, “On the strengths of connectivity and robustness in general random intersection graphs,” in _53rd IEEE Conference on Decision and Control_. IEEE, 2014, pp. 3661–3668.
  * [74] H. Zhang, E. Fata, and S. Sundaram, “A notion of robustness in complex networks,” _IEEE Transactions on Control of Network Systems_ , vol. 2, no. 3, pp. 310–320, 2015.
  * [75] F. G. Morales, M. H. Paiva, and J. A. Bustos-Jiménez, “Measuring and improving network robustness: A chilean case study,” _IEEE Communications Letters_ , vol. 23, no. 1, pp. 44–47, 2018.
  * [76] H. Wiener, “Structural determination of paraffin boiling points,” _Journal of the American Chemical Society_ , vol. 69, no. 1, pp. 17–20, 1947\.
  * [77] T. Qiu, A. Zhao, F. Xia, W. Si, and D. O. Wu, “ROSE: Robustness strategy for scale-free wireless sensor networks,” _IEEE/ACM Transactions on Networking_ , vol. 25, no. 5, pp. 2944–2959, 2017.
  * [78] Y.-D. Xiao, S.-Y. Lao, L.-L. Hou, and L. Bai, “Optimization of robustness of network controllability against malicious attacks,” _Chinese Physics B_ , vol. 23, no. 11, p. 118902, 2014.
  * [79] S. Wang and J. Liu, “A multi-objective evolutionary algorithm for promoting the emergence of cooperation and controllable robustness on directed networks,” _IEEE Transactions on Network Science and Engineering_ , vol. 5, no. 2, pp. 92–100, 2018.
  * [80] C.-L. Pu, W.-J. Pei, and A. Michaelson, “Robustness analysis of network controllability,” _Physica A: Statistical Mechanics and its Applications_ , vol. 391, no. 18, pp. 4420–4425, 2012.
  * [81] S. Nie, X. Wang, H. Zhang, Q. Li, and B. Wang, “Robustness of controllability for networks based on edge-attack,” _PLoS One_ , vol. 9, no. 2, p. e89066, 2014.
  * [82] X. Tang, J. Liu, and X. Hao, “Mitigate cascading failures on networks using a memetic algorithm,” _Scientific Reports_ , vol. 6, no. 1, pp. 1–12, 2016\.
  * [83] S.-M. Chen, Y.-F. Xu, and S. Nie, “Robustness of network controllability in cascading failure,” _Physica A: Statistical Mechanics and Its Applications_ , vol. 471, pp. 536–539, 2017.
  * [84] L.-l. Hou, Y.-d. Xiao, and L. Lu, “Robustness of network controllability against cascading failure,” in _International Conference on Intelligent Science and Big Data Engineering_. Springer, 2019, pp. 347–355.
  * [85] L. Ma, M. Gong, Q. Cai, and L. Jiao, “Enhancing community integrity of networks against multilevel targeted attacks,” _Physical Review E_ , vol. 88, no. 2, p. 022810, 2013.
  * [86] S. Wang, J. Liu, and X. Wang, “Mitigation of attacks and errors on community structure in complex networks,” _Journal of Statistical Mechanics: Theory and Experiment_ , vol. 2017, no. 4, p. 043405, 2017.
  * [87] S. Scellato, I. Leontiadis, C. Mascolo, P. Basu, and M. Zafer, “Evaluating temporal robustness of mobile networks,” _IEEE Transactions on Mobile Computing_ , vol. 12, no. 1, pp. 105–117, 2011.
  * [88] T. Nie, Z. Guo, K. Zhao, and Z.-M. Lu, “New attack strategies for complex networks,” _Physica A: Statistical Mechanics and Its Applications_ , vol. 424, pp. 248–253, 2015.
  * [89] Y.-L. Gao, S.-M. Chen, S. Nie, F. Ma, and J.-J. Guan, “Robustness analysis of interdependent networks under multiple-attacking strategies,” _Physica A: Statistical Mechanics and Its Applications_ , vol. 496, pp. 495–504, 2018.
  * [90] Y. Hao, L. Jia, and Y. Wang, “Edge attack strategies in interdependent scale-free networks,” _Physica A: Statistical Mechanics and Its Applications_ , vol. 540, p. 122759, 2020.
  * [91] Q. Nguyen, H. Pham, D. Cassi, and M. Bellingeri, “Conditional attack strategy for real-world complex networks,” _Physica A: Statistical Mechanics and Its Applications_ , vol. 530, p. 121561, 2019.
  * [92] X. Huang, J. Gao, S. V. Buldyrev, S. Havlin, and H. E. Stanley, “Robustness of interdependent networks under targeted attack,” _Physical Review E_ , vol. 83, no. 6, p. 065101, 2011.
  * [93] G. Dong, J. Gao, L. Tian, R. Du, and Y. He, “Percolation of partially interdependent networks under targeted attack,” _Physical Review E_ , vol. 85, no. 1, p. 016112, 2012.
  * [94] P. Cui, P. Zhu, K. Wang, P. Xun, and Z. Xia, “Enhancing robustness of interdependent network by adding connectivity and dependence links,” _Physica A: Statistical Mechanics and Its Applications_ , vol. 497, pp. 185–197, 2018.
  * [95] G. Dong, J. Gao, R. Du, L. Tian, H. E. Stanley, and S. Havlin, “Robustness of network of networks under targeted attack,” _Physical Review E_ , vol. 87, no. 5, p. 052804, 2013.
  * [96] X. Liu, H. Peng, and J. Gao, “Vulnerability and controllability of networks of networks,” _Chaos, Solitons & Fractals_, vol. 80, pp. 125–138, 2015.
  * [97] M. Bellingeri and D. Cassi, “Robustness of weighted networks,” _Physica A: Statistical Mechanics and Its Applications_ , vol. 489, pp. 47–55, 2018.
  * [98] G. Chen, Y. Lou, and L. Wang, “A comparative study on controllability robustness of complex networks,” _IEEE Transactions on Circuits and Systems II: Express Briefs_ , vol. 66, no. 5, pp. 828–832, 2019.
  * [99] S. P. Borgatti, “Centrality and network flow,” _Social Networks_ , vol. 27, no. 1, pp. 55–71, 2005.
  * [100] L. Katz, “A new status index derived from sociometric analysis,” _Psychometrika_ , vol. 18, no. 1, pp. 39–43, 1953.
  * [101] Y.-R. Ruan, S.-Y. Lao, J.-D. Wang, L. Bai, and L.-D. Chen, “Node importance measurement based on neighborhood similarity in complex network,” _Acta Physica Sinica_ , vol. 66, no. 3, p. 038902, 2017.
  * [102] M. Šimon, I. Dirgová Luptáková, L. Huraj, M. Host’oveckỳ, and J. Pospíchal, “Combined heuristic attack strategy on complex networks,” _Mathematical Problems in Engineering_ , vol. 2017, 2017.
  * [103] H. Yang and S. An, “Critical nodes identification in complex networks,” _Symmetry_ , vol. 12, no. 1, p. 123, 2020.
  * [104] B. R. da Cunha, J. C. Gonzalez-Avella, and S. Goncalves, “Fast fragmentation of networks using module-based attacks,” _PLoS One_ , vol. 10, no. 11, 2015\.
  * [105] S. Shai, D. Y. Kenett, Y. N. Kenett, M. Faust, S. Dobson, and S. Havlin, “Critical tipping point distinguishing two types of transitions in modular network structures,” _Physical Review E_ , vol. 92, no. 6, p. 062805, 2015\.
  * [106] X.-L. Ren, N. Gleinig, D. Helbing, and N. Antulov-Fantulin, “Generalized network dismantling,” _Proceedings of the National Academy of Sciences_ , vol. 116, no. 14, pp. 6554–6559, 2019.
  * [107] Z.-M. Lu and X.-F. Li, “Attack vulnerability of network controllability,” _PLoS One_ , vol. 11, no. 9, 2016.
  * [108] Y.-H. Hao, J.-H. Han, Y. Lin, and L. Liu, “Vulnerability of complex networks under three-level-tree attacks,” _Physica A: Statistical Mechanics and Its Applications_ , vol. 462, pp. 674–683, 2016.
  * [109] C.-L. Pu and W. Cui, “Vulnerability of complex networks under path-based attacks,” _Physica A: Statistical Mechanics and Its Applications_ , vol. 419, pp. 622–629, 2015.
  * [110] X. Li and G. Chen, “A local-world evolving network model,” _Physica A: Statistical Mechanics and Its Applications_ , vol. 328, no. 1-2, pp. 274–286, 2003\.
  * [111] S. Sun, Y. Ma, Y. Wu, L. Wang, and C. Xia, “Towards structural controllability of local-world networks,” _Physics Letters A_ , vol. 380, no. 22-23, pp. 1912–1917, 2016.
  * [112] H. Wang, J. Huang, X. Xu, and Y. Xiao, “Damage attack on complex networks,” _Physica A: Statistical Mechanics and Its Applications_ , vol. 408, pp. 134–148, 2014.
  * [113] W. Lin, S. Wandelt, and X. Sun, “Efficient network dismantling through genetic algorithms,” _Soft Computing_ , vol. 26, pp. 3107–3125, 2022.
  * [114] Z. Yang and J. Liu, “A memetic algorithm for determining the nodal attacks with minimum cost on complex networks,” _Physica A: Statistical Mechanics and Its Applications_ , vol. 503, pp. 1041–1053, 2018.
  * [115] Y. Lou, L. Wang, and G. Chen, “A framework of hierarchical attacks to network controllability,” _Communications in Nonlinear Science and Numerical Simulation_ , vol. 98, p. 105780, 2021.
  * [116] R. M. Karp, “Reducibility among combinatorial problems,” in _Complexity of Computer Computations_. Springer, 1972, pp. 85–103.
  * [117] A. Braunstein, L. Dall’Asta, G. Semerjian, and L. Zdeborová, “Network dismantling,” _Proceedings of the National Academy of Sciences_ , vol. 113, no. 44, pp. 12 368–12 373, 2016.
  * [118] X. Zhang, J. Wu, H. Wang, J. Xiong, and K. Yang, “Optimization of disintegration strategy for multi-edges complex networks,” in _2016 IEEE Congress on Evolutionary Computation (CEC)_. IEEE, 2016, pp. 522–528.
  * [119] M. Lozano, C. Garcia-Martinez, F. J. Rodriguez, and H. M. Trujillo, “Optimizing network attacks by artificial bee colony,” _Information Sciences_ , vol. 377, pp. 30–50, 2017.
  * [120] Y. Deng, J. Wu, and Y.-j. Tan, “Optimal attack strategy of complex networks based on tabu search,” _Physica A: Statistical Mechanics and Its Applications_ , vol. 442, pp. 74–81, 2016.
  * [121] M. Qi, Y. Deng, H. Deng, and J. Wu, “Optimal disintegration strategy in multiplex networks,” _Chaos: An Interdisciplinary Journal of Nonlinear Science_ , vol. 28, no. 12, p. 121104, 2018.
  * [122] M. Ventresca, “Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem,” _Computers & Operations Research_, vol. 39, no. 11, pp. 2763–2775, 2012\.
  * [123] Q. Li, S.-Y. Liu, and X.-S. Yang, “Neighborhood information-based probabilistic algorithm for network disintegration,” _Expert Systems with Applications_ , vol. 139, p. 112853, 2020.
  * [124] X. Li, Z. Zhang, J. Liu, and K. Gai, “A new complex network robustness attack algorithm,” in _ACM International Symposium on Blockchain and Secure Critical Infrastructure_ , 2019, pp. 13–17.
  * [125] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio, “Graph attention networks,” _arXiv preprint arXiv:1710.10903_ , 2017.
  * [126] M. Grassia, M. De Domenico, and G. Mangioni, “Machine learning dismantling and early-warning signals of disintegration in complex systems,” _Nature Communications_ , vol. 12, no. 5190, 2021.
  * [127] C. Fan, L. Zeng, Y. Sun, and Y.-Y. Liu, “Finding key players in complex networks through deep reinforcement learning,” _Nature Machine Intelligence_ , vol. 2, pp. 317–324, 2020.
  * [128] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski _et al._ , “Human-level control through deep reinforcement learning,” _Nature_ , vol. 518, no. 7540, pp. 529–533, 2015.
  * [129] R. S. Sutton and A. G. Barto, _Reinforcement Learning: An Introduction_. MIT press, 2018.
  * [130] J. Yan, H. He, X. Zhong, and Y. Tang, “Q-learning-based vulnerability analysis of smart grid against sequential topology attacks,” _IEEE Transactions on Information Forensics and Security_ , vol. 12, no. 1, pp. 200–210, 2016.
  * [131] M. Tian, Z. Dong, and X. Wang, “Reinforcement learning approach for robustness analysis of complex networks with incomplete information,” _Chaos, Solitons & Fractals_, vol. 144, p. 110643, 2021.
  * [132] D. Yan, W. Xie, Y. Zhang, Q. He, and Y. Yang, “Hypernetwork dismantling via deep reinforcement learning,” _IEEE Transactions on Network Science and Engineering_ , 2022.
  * [133] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” _arXiv preprint arXiv:1609.02907_ , 2016.
  * [134] W. L. Hamilton, R. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” in _International Conference on Neural Information Processing Systems (NeurIPS)_ , 2017, pp. 1025–1035.
  * [135] W. L. Hamilton, “Graph representation learning,” _Synthesis Lectures on Artifical Intelligence and Machine Learning_ , vol. 14, no. 3, pp. 1–159, 2020\.
  * [136] M. Zhang, X. Wang, L. Jin, M. Song, and Z. Li, “A new approach for evaluating node importance in complex networks via deep learning methods,” _Neurocomputing_ , vol. 497, pp. 13–27, 2022.
  * [137] Q. Cai, S. Alam, M. Pratama, and J. Liu, “Robustness evaluation of multipartite complex networks based on percolation theory,” _IEEE Transactions on Systems, Man, and Cybernetics: Systems_ , vol. 51, no. 10, pp. 6244–6257, 2021.
  * [138] A. Dhiman, P. Sun, and R. Kooij, “Using machine learning to quantify the robustness of network controllability,” in _International Conference on Machine Learning for Networking_. Springer, 2021, pp. 19–39.
  * [139] R. L. Hardy, “Multiquadric equations of topography and other irregular surfaces,” _Journal of Geophysical Research_ , vol. 76, no. 8, pp. 1905–1915, 1971.
  * [140] Z. Zhou, Y. S. Ong, M. H. Nguyen, and D. Lim, “A study on polynomial regression and gaussian process global surrogate model in hierarchical surrogate-assisted evolutionary algorithm,” in _2005 IEEE Congress on Evolutionary Computation (CEC)_ , vol. 3. IEEE, 2005, pp. 2832–2839.
  * [141] D. Shepard, “A two-dimensional interpolation function for irregularly-spaced data,” in _1968 ACM National Conference_ , 1968, pp. 517–524.
  * [142] C. Wu, Y. Lou, R. Wu, W. Liu, and J. Li, “CNN-based prediction of network robustness with missing edges,” in _2022 International Joint Conference on Neural Networks (IJCNN)_. IEEE, 2022, pp. 1–8.
  * [143] Y. Lou, R. Wu, J. Li, L. Wang, X. Li, and G. Chen, “A learning convolutional neural network approach for network robustness prediction,” _IEEE Transactions on Cybernetics_ , 2022, 10.1109/TCYB.2022.3207878 (online published).
  * [144] H. J. Herrmann, C. M. Schneider, A. A. Moreira, J. S. Andrade Jr, and S. Havlin, “Onion-like network topology enhances robustness against malicious attacks,” _Journal of Statistical Mechanics: Theory and Experiment_ , vol. 2011, no. 01, p. P01027, 2011.
  * [145] T. Tanizawa, S. Havlin, and H. E. Stanley, “Robustness of onionlike correlated networks against targeted attacks,” _Physical Review E_ , vol. 85, no. 4, p. 046109, 2012.
  * [146] Y. Hayashi and N. Uchiyama, “Onion-like networks are both robust and resilient,” _Scientific Reports_ , vol. 8, 2018.
  * [147] R. C. Gunasekara, C. K. Mohan, and K. Mehrotra, “Multi-objective optimization to improve robustness in networks,” in _Multi-Objective Optimization_. Springer, 2018, pp. 115–139.
  * [148] J. Liu, H. A. Abbass, and K. C. Tan, “Evolving robust networks using evolutionary algorithms,” in _Evolutionary Computation and Complex Networks_. Springer, 2019, pp. 117–140.
  * [149] P. Buesser, F. Daolio, and M. Tomassini, “Optimizing the robustness of scale-free networks with simulated annealing,” in _International Conference on Adaptive and Natural Computing Algorithms_. Springer, 2011, pp. 167–176.
  * [150] T. P. Peixoto and S. Bornholdt, “Evolution of robust network topologies: Emergence of central backbones,” _Physical Review Letters_ , vol. 109, no. 11, p. 118703, 2012.
  * [151] R. Fletcher, _Practical Methods of Optimization_. John Wiley & Sons, 2013.
  * [152] X.-B. Cao, C. Hong, W.-B. Du, and J. Zhang, “Improving the network robustness against cascading failures by adding links,” _Chaos, Solitons & Fractals_, vol. 57, pp. 35–40, 2013.
  * [153] M. Zhou and J. Liu, “A memetic algorithm for enhancing the robustness of scale-free networks against malicious attacks,” _Physica A: Statistical Mechanics and Its Applications_ , vol. 410, pp. 131–143, 2014.
  * [154] L. Bai, Y.-D. Xiao, L.-L. Hou, and S.-Y. Lao, “Smart rewiring: Improving network robustness faster,” _Chinese Physics Letters_ , vol. 32, no. 7, p. 078901, 2015.
  * [155] Y. Yang, Z. Li, Y. Chen, X. Zhang, and S. Wang, “Improving the robustness of complex networks with preserving community structure,” _PLoS One_ , vol. 10, no. 2, p. e0116551, 2015.
  * [156] X. Tang, J. Liu, and M. Zhou, “Enhancing network robustness against targeted and random attacks using a memetic algorithm,” _EPL (Europhysics Letters)_ , vol. 111, no. 3, p. 38005, 2015.
  * [157] L. Ma, J. Liu, and B. Duan, “Evolution of network robustness under continuous topological changes,” _Physica A: Statistical Mechanics and Its Applications_ , vol. 451, pp. 623–631, 2016.
  * [158] S.-W. Sun, Y.-L. Ma, R.-Q. Li, L. Wang, and C.-Y. Xia, “Tabu search enhances network robustness under targeted attacks,” _Physica A: Statistical Mechanics and Its Applications_ , vol. 446, pp. 82–91, 2016.
  * [159] J. Park and S. G. Hahn, “Bypass rewiring and robustness of complex networks,” _Physical Review E_ , vol. 94, no. 2, p. 022310, 2016.
  * [160] L.-Z. Wang, Y.-Z. Chen, W.-X. Wang, and Y.-C. Lai, “Physical controllability of complex networks,” _Scientific Reports_ , vol. 7, p. 40198, 2017.
  * [161] S. Wang and J. Liu, “A multi-agent genetic algorithm for improving the robustness of communities in complex networks against attacks,” in _2017 IEEE Congress on Evolutionary Computation (CEC)_. IEEE, 2017, pp. 17–22.
  * [162] L. Rong and J. Liu, “A heuristic algorithm for enhancing the robustness of scale-free networks based on edge classification,” _Physica A: Statistical Mechanics and Its Applications_ , vol. 503, pp. 503–515, 2018.
  * [163] Y. Liu, X. Wang, and J. Kurths, “Framework of evolutionary algorithm for investigation of influential nodes in complex networks,” _IEEE Transactions on Evolutionary Computation_ , vol. 23, no. 6, pp. 1049–1063, 2019\.
  * [164] Y. Lou, L. Wang, K.-F. Tsang, and G. Chen, “Towards optimal robustness of network controllability: An empirical necessary condition,” _IEEE Transactions on Circuits and Systems I: Regular Papers_ , vol. 67, no. 9, pp. 3163–3174, 2020.
  * [165] J. A. Dunne, R. J. Williams, and N. D. Martinez, “Network structure and robustness of marine food webs,” _Marine Ecology Progress Series_ , vol. 273, pp. 291–302, 2004.
  * [166] A. Curtsdotter, A. Binzer, U. Brose, F. de Castro, B. Ebenman, A. Eklöf, J. O. Riede, A. Thierry, and B. C. Rall, “Robustness to secondary extinctions: comparing trait-based sequential deletions in static and dynamic food webs,” _Basic and Applied Ecology_ , vol. 12, no. 7, pp. 571–580, 2011\.
  * [167] M. Molloy and B. Reed, “A critical point for random graphs with a given degree sequence,” _Random Structures & Algorithms_, vol. 6, no. 2-3, pp. 161–180, 1995.
  * [168] R. Uehara, “The number of connected components in graphs and its applications,” Komazawa University, Japan, Tech. Rep., 1999.
  * [169] O. Lordan and M. Albareda-Sambola, “Exact calculation of network robustness,” _Reliability Engineering & System Safety_, vol. 183, pp. 276–280, 2019\.
  * [170] P. Erdös and A. Rényi, “On the strength of connectedness of a random graph,” _Acta Mathematica Hungarica_ , vol. 12, no. 1-2, pp. 261–267, 1964\.
  * [171] M. E. Newman and D. J. Watts, “Renormalization group analysis of the small-world network model,” _Physics Letters A_ , vol. 263, no. 4-6, pp. 341–346, 1999.
  * [172] Y. Lou, D. Yang, L. Wang, C. Tang, and G. Chen, “Controllability robustness of Henneberg-growth complex networks,” _IEEE Access_ , vol. 10, pp. 5103–5114, 2022.
  * [173] A.-L. Barabási and R. Albert, “Emergence of scaling in random networks,” _Science_ , vol. 286, no. 5439, pp. 509–512, 1999.
  * [174] A.-L. Barabási, “Scale-free networks: A decade and beyond,” _Science_ , vol. 325, no. 5939, pp. 412–413, 2009.
  * [175] K.-I. Goh, B. Kahng, and D. Kim, “Universal behavior of load distribution in scale-free networks,” _Physical Review Letters_ , vol. 87, no. 27, p. 278701, 2001.
  * [176] J.-N. Wu, X. Li, and G. Chen, “Controllability of multi-layer snapback networks,” _IEEE Transactions on Control of Network Systems_ , 2022, 10.1109/TCNS.2022.3185153 (online published).
  * [177] V. Latora and M. Marchiori, “Efficient behavior of small-world networks,” _Physical Review Letters_ , vol. 87, no. 19, p. 198701, 2001.
  * [178] M. Li, R.-R. Liu, L. Lü, M.-B. Hu, S. Xu, and Y.-C. Zhang, “Percolation on complex networks: Theory and application,” _Physics Reports_ , vol. 907, pp. 1–68, 2021.
  * [179] Y. Lou, R. Wu, J. Li, L. Wang, and G. Chen, “A convolutional neural network approach to predicting network connectedness robustness,” _IEEE Transactions on Network Science and Engineering_ , vol. 8, no. 4, pp. 3209–3219, 2021.
  * [180] D. Kempe, J. Kleinberg, and É. Tardos, “Maximizing the spread of influence through a social network,” in _ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , 2003, pp. 137–146.
  * [181] J. Gao, S. V. Buldyrev, S. Havlin, and H. E. Stanley, “Robustness of a network of networks,” _Physical Review Letters_ , vol. 107, no. 19, p. 195701, 2011\.
  * [182] S. Havlin, D. Kenett, A. Bashan, J. Gao, and H. E. Stanley, “Vulnerability of network of networks,” _The European Physical Journal Special Topics_ , vol. 223, no. 11, pp. 2087–2106, 2014.
  * [183] J. Gao, S. V. Buldyrev, S. Havlin, and H. E. Stanley, “Robustness of a network formed by n interdependent networks with a one-to-one correspondence of dependent nodes,” _Physical Review E_ , vol. 85, no. 6, p. 066134, 2012.
  * [184] Z. Zhang, Y. Yin, X. Zhang, and L. Liu, “Optimization of robustness of interdependent network controllability by redundant design,” _PLoS One_ , vol. 13, no. 2, p. e0192874, 2018.
  * [185] B. Min, S. Do Yi, K.-M. Lee, and K.-I. Goh, “Network robustness of multiplex networks with interlayer degree correlations,” _Physical Review E_ , vol. 89, no. 4, p. 042811, 2014.
  * [186] C. Chen, J. He, N. Bliss, and H. Tong, “Towards optimal connectivity on multi-layered networks,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 29, no. 10, pp. 2332–2346, 2017.
  * [187] P. Zhang, B. Cheng, Z. Zhao, D. Li, G. Lu, Y. Wang, and J. Xiao, “The robustness of interdependent transportation networks under targeted attack,” _EPL (Europhysics Letters)_ , vol. 103, no. 6, p. 68005, 2013.
  * [188] X. Sun, V. Gollnick, and S. Wandelt, “Robustness analysis metrics for worldwide airport network: A comprehensive study,” _Chinese Journal of Aeronautics_ , vol. 30, no. 2, pp. 500–512, 2017.
  * [189] O. Lordan, J. M. Sallan, P. Simo, and D. Gonzalez-Prieto, “Robustness of the air transport network,” _Transportation Research Part E: Logistics and Transportation Review_ , vol. 68, pp. 155–163, 2014.
  * [190] J. Jiao, F. Zhang, and J. Liu, “A spatiotemporal analysis of the robustness of high-speed rail network in China,” _Transportation Research Part D: Transport and Environment_ , vol. 89, p. 102584, 2020.
  * [191] T. Li and L. Rong, “A comprehensive method for the robustness assessment of high-speed rail network with operation data: A case in China,” _Transportation Research Part A: Policy and Practice_ , vol. 132, pp. 666–681, 2020.
  * [192] O. Lordan and J. M. Sallan, “Dynamic measures for transportation networks,” _PLoS One_ , vol. 15, no. 12, p. e0242875, 2020.
  * [193] W. Zhu, K. Liu, M. Wang, and X. Yan, “Enhancing robustness of metro networks using strategic defense,” _Physica A: Statistical Mechanics and Its Applications_ , vol. 503, pp. 1081–1091, 2018.
  * [194] A. De-Los-Santos, G. Laporte, J. A. Mesa, and F. Perea, “Evaluating passenger robustness in a rail transit network,” _Transportation Research Part C: Emerging Technologies_ , vol. 20, no. 1, pp. 34–46, 2012.
  * [195] S. Hu and G. Li, “TMSE: A topology modification strategy to enhance the robustness of scale-free wireless sensor networks,” _Computer Communications_ , vol. 157, pp. 53–63, 2020.
  * [196] J. Guo, F. Liu, J. Wang, J. Lin, and S. Mei, “Toward efficient cascading outage simulation and probability analysis in power systems,” _IEEE Transactions on Power Systems_ , vol. 33, no. 3, pp. 2370–2382, 2017.
  * [197] H. Tu, Y. Xia, H. H.-C. Iu, and X. Chen, “Optimal robustness in power grids from a network science perspective,” _IEEE Transactions on Circuits and Systems II: Express Briefs_ , vol. 66, no. 1, pp. 126–130, 2018.
  * [198] T. Qiu, N. Chen, and S. Zhang, _Robustness Optimization for IoT Topology_. Springer, 2022.