Mercurial > public > think_complexity

comparison SmallWorldGraph.py @ 23:74c9d126bd05

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Working on the SmallWorldGraph exercises.
author Brian Neal <bgneal@gmail.com>
date Wed, 02 Jan 2013 16:50:55 -0600
parents
children 5c2c4ce095ef
comparison
equal deleted inserted replaced
22:84e183b40c63 23:74c9d126bd05
1 """This module contains the SmallWorldGraph class for 4.4, exercise 4.
2
3 """
4 import itertools
5 import random
6
7 from Graph import Edge
8 from RandomGraph import RandomGraph
9
10
11 class SmallWorldGraph(RandomGraph):
12 """A small world graph for 4.4, exercise 4 in Think Complexity."""
13
14 def __init__(self, vs, k, p):
15 """Create a small world graph. Parameters:
16 vs - a list of vertices
17 k - regular graph parameter k: the number of edges between vertices
18 p - probability for rewiring.
19
20 First a regular graph is created from the list of vertices and parameter
21 k, which specifies how many edges each vertex should have. Then the
22 rewire() method is called with parameter p to rewire the graph according
23 to the algorithm by Watts and Strogatz.
24
25 """
26 super(SmallWorldGraph, self).__init__(vs=vs)
27 self.add_regular_edges(k)
28 self.rewire(p)
29
30 def rewire(self, p):
31 """Assuming the graph is initially a regular graph, rewires the graph
32 using the Watts and Strogatz algorithm.
33
34 """
35 # We iterate over the edges in a random order:
36 edges = self.edges()
37 random.shuffle(edges)
38 vertices = self.vertices()
39
40 for e in edges:
41 if random.random() < p:
42 v, w = e # remember the 2 vertices this edge connected
43 self.remove_edge(e) # remove from graph
44
45 # pick another vertex to connect to v; duplicate edges are
46 # forbidden
47 while True:
48 x = random.choice(vertices)
49 if v is not x and not self.get_edge(v, x):
50 self.add_edge(Edge(v, x))
51 break
52
53 def clustering_coefficient(self):
54 """Compute the clustering coefficient for this graph as defined by Watts
55 and Strogatz.
56
57 """
58 cv = {}
59 for v in self:
60 # consider a node and its neighbors
61 nodes = self.out_vertices(v)
62 nodes.append(v)
63
64 # compute the maximum number of possible edges between these nodes
65 # if they were all connected to each other:
66 n = len(nodes)
67 if n == 1:
68 # edge case of only 1 node; handle this case to avoid division
69 # by zero in the general case
70 cv[v] = 1.0
71 continue
72
73 possible = n * (n - 1) / 2.0
74
75 # now compute how many edges actually exist between the nodes
76 actual = 0
77 for x, y in itertools.combinations(nodes, 2):
78 if self.get_edge(x, y):
79 actual += 1
80
81 # the fraction of actual / possible is this nodes C sub v value
82 cv[v] = actual / possible
83
84 # The clustering coefficient is the average of all C sub v values
85 if len(cv):
86 return sum(cv.values()) / float(len(cv))
87 return 0.0