Newer
Older
from edge_addition import *
RANDOM_REWIRE = 20 # Remove and add random edge
PREFERENTIAL_REW = 21 # Disconnect a random edge from a highest-degree node, and reconnect that edge to a random node
PREFERENTIAL_RANDOM = 22 # Choose a random edge, disconnect it from its higher-degree node, and reconnect that edge to a random node.
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
def random_rewire(g):
g = remove_random_edge(g)
g = recover.add_random_edge(g)
return g
def pref_rewire(g):
nodes = sorted(g.degree, key=lambda x: x[1], reverse=True)
node_highest_degree = nodes[0][0]
chosen_edge = random.choice(list(g.edges(node_highest_degree)))
g.remove_edge(chosen_edge[0], chosen_edge[1])
possible_nodes = set(g.nodes())
neighbours = list(g.neighbors(node_highest_degree)) + [node_highest_degree]
possible_nodes.difference_update(neighbours) # remove the first node and all its neighbours from the candidates
second_node = random.choice(list(possible_nodes))
g.add_edge(node_highest_degree, second_node)
return g
def pref_random_rewire(g):
edges = list(g.edges)
chosen_edge = random.choice(edges)
node1 = chosen_edge[0]
node2 = chosen_edge[1]
g.remove_edge(chosen_edge[0], chosen_edge[1])
random_node = random.choice(list(g.nodes()))
if g.degree[node1] > g.degree[node2]:
while g.has_edge(node2, random_node):
random_node = random.choice(list(g.nodes()))
g.add_edge(node2, random_node)
else:
while g.has_edge(node1, random_node):
random_node = random.choice(list(g.nodes()))
g.add_edge(node1, random_node)
return g
def rewire_to_initial_diameter_lcc_ratio(initial_diameter, initial_lcc, attacked_graph, recovery_option=RANDOM_REWIRE):
d, lcc, av_cc = get_robustness(attacked_graph)
num_edges = 0
new_d_lcc = d/lcc
recovered_graph = attacked_graph.copy()
size = recovered_graph.size()
# Give up once robustness doesn't increase or too many edges rewired
while new_d_lcc > initial_d_lcc and num_edges < size*2 and stop < size*0.1:
recovered_graph = rewire_edge(recovery_option, recovered_graph)
num_edges += 1
d, lcc, av_cc = get_robustness(recovered_graph)
new_d_lcc = d / lcc
stop = 0 if old_d_lcc < new_d_lcc else stop + 1
# print_robustness(recovered_graph)
# print("\nNumber of edges needed to recover:", num_edges)
return recovered_graph, num_edges
def rewire_edge(recovery_option, recovered_graph):
# Select respective recovery option
if recovery_option == RANDOM_REWIRE:
recovered_graph = random_rewire(recovered_graph)