7. Network robustness#
import networkx as nx
import seaborn as sns
%pylab inline
%pylab is deprecated, use %matplotlib inline and import the required libraries.
Populating the interactive namespace from numpy and matplotlib
/Users/maxime/.pyenv/versions/venv_xgi/lib/python3.9/site-packages/IPython/core/magics/pylab.py:162: UserWarning: pylab import has clobbered these variables: ['zipf']
`%matplotlib` prevents importing * from pylab and numpy
warn("pylab import has clobbered these variables: %s" % clobbered +
7.1. Simulating random and targeted attacks to a network#
Resilience is the ability to provide and maintain an acceptable level of service in the face of faults and challenges to normal operation. Threats and challenges for services can range from simple misconfiguration over large scale natural disasters to targeted attacks.
We define a function that performs a random or targeted attack to a network according to a given strategy (random, degree based, betweenness based, etc. )
def net_attack(graph, ranked_nodes):
# here we store the tuples: (%removed nodes, size of gcc)
fraction_removed = []
graph1 = graph.copy()
nnodes = len(ranked_nodes)
n = 0
gcc = list(nx.connected_components(graph1))[0]
gcc_size = float(len(gcc)) / nnodes
fraction_removed.append((float(n) / nnodes, gcc_size))
while gcc_size > 0.01:
# we start from the end of the list!
graph1.remove_node(ranked_nodes.pop())
gcc = list(nx.connected_components(graph1))[0]
gcc_size = float(len(gcc)) / nnodes
n += 1
fraction_removed.append((float(n) / nnodes, gcc_size))
return fraction_removed
7.2. Robustness of the US airport network#
7.2.1. Random attack#
filepath_air = "./../datasets/USairport_2010.txt"
G = nx.Graph()
fh = open(filepath_air, "r")
for line in fh.readlines():
s = line.strip().split()
G.add_edge(int(s[0]), int(s[1]))
fh.close()
airport_nodes = list(G.nodes())
resilience_random = net_attack(G, airport_nodes)
7.2.2. Betweenness based attack#
from operator import itemgetter
airport_nodes_betw = []
betw = nx.betweenness_centrality(G)
for i in sorted(betw.items(), key=itemgetter(1)):
airport_nodes_betw.append(i[0])
resilience_betw = net_attack(G, airport_nodes_betw)
7.2.3. Degree based attack#
airport_nodes_degree = []
deg = dict(G.degree())
for i in sorted(deg.items(), key=itemgetter(1)):
airport_nodes_degree.append(i[0])
resilience_deg = net_attack(G, list(airport_nodes_degree))
Let’s compare the results.
x = [k[0] for k in resilience_random]
y = [k[1] for k in resilience_random]
x1 = [k[0] for k in resilience_deg]
y1 = [k[1] for k in resilience_deg]
x2 = [k[0] for k in resilience_betw]
y2 = [k[1] for k in resilience_betw]
plt.figure(figsize=(10, 7))
plt.plot(x, y, label="random attack")
plt.plot(x1, y1, label="degree based")
plt.plot(x2, y2, label="betw based")
plt.xlabel("$f_{c}$", fontsize=22)
plt.ylabel("$LCC$", fontsize=22)
plt.xticks(fontsize=20)
plt.yticks(fontsize=22)
plt.legend(loc="upper right", fontsize=20)
<matplotlib.legend.Legend at 0x13fe21fa0>
Real networks such as the air transport network are vulnerable to targeted attacks.
7.3. Robustness of the Erdos-Renyi random network#
ER = nx.fast_gnp_random_graph(2000, 0.012)
ER_nodes = list(ER.nodes())
# we rank the nodes by degree
ER_nodes_deg = [i for i, d in sorted(dict(ER.degree()).items(), key=itemgetter(1))]
ER_betw = nx.betweenness_centrality(ER)
ER_nodes_betw = [i for i, b in sorted(dict(ER_betw).items(), key=itemgetter(1))]
resilience_random = net_attack(ER, ER_nodes)
resilience_deg = net_attack(ER, ER_nodes_deg)
resilience_betw = net_attack(ER, ER_nodes_betw)
x = [k[0] for k in resilience_random]
y = [k[1] for k in resilience_random]
x1 = [k[0] for k in resilience_deg]
y1 = [k[1] for k in resilience_deg]
x2 = [k[0] for k in resilience_betw]
y2 = [k[1] for k in resilience_betw]
plt.figure(figsize=(10, 7))
plt.plot(x, y, label="random attack")
plt.plot(x1, y1, label="degree based")
plt.plot(x2, y2, label="betw based")
plt.xlabel("$f_{c}$", fontsize=22)
plt.ylabel("$LCC$", fontsize=22)
plt.xticks(fontsize=20)
plt.yticks(fontsize=20)
plt.legend(loc="upper right", fontsize=22)
<matplotlib.legend.Legend at 0x105526490>
Random networks such as the E-R network are not vulnerable to targeted attacks.
7.4. Robustness of Barabasi-Albert network#
BA = nx.barabasi_albert_graph(2000, 3)
BA_nodes = list(BA.nodes())
# we rank the nodes by degree
BA_nodes_deg = [i for i, d in sorted(dict(BA.degree()).items(), key=itemgetter(1))]
BA_betw = nx.betweenness_centrality(BA)
BA_nodes_betw = [i for i, b in sorted(dict(BA_betw).items(), key=itemgetter(1))]
resilience_random = net_attack(BA, BA_nodes)
resilience_deg = net_attack(BA, BA_nodes_deg)
resilience_betw = net_attack(BA, BA_nodes_betw)
x = [k[0] for k in resilience_random]
y = [k[1] for k in resilience_random]
x1 = [k[0] for k in resilience_deg]
y1 = [k[1] for k in resilience_deg]
x2 = [k[0] for k in resilience_betw]
y2 = [k[1] for k in resilience_betw]
plt.figure(figsize=(10, 7))
plt.plot(x, y, label="random attack")
plt.plot(x1, y1, label="degree based")
plt.plot(x2, y2, label="betw based")
plt.xlabel("$f_{c}$", fontsize=22)
plt.ylabel("$LCC$", fontsize=22)
plt.xticks(fontsize=20)
plt.yticks(fontsize=20)
plt.legend(loc="upper right", fontsize=22)
<matplotlib.legend.Legend at 0x13ad99a00>
from scipy.stats import zipf
a = 2.5
seq = zipf.rvs(a, loc=1, size=10000)
if np.sum(seq) % 2 != 0:
seq[0] = seq[0] + 1
gs = nx.configuration_model(seq[:2000])
# we rank the nodes by degree
gs_nodes = list(gs.nodes())
gs_nodes_deg = [i for i, d in sorted(dict(gs.degree()).items(), key=itemgetter(1))]
gs_betw = nx.betweenness_centrality(gs)
gs_nodes_betw = [i for i, b in sorted(dict(gs_betw).items(), key=itemgetter(1))]
resilience_random = net_attack(gs, gs_nodes)
resilience_deg = net_attack(gs, gs_nodes_deg)
resilience_betw = net_attack(gs, gs_nodes_betw)
x = [k[0] for k in resilience_random]
y = [k[1] for k in resilience_random]
x1 = [k[0] for k in resilience_deg]
y1 = [k[1] for k in resilience_deg]
x2 = [k[0] for k in resilience_betw]
y2 = [k[1] for k in resilience_betw]
plt.figure(figsize=(10, 7))
plt.plot(x, y, label="random attack")
plt.plot(x1, y1, label="degree based")
plt.plot(x2, y2, label="betw based")
plt.xlabel("$f_{c}$", fontsize=22)
plt.ylabel("$LCC$", fontsize=22)
plt.xticks(fontsize=20)
plt.yticks(fontsize=20)
plt.legend(loc="upper right", fontsize=22)
<matplotlib.legend.Legend at 0x13a4679d0>
