Network Models: Small World

In [ ]:
import numpy as np
import matplotlib.pyplot as plt
plt.xkcd()
import networkx as nx
%matplotlib inline

During this seminar we will work with Watts and Strogatz model. Again, the idea of the model:

  1. Start with regular lattice with N nodes, K nearest neighbours
  2. For each node take every edge and rewire it with probability $p$, assuming that there is no loops and edge duplications
Task
  1. Implement rewind(G, p) function that takes graph G and probability p as input. The function should produce a graph after step 2 of the model above.
  2. Run experiments for various values of p, compute and show
    • average path length
    • clustering coefficients (transitivity)
    • degree distribution
In [ ]:
def gen_regular_graph(n, k):
    G = nx.Graph()
    nodes = list(range(n))
    for j in range(1, k // 2+1):
        targets = nodes[j:] + nodes[0:j] # first j nodes are now last in list
        G.add_edges_from(zip(nodes,targets))
    return G

def degree_distr(k, bins = 100):
    yh, binEdges = np.histogram(k, bins)
    bincenters = 0.5*(binEdges[1:]+binEdges[:-1])
    return yh, bincenters