Mercurial > public > think_complexity

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