# HG changeset patch
# User Brian Neal <bgneal@gmail.com>
# Date 1357167055 21600
# Node ID 74c9d126bd058f0a49d70039e322ab1975c37268
# Parent  84e183b40c63b8db87fe14f34c3d26c28dfb2a27
Working on the SmallWorldGraph exercises.

diff -r 84e183b40c63 -r 74c9d126bd05 SmallWorldGraph.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/SmallWorldGraph.py	Wed Jan 02 16:50:55 2013 -0600
@@ -0,0 +1,87 @@
+"""This module contains the SmallWorldGraph class for 4.4, exercise 4.
+
+"""
+import itertools
+import random
+
+from Graph import Edge
+from RandomGraph import RandomGraph
+
+
+class SmallWorldGraph(RandomGraph):
+    """A small world graph for 4.4, exercise 4 in Think Complexity."""
+
+    def __init__(self, vs, k, p):
+        """Create a small world graph. Parameters:
+            vs - a list of vertices
+            k - regular graph parameter k: the number of edges between vertices
+            p - probability for rewiring.
+
+        First a regular graph is created from the list of vertices and parameter
+        k, which specifies how many edges each vertex should have. Then the
+        rewire() method is called with parameter p to rewire the graph according
+        to the algorithm by Watts and Strogatz.
+
+        """
+        super(SmallWorldGraph, self).__init__(vs=vs)
+        self.add_regular_edges(k)
+        self.rewire(p)
+
+    def rewire(self, p):
+        """Assuming the graph is initially a regular graph, rewires the graph
+        using the Watts and Strogatz algorithm.
+
+        """
+        # We iterate over the edges in a random order:
+        edges = self.edges()
+        random.shuffle(edges)
+        vertices = self.vertices()
+
+        for e in edges:
+            if random.random() < p:
+                v, w = e    # remember the 2 vertices this edge connected
+                self.remove_edge(e)     # remove from graph
+
+                # pick another vertex to connect to v; duplicate edges are
+                # forbidden
+                while True:
+                    x = random.choice(vertices)
+                    if v is not x and not self.get_edge(v, x):
+                        self.add_edge(Edge(v, x))
+                        break
+
+    def clustering_coefficient(self):
+        """Compute the clustering coefficient for this graph as defined by Watts
+        and Strogatz.
+
+        """
+        cv = {}
+        for v in self:
+            # consider a node and its neighbors
+            nodes = self.out_vertices(v)
+            nodes.append(v)
+
+            # compute the maximum number of possible edges between these nodes
+            # if they were all connected to each other:
+            n = len(nodes)
+            if n == 1:
+                # edge case of only 1 node; handle this case to avoid division
+                # by zero in the general case
+                cv[v] = 1.0
+                continue
+
+            possible = n * (n - 1) / 2.0
+
+            # now compute how many edges actually exist between the nodes
+            actual = 0
+            for x, y in itertools.combinations(nodes, 2):
+                if self.get_edge(x, y):
+                    actual += 1
+
+            # the fraction of actual / possible is this nodes C sub v value
+            cv[v] = actual / possible
+
+        # The clustering coefficient is the average of all C sub v values
+        if len(cv):
+            return sum(cv.values()) / float(len(cv))
+        return 0.0
diff -r 84e183b40c63 -r 74c9d126bd05 ch4ex4.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/ch4ex4.py	Wed Jan 02 16:50:55 2013 -0600
@@ -0,0 +1,47 @@
+"""This program performs item 4 in 4.4 exercise 4.
+
+"Make a graph that replicates the line marked C(p)/C(0) in Figure 2 of the
+paper. In other words, confirm that the clustering coefficient drops off slowly
+for small values of p."
+
+"""
+import random
+import matplotlib.pyplot as pyplot
+
+from Graph import Vertex
+from SmallWorldGraph import SmallWorldGraph
+
+
+title = 'C(p)/C(0)'
+
+# compute C(0)
+n = 1000
+k = 10
+vs = [Vertex(str(i)) for i in range(n)]
+g = SmallWorldGraph(vs, k, 0.0)
+c0 = g.clustering_coefficient()
+print 'c0 =', c0
+
+# compute data
+p_vals = [0,
+          0.0001, 0.0002, 0.0004, 0.0006, 0.0008,
+          0.001, 0.002, 0.004, 0.006, 0.008,
+          0.01, 0.02, 0.04, 0.06, 0.08,
+          0.1, 0.2, 0.4, 0.6, 0.8,
+          1.0]
+
+c_vals = []
+for p in p_vals:
+    g = SmallWorldGraph(vs, k, p)
+    c_vals.append(g.clustering_coefficient() / c0)
+
+# plot graph
+pyplot.clf()
+pyplot.xscale('log')
+pyplot.yscale('log')
+pyplot.title('')
+pyplot.xlabel('p')
+pyplot.ylabel('C(p)/C(0)')
+pyplot.plot(p_vals, c_vals, label=title, color='green', linewidth=3)
+pyplot.legend(loc=4)
+pyplot.show()