|
bgneal@23
|
1 """This program performs item 4 in 4.4 exercise 4.
|
|
bgneal@23
|
2
|
|
bgneal@23
|
3 "Make a graph that replicates the line marked C(p)/C(0) in Figure 2 of the
|
|
bgneal@23
|
4 paper. In other words, confirm that the clustering coefficient drops off slowly
|
|
bgneal@23
|
5 for small values of p."
|
|
bgneal@23
|
6
|
|
bgneal@23
|
7 """
|
|
bgneal@23
|
8 import matplotlib.pyplot as pyplot
|
|
bgneal@23
|
9
|
|
bgneal@23
|
10 from Graph import Vertex
|
|
bgneal@23
|
11 from SmallWorldGraph import SmallWorldGraph
|
|
bgneal@23
|
12
|
|
bgneal@25
|
13 # Use Dijkstra or Floyd-Warshall to compute L
|
|
bgneal@26
|
14 DIJKSTRA = True
|
|
bgneal@23
|
15
|
|
bgneal@23
|
16 # compute C(0)
|
|
bgneal@23
|
17 n = 1000
|
|
bgneal@23
|
18 k = 10
|
|
bgneal@23
|
19 vs = [Vertex(str(i)) for i in range(n)]
|
|
bgneal@23
|
20 g = SmallWorldGraph(vs, k, 0.0)
|
|
bgneal@23
|
21 c0 = g.clustering_coefficient()
|
|
bgneal@26
|
22 l0 = g.big_l3() if DIJKSTRA else g.big_l2()
|
|
bgneal@24
|
23 print 'c0 =', c0, 'l0 =', l0
|
|
bgneal@23
|
24
|
|
bgneal@23
|
25 # compute data
|
|
bgneal@25
|
26 p_vals = [0.0001, 0.0002, 0.0004, # 0.0006, 0.0008,
|
|
bgneal@24
|
27 0.001, 0.002, 0.004, # 0.006, 0.008,
|
|
bgneal@24
|
28 0.01, 0.02, 0.04, # 0.06, 0.08,
|
|
bgneal@24
|
29 0.1, 0.2, 0.4, # 0.6, 0.8,
|
|
bgneal@23
|
30 1.0]
|
|
bgneal@23
|
31
|
|
bgneal@23
|
32 c_vals = []
|
|
bgneal@24
|
33 l_vals = []
|
|
bgneal@23
|
34 for p in p_vals:
|
|
bgneal@23
|
35 g = SmallWorldGraph(vs, k, p)
|
|
bgneal@23
|
36 c_vals.append(g.clustering_coefficient() / c0)
|
|
bgneal@26
|
37 l = g.big_l3() if DIJKSTRA else g.big_l2()
|
|
bgneal@25
|
38 l_vals.append(l / l0)
|
|
bgneal@25
|
39
|
|
bgneal@25
|
40 p_vals.insert(0, 0.0)
|
|
bgneal@25
|
41 c_vals.insert(0, 1.0)
|
|
bgneal@25
|
42 l_vals.insert(0, 1.0)
|
|
bgneal@23
|
43
|
|
bgneal@23
|
44 # plot graph
|
|
bgneal@23
|
45 pyplot.clf()
|
|
bgneal@23
|
46 pyplot.xscale('log')
|
|
bgneal@28
|
47 pyplot.yscale('linear')
|
|
bgneal@23
|
48 pyplot.title('')
|
|
bgneal@23
|
49 pyplot.xlabel('p')
|
|
bgneal@23
|
50 pyplot.ylabel('C(p)/C(0)')
|
|
bgneal@24
|
51 pyplot.plot(p_vals, c_vals, label='C(p)/C(0)', color='green', linewidth=3)
|
|
bgneal@24
|
52 pyplot.plot(p_vals, l_vals, label='L(p)/L(0)', color='blue', linewidth=3)
|
|
bgneal@28
|
53 pyplot.legend(loc='lower left')
|
|
bgneal@23
|
54 pyplot.show()
|
