IEEE Circuits and Systems Magazine - Q1 2023 - 20

Given an N-node network, which is subject to nodeattacks,
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].
3) 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 noncritical [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.
4) Computational Intelligence-based Attack Strategies
Searching for a desirable attack sequence from the large
number of possible choices is an NP-hard combinatorial
20
IEEE CIRCUITS AND SYSTEMS MAGAZINE
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 Section 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
algorithmbased strategies aim at finding the most
destructive attack sequence for the given networks,
while machine learningbased strategies also pursue the
generalizability to unknown data, for which greater computational
cost is needed in the training stage.
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].
1) 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
FIRST QUARTER 2023
IEEE Circuits and Systems Magazine - Q1 2023

Table of Contents for the Digital Edition of IEEE Circuits and Systems Magazine - Q1 2023
