IEEE Circuits and Systems Magazine - Q1 2023 - 15

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.
Section 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 Section II-B. Various attack strategies and
robustness estimation methods are reviewed in Sections
II-C and II-D, respectively. Finally, Section II-E presents
some robustness optimization technicians based
on a posteriori measures.
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
where fi
=⋅i ()
=
1 ∑
1
K
wf i
K
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; wi represents
the weight of fi
work functions are concerned, such as the connectivity,
controllability or communication ability, to be discussed
below,
f ⋅() will be specified accordingly. The weighting
FIRST QUARTER 2023
,
(1)
Figure 2. Widely-used a priori and a posteriori robustness
measures of the three network functions.
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 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.
1) 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 nodemalfunctioning
failures or removals, the connectivity
robustness is evaluated by calculating the remaining
LCC after each attack [15], formulated as follows:
R ∑∑ ,
L
1 =
11 ()
L () =
N−1
ni
N
i=0
N
i=0
where niL () and NiL () represent the proportion and
the number of nodes in the remaining LCC after a total
number of i nodes have been attacked. Specifically,
fi NiL
and wNi =1/
N−1
Ni
N
(2)
() = () measures the remaining connectivity
is the uniform weight, assuming that the
() in calculating R. When different netmalfunctioned
nodes are still counted as a part of the
N-node networks.
In contrast, if the attacked nodes are removed
from the network, its
calculated by
connectivity robustness
R2 =
1
N−1
N∑
i=0
IEEE CIRCUITS AND SYSTEMS MAGAZINE
15
L
()
−
Ni
Ni
,
is
(3)
IEEE Circuits and Systems Magazine - Q1 2023

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