%matplotlib inline

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
import matplotlib.animation as animation

from JSAnimation.IPython_display import display_animation, anim_to_html

n = 256
# g = nx.erdos_renyi_graph(n, 0.05)
# g = nx.erdos_renyi_graph(n, 1/(n-1)+0.001)
# g = nx.watts_strogatz_graph(n, 4, 0.1)
# g = nx.barabasi_albert_graph(n, 2)
# g = nx.powerlaw_cluster_graph(n, 2, 0.01)
# g = nx.relaxed_caveman_graph(16, 16, 0.12)
# g = nx.read_graphml("risk.graphml").to_undirected()
g = nx.read_graphml("USAir97.graphml").to_undirected()
# g = nx.read_graphml("bridge.graphml").to_undirected()

print("Nodes:", len(g.nodes))
# pos = nx.fruchterman_reingold_layout(g, k=0.1)

# The KK layout algorithm takes a minute
pos = nx.kamada_kawai_layout(g)

Nodes: 332

for x in list(g.nodes(data=True))[:5]:
    print(x)

('331', {'label': 'Pago Pago Intl', 'size': 100.0, 'r': 0, 'g': 0, 'b': 0, 'x': -39.03929, 'y': 60.31818})
('330', {'label': 'Babelthuap/Koror', 'size': 75.671394, 'r': 0, 'g': 0, 'b': 0, 'x': -71.759094, 'y': 35.98957})
('329', {'label': 'Guam Intll', 'size': 68.80587, 'r': 0, 'g': 0, 'b': 0, 'x': -65.63294, 'y': 29.124046})
('328', {'label': 'Rota Intl', 'size': 68.0313, 'r': 0, 'g': 0, 'b': 0, 'x': -65.363014, 'y': 28.349478})
('332', {'label': 'West Tinian', 'size': 67.11589, 'r': 0, 'g': 0, 'b': 0, 'x': -65.14003, 'y': 27.434069})

Immunization

infected_map = {x:False for x in g.nodes}
immune_map = {x:False for x in g.nodes}

time_steps = 0

trans_p = 0.75

# Immunize
for item in [
"8",
]:
    immune_map[item] = True

# Infect
for item in [
"261",
]:
    infected_map[item] = True

last_infected_count = sum([1 for n, i in infected_map.items() if i])
infected_counts = [last_infected_count]

node_dict = g.nodes(data=True)
   
print("Inoculated:")
for k in [inf for inf in immune_map if immune_map[inf] == True]:
    info = node_dict[k]
    if ( "label" in info ):
        print(k, info["label"])
    else:
        print(k)
    
print("\nInfected:")
for k in [inf for inf in infected_map if infected_map[inf] == True]:
    info = node_dict[k]
    if ( "label" in info ):
        print(k, info["label"])
    else:
        print(k)

Inoculated:
8 Anchorage Intl

Infected:
261 Dallas/Fort Worth Intl

Before Propagation

# Build the graph and set its size
graph_fig = plt.figure()
graph_fig.set_figheight(10)
graph_fig.set_figwidth(15)
ax = graph_fig.gca()

# Update our timestep
time_steps += 1

# The edges don't change, so we want to go ahead and draw them once
nx.draw_networkx_edges(g, pos, ax=ax)
nx.draw_networkx_labels(g, pos, ax=ax)

# Get colors for infected nodes
cmap = plt.get_cmap("rainbow")

# Update infected colors
colors = [1.0 if infected_map[x] else 0.5 if immune_map[x] else 0.0 for x in g.nodes]

# Draw this frame
nx.draw_networkx_nodes(g, pos, alpha=0.75, node_color=colors, cmap=cmap, ax=ax, vmin=0.0, vmax=1.0)

plt.show()

Step-by-Step Propagation

# Build the graph and set its size
graph_fig = plt.figure()
graph_fig.set_figheight(10)
graph_fig.set_figwidth(15)
ax = graph_fig.gca()

# Update our timestep
time_steps += 1

# The edges don't change, so we want to go ahead and draw them once
nx.draw_networkx_edges(g, pos, ax=ax)

# Get colors for infected nodes
cmap = plt.get_cmap("rainbow")
    
# For each infected node, find and infect uninfected neighbors
for ill_node in [n for n, i in infected_map.items() if i]:
    for neighbor in g.neighbors(ill_node):

        # Can't infect immune neighbors
        if ( immune_map[neighbor] == True ):
            continue

        # probabilistic transmission
        if ( np.random.random() < trans_p ):
            infected_map[neighbor] = True

# Update infected colors
colors = [1.0 if infected_map[x] else 0.5 if immune_map[x] else 0.0 for x in g.nodes]

# Draw this frame
nx.draw_networkx_nodes(g, pos, alpha=0.75, node_color=colors, cmap=cmap, ax=ax, vmin=0.0, vmax=1.0)

# Check if we have infected the whole graph or reached a steady state/fixed point
infected_count = sum([1 for n, i in infected_map.items() if i])
infected_counts.append(infected_count)
if ( infected_count == len(g.nodes) ):
    print("Total Infection!")

print("Time Step:", time_steps, "Infected Percentage:", infected_count / len(g.nodes))
    

Time Step: 2 Infected Percentage: 0.2680722891566265

Carry Forward

# Build the graph and set its size
graph_fig = plt.figure()
graph_fig.set_figheight(10)
graph_fig.set_figwidth(15)
ax = graph_fig.gca()

# The edges don't change, so we want to go ahead and draw them once
nx.draw_networkx_edges(g, pos, ax=ax)

# Get colors for infected nodes
cmap = plt.get_cmap("rainbow")
colors = [1.0 if infected_map[x] else 0.5 if immune_map[x] else 0.0 for x in g.nodes]

# Draw the first frame of our animation
ims = [
    (nx.draw_networkx_nodes(g, pos, alpha=0.75, node_color=colors, cmap=cmap, ax=ax, vmin=0.0, vmax=1.0),)
]

# Draw at most *horizon* fames, keeping track of changes in the infected count
#  We'll stop if we don't see the infected count change.
horizon = 16

# For up to *horizon* time steps, infect nodes
for add in np.arange(horizon):
    
    # For each infected node, find and infect uninfected neighbors
    for ill_node in [n for n, i in infected_map.items() if i]:
        for neighbor in g.neighbors(ill_node):
            
            # Can't infect immune neighbors
            if ( immune_map[neighbor] == True ):
                continue
            
            # probabilistic transmission
            if ( np.random.random() < trans_p ):
                infected_map[neighbor] = True
    
    # Update infected colors
    colors = [1.0 if infected_map[x] else 0.5 if immune_map[x] else 0.0 for x in g.nodes]
    
    # Add the new frame of colored nodes to our frames
    ims.append(
        (nx.draw_networkx_nodes(g, pos, alpha=0.75, node_color=colors, cmap=cmap, ax=ax, vmin=0.0, vmax=1.0),)
    )
    
    # Check if we have infected the whole graph or reached a steady state/fixed point
    infected_count = sum([1 for n, i in infected_map.items() if i])
    if ( infected_count == len(g.nodes) ):
        print("Total Infection After:", add+1)
        break

    last_infected_count = infected_count
    infected_counts.append(last_infected_count)

print("Infected Percentage:", infected_counts[-1] / len(g.nodes))
    
im_ani = animation.ArtistAnimation(graph_fig, ims, interval=1000, repeat_delay=3000,
                                   blit=True)

display_animation(im_ani)

Infected Percentage: 0.9186746987951807

– +

Once Loop Reflect

plt.plot(infected_counts)
plt.xlabel("Time Steps")
plt.ylabel("Infected Count")

plt.show()

Centralities

top_k = 15

print("Degree Centrality:")
cents = sorted(nx.degree_centrality(g).items(), key=lambda x: x[1], reverse=True)
for node, rank in cents[:top_k]:
    print("\t", node, rank)
print("\t ...")
for node, rank in cents[-5:]:
    print("\t", node, rank)
    
print("Closeness Centrality:")
cents = sorted(nx.closeness_centrality(g).items(), key=lambda x: x[1], reverse=True)
for node, rank in cents[:top_k]:
    print("\t", node, rank)
print("\t ...")
for node, rank in cents[-5:]:
    print("\t", node, rank)
    
print("Betweenness Centrality:")
cents = sorted(nx.betweenness_centrality(g).items(), key=lambda x: x[1], reverse=True)
for node, rank in cents[:top_k]:
    print("\t", node, rank)
print("\t ...")
for node, rank in cents[-5:]:
    print("\t", node, rank)
    
print("Eigenvector Centrality:")
cents = sorted(nx.eigenvector_centrality(g).items(), key=lambda x: x[1], reverse=True)
for node, rank in cents[:top_k]:
    print("\t", node, rank)
print("\t ...")
for node, rank in cents[-5:]:
    print("\t", node, rank)