IEEE Circuits and Systems Magazine - Q1 2023 - 13

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.
I. Introduction
N
etwork 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 [12], [14], [15], 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 article, 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 [13], [14].
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.
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
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, SAR, China (e-mail: eegchen@cityu.edu.hk).
FIRST QUARTER 2023
IEEE CIRCUITS AND SYSTEMS MAGAZINE
13
IEEE Circuits and Systems Magazine - Q1 2023

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