Mercurial > public > think_complexity

annotate ch4ex4.py @ 24:5c2c4ce095ef

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
A stab at the L(p)/L(0) plot. I still don't quite get how the graphs in the Watts and Strogatz paper were generated. My results have basically the same shape, but don't converge to 0. I'm not sure how this is possible if the rewire function does not remove edges.
author Brian Neal <bgneal@gmail.com>
date Thu, 03 Jan 2013 18:41:13 -0600
parents 74c9d126bd05
children a46783561538
rev   line source
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 random
bgneal@23 9 import matplotlib.pyplot as pyplot
bgneal@23 10
bgneal@23 11 from Graph import Vertex
bgneal@23 12 from SmallWorldGraph import SmallWorldGraph
bgneal@23 13
bgneal@23 14
bgneal@23 15 title = 'C(p)/C(0)'
bgneal@23 16
bgneal@23 17 # compute C(0)
bgneal@23 18 n = 1000
bgneal@23 19 k = 10
bgneal@23 20 vs = [Vertex(str(i)) for i in range(n)]
bgneal@23 21 g = SmallWorldGraph(vs, k, 0.0)
bgneal@23 22 c0 = g.clustering_coefficient()
bgneal@24 23 l0 = g.big_l()
bgneal@24 24 print 'c0 =', c0, 'l0 =', l0
bgneal@23 25
bgneal@23 26 # compute data
bgneal@24 27 p_vals = [# 0,
bgneal@24 28 0.0001, 0.0002, 0.0004, # 0.0006, 0.0008,
bgneal@24 29 0.001, 0.002, 0.004, # 0.006, 0.008,
bgneal@24 30 0.01, 0.02, 0.04, # 0.06, 0.08,
bgneal@24 31 0.1, 0.2, 0.4, # 0.6, 0.8,
bgneal@23 32 1.0]
bgneal@23 33
bgneal@23 34 c_vals = []
bgneal@24 35 l_vals = []
bgneal@23 36 for p in p_vals:
bgneal@23 37 g = SmallWorldGraph(vs, k, p)
bgneal@23 38 c_vals.append(g.clustering_coefficient() / c0)
bgneal@24 39 l_vals.append(g.big_l() / l0)
bgneal@23 40
bgneal@23 41 # plot graph
bgneal@23 42 pyplot.clf()
bgneal@23 43 pyplot.xscale('log')
bgneal@23 44 pyplot.yscale('log')
bgneal@23 45 pyplot.title('')
bgneal@23 46 pyplot.xlabel('p')
bgneal@23 47 pyplot.ylabel('C(p)/C(0)')
bgneal@24 48 pyplot.plot(p_vals, c_vals, label='C(p)/C(0)', color='green', linewidth=3)
bgneal@24 49 pyplot.plot(p_vals, l_vals, label='L(p)/L(0)', color='blue', linewidth=3)
bgneal@23 50 pyplot.legend(loc=4)
bgneal@23 51 pyplot.show()