bgneal@23: """This program performs item 4 in 4.4 exercise 4.
bgneal@23: 
bgneal@23: "Make a graph that replicates the line marked C(p)/C(0) in Figure 2 of the
bgneal@23: paper. In other words, confirm that the clustering coefficient drops off slowly
bgneal@23: for small values of p."
bgneal@23: 
bgneal@23: """
bgneal@23: import matplotlib.pyplot as pyplot
bgneal@23: 
bgneal@23: from Graph import Vertex
bgneal@23: from SmallWorldGraph import SmallWorldGraph
bgneal@23: 
bgneal@25: # Use Dijkstra or Floyd-Warshall to compute L
bgneal@26: DIJKSTRA = True
bgneal@23: 
bgneal@23: # compute C(0)
bgneal@23: n = 1000
bgneal@23: k = 10
bgneal@23: vs = [Vertex(str(i)) for i in range(n)]
bgneal@23: g = SmallWorldGraph(vs, k, 0.0)
bgneal@23: c0 = g.clustering_coefficient()
bgneal@26: l0 = g.big_l3() if DIJKSTRA else g.big_l2()
bgneal@24: print 'c0 =', c0, 'l0 =', l0
bgneal@23: 
bgneal@23: # compute data
bgneal@25: p_vals = [0.0001, 0.0002, 0.0004, # 0.0006, 0.0008,
bgneal@24:           0.001, 0.002, 0.004, # 0.006, 0.008,
bgneal@24:           0.01, 0.02, 0.04, # 0.06, 0.08,
bgneal@24:           0.1, 0.2, 0.4, # 0.6, 0.8,
bgneal@23:           1.0]
bgneal@23: 
bgneal@23: c_vals = []
bgneal@24: l_vals = []
bgneal@23: for p in p_vals:
bgneal@23:     g = SmallWorldGraph(vs, k, p)
bgneal@23:     c_vals.append(g.clustering_coefficient() / c0)
bgneal@26:     l = g.big_l3() if DIJKSTRA else g.big_l2()
bgneal@25:     l_vals.append(l / l0)
bgneal@25: 
bgneal@25: p_vals.insert(0, 0.0)
bgneal@25: c_vals.insert(0, 1.0)
bgneal@25: l_vals.insert(0, 1.0)
bgneal@23: 
bgneal@23: # plot graph
bgneal@23: pyplot.clf()
bgneal@23: pyplot.xscale('log')
bgneal@28: pyplot.yscale('linear')
bgneal@23: pyplot.title('')
bgneal@23: pyplot.xlabel('p')
bgneal@23: pyplot.ylabel('C(p)/C(0)')
bgneal@24: pyplot.plot(p_vals, c_vals, label='C(p)/C(0)', color='green', linewidth=3)
bgneal@24: pyplot.plot(p_vals, l_vals, label='L(p)/L(0)', color='blue', linewidth=3)
bgneal@28: pyplot.legend(loc='lower left')
bgneal@23: pyplot.show()