Skip to content
Snippets Groups Projects
rewire.py 2.98 KiB
Newer Older
s1922262's avatar
s1922262 committed
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
s1922262's avatar
s1922262 committed
PREFERENTIAL_RANDOM = 22     # Choose a random edge, disconnect it from its higher-degree node, and reconnect that edge to a random node.
NO_REWIRE = 200
s1922262's avatar
s1922262 committed


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

    old_d_lcc = initial_diameter/initial_lcc
s1922262's avatar
s1922262 committed
    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
s1922262's avatar
s1922262 committed
    while new_d_lcc > initial_d_lcc and num_edges < size*2 and stop < size*0.1:
s1922262's avatar
s1922262 committed
        recovered_graph = rewire_edge(recovery_option, recovered_graph)
        num_edges += 1
        d, lcc, av_cc = get_robustness(recovered_graph)
        old_d_lcc = new_d_lcc
s1922262's avatar
s1922262 committed
        new_d_lcc = d / lcc
        stop = 0 if old_d_lcc < new_d_lcc else stop + 1
s1922262's avatar
s1922262 committed

    # 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)
    elif recovery_option == PREFERENTIAL_REW:
s1922262's avatar
s1922262 committed
        recovered_graph = pref_rewire(recovered_graph)
    elif recovery_option == PREFERENTIAL_RANDOM:
        recovered_graph = pref_random_rewire(recovered_graph)
    else:
        raise Exception("Incorrect rewiring option specified")

    return recovered_graph