# HG changeset patch # User Brian Neal # Date 1357867442 21600 # Node ID 305cc03c275006606d27a836a25b61d47a98f3a9 # Parent 10db8c3a6b830cace1369f901b9ded90f75aefa4 Chapter 5.5, exercise 6, #3: compute WS clustering coefficient and characteristic length on a BA model graph. diff -r 10db8c3a6b83 -r 305cc03c2750 Graph.py --- a/Graph.py Wed Jan 09 20:51:16 2013 -0600 +++ b/Graph.py Thu Jan 10 19:24:02 2013 -0600 @@ -6,10 +6,14 @@ Copyright 2011 Allen B. Downey. Distributed under the GNU General Public License at gnu.org/licenses/gpl.html. """ +import heapq import itertools from collections import deque, Counter +INFINITY = float('Inf') + + class GraphError(Exception): """Exception for Graph errors""" pass @@ -69,6 +73,14 @@ for e in es: self.add_edge(e) + def set_edge_length(self, n=1): + """Give each edge a length of n; this is used by the + shortest_path_tree() method. + + """ + for e in self.edges(): + e.length = n + def add_vertex(self, v): """Add a vertex to the graph.""" self[v] = {} @@ -257,6 +269,183 @@ return c + 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 + + def shortest_path_tree(self, source, hint=None): + """Finds the length of the shortest path from the source vertex to all + other vertices in the graph. This length is stored on the vertices as an + attribute named 'dist'. The algorithm used is Dijkstra's. + + hint: if provided, must be a dictionary mapping tuples to already known + shortest path distances. This can be used to speed up the algorithm. + + """ + if not hint: + hint = {} + + for v in self.vertices(): + v.dist = hint.get((source, v), INFINITY) + source.dist = 0 + + queue = [v for v in self.vertices() if v.dist < INFINITY] + sort_flag = True + while len(queue): + + if sort_flag: + queue.sort(key=lambda v: v.dist) + sort_flag = False + + v = queue.pop(0) + + # for each neighbor of v, see if we found a new shortest path + for w, e in self[v].iteritems(): + d = v.dist + e.length + if d < w.dist: + w.dist = d + queue.append(w) + sort_flag = True + + def shortest_path_tree2(self, source): + """Finds the length of the shortest path from the source vertex to all + other vertices in the graph. This length is stored on the vertices as an + attribute named 'dist'. The algorithm used is Dijkstra's with a Heap + used to sort/store pending nodes to be examined. + + """ + for v in self.vertices(): + v.dist = INFINITY + source.dist = 0 + + queue = [] + heapq.heappush(queue, (0, source)) + while len(queue): + + _, v = heapq.heappop(queue) + + # for each neighbor of v, see if we found a new shortest path + for w, e in self[v].iteritems(): + d = v.dist + e.length + if d < w.dist: + w.dist = d + heapq.heappush(queue, (d, w)) + + def all_pairs_floyd_warshall(self): + """Finds the shortest paths between all pairs of vertices using the + Floyd-Warshall algorithm. + + http://en.wikipedia.org/wiki/Floyd-Warshall_algorithm + + """ + vertices = self.vertices() + dist = {} + for i in vertices: + for j in vertices: + if i is j: + dist[i, j] = 0.0 + else: + e = self.get_edge(i, j) + dist[i, j] = e.length if e else INFINITY + + for k in vertices: + for i in vertices: + for j in vertices: + d_ik = dist[i, k] + d_kj = dist[k, j] + new_cost = d_ik + d_kj + if new_cost < dist[i, j]: + dist[i, j] = new_cost + + return dist + + def big_l(self): + """Computes the "big-L" value for the graph as per Watts & Strogatz. + + L is defined as the number of edges in the shortest path between + two vertices, averaged over all vertices. + + Uses the shortest_path_tree() method, called once for every node. + + """ + d = {} + for v in self.vertices(): + self.shortest_path_tree(v, d) + t = [((w, v), w.dist) for w in self.vertices() if v is not w] + d.update(t) + + if len(d): + return sum(d.values()) / float(len(d)) + return 0.0 + + def big_l2(self): + """Computes the "big-L" value for the graph as per Watts & Strogatz. + + L is defined as the number of edges in the shortest path between + two vertices, averaged over all vertices. + + Uses the all_pairs_floyd_warshall() method. + + """ + dist = self.all_pairs_floyd_warshall() + vertices = self.vertices() + result = [dist[i, j] for i in vertices for j in vertices if i is not j] + + if len(result): + return sum(result) / float(len(result)) + return 0.0 + + def big_l3(self): + """Computes the "big-L" value for the graph as per Watts & Strogatz. + + L is defined as the number of edges in the shortest path between + two vertices, averaged over all vertices. + + Uses the shortest_path_tree2() method, called once for every node. + + """ + d = {} + for v in self.vertices(): + self.shortest_path_tree2(v) + t = [((v, w), w.dist) for w in self.vertices() if v is not w] + d.update(t) + + if len(d): + return sum(d.values()) / float(len(d)) + return 0.0 + def main(script, *args): import pprint diff -r 10db8c3a6b83 -r 305cc03c2750 SmallWorldGraph.py --- a/SmallWorldGraph.py Wed Jan 09 20:51:16 2013 -0600 +++ b/SmallWorldGraph.py Thu Jan 10 19:24:02 2013 -0600 @@ -1,16 +1,12 @@ """This module contains the SmallWorldGraph class for 4.4, exercise 4. """ -import heapq -import itertools import random from Graph import Edge from RandomGraph import RandomGraph -INFINITY = float('Inf') - class SmallWorldGraph(RandomGraph): """A small world graph for 4.4, exercise 4 in Think Complexity.""" @@ -29,11 +25,7 @@ super(SmallWorldGraph, self).__init__(vs=vs) self.add_regular_edges(k) self.rewire(p) - - # give each edge a default length of 1; this is used by the - # shortest_path_tree() method - for e in self.edges(): - e.length = 1 + self.set_edge_length(1) def rewire(self, p): """Assuming the graph is initially a regular graph, rewires the graph @@ -58,180 +50,3 @@ 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 - - def shortest_path_tree(self, source, hint=None): - """Finds the length of the shortest path from the source vertex to all - other vertices in the graph. This length is stored on the vertices as an - attribute named 'dist'. The algorithm used is Dijkstra's. - - hint: if provided, must be a dictionary mapping tuples to already known - shortest path distances. This can be used to speed up the algorithm. - - """ - if not hint: - hint = {} - - for v in self.vertices(): - v.dist = hint.get((source, v), INFINITY) - source.dist = 0 - - queue = [v for v in self.vertices() if v.dist < INFINITY] - sort_flag = True - while len(queue): - - if sort_flag: - queue.sort(key=lambda v: v.dist) - sort_flag = False - - v = queue.pop(0) - - # for each neighbor of v, see if we found a new shortest path - for w, e in self[v].iteritems(): - d = v.dist + e.length - if d < w.dist: - w.dist = d - queue.append(w) - sort_flag = True - - def shortest_path_tree2(self, source): - """Finds the length of the shortest path from the source vertex to all - other vertices in the graph. This length is stored on the vertices as an - attribute named 'dist'. The algorithm used is Dijkstra's with a Heap - used to sort/store pending nodes to be examined. - - """ - for v in self.vertices(): - v.dist = INFINITY - source.dist = 0 - - queue = [] - heapq.heappush(queue, (0, source)) - while len(queue): - - _, v = heapq.heappop(queue) - - # for each neighbor of v, see if we found a new shortest path - for w, e in self[v].iteritems(): - d = v.dist + e.length - if d < w.dist: - w.dist = d - heapq.heappush(queue, (d, w)) - - def all_pairs_floyd_warshall(self): - """Finds the shortest paths between all pairs of vertices using the - Floyd-Warshall algorithm. - - http://en.wikipedia.org/wiki/Floyd-Warshall_algorithm - - """ - vertices = self.vertices() - dist = {} - for i in vertices: - for j in vertices: - if i is j: - dist[i, j] = 0.0 - else: - e = self.get_edge(i, j) - dist[i, j] = e.length if e else INFINITY - - for k in vertices: - for i in vertices: - for j in vertices: - d_ik = dist[i, k] - d_kj = dist[k, j] - new_cost = d_ik + d_kj - if new_cost < dist[i, j]: - dist[i, j] = new_cost - - return dist - - def big_l(self): - """Computes the "big-L" value for the graph as per Watts & Strogatz. - - L is defined as the number of edges in the shortest path between - two vertices, averaged over all vertices. - - Uses the shortest_path_tree() method, called once for every node. - - """ - d = {} - for v in self.vertices(): - self.shortest_path_tree(v, d) - t = [((w, v), w.dist) for w in self.vertices() if v is not w] - d.update(t) - - if len(d): - return sum(d.values()) / float(len(d)) - return 0.0 - - def big_l2(self): - """Computes the "big-L" value for the graph as per Watts & Strogatz. - - L is defined as the number of edges in the shortest path between - two vertices, averaged over all vertices. - - Uses the all_pairs_floyd_warshall() method. - - """ - dist = self.all_pairs_floyd_warshall() - vertices = self.vertices() - result = [dist[i, j] for i in vertices for j in vertices if i is not j] - - if len(result): - return sum(result) / float(len(result)) - return 0.0 - - def big_l3(self): - """Computes the "big-L" value for the graph as per Watts & Strogatz. - - L is defined as the number of edges in the shortest path between - two vertices, averaged over all vertices. - - Uses the shortest_path_tree2() method, called once for every node. - - """ - d = {} - for v in self.vertices(): - self.shortest_path_tree2(v) - t = [((v, w), w.dist) for w in self.vertices() if v is not w] - d.update(t) - - if len(d): - return sum(d.values()) / float(len(d)) - return 0.0 - diff -r 10db8c3a6b83 -r 305cc03c2750 ch5ex6-3.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/ch5ex6-3.py Thu Jan 10 19:24:02 2013 -0600 @@ -0,0 +1,19 @@ +"""Chapter 5.5, exercise 6 in Allen Downey's Think Complexity book. + +3. Use the BA model to generate a graph with about 1000 vertices and compute the + characteristic length and clustering coefficient as defined in the Watts and + Strogatz paper. Do scale-free networks have the characteristics of + a small-world graph? + +""" + +from ch5ex6 import BAGraph + +g = BAGraph(5, 5) + +for i in xrange(1000): + g.step() + +g.set_edge_length(1) +print "Clustering coefficient:", g.clustering_coefficient() +print "Characteristic length:", g.big_l3()