Mercurial > public > think_complexity

annotate ch5ex6.py @ 48:98eb01502cf5 tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Follow up to last commit. Re-orient the r-pentomino. Added progress display.
author Brian Neal <bgneal@gmail.com>
date Wed, 31 Jul 2013 20:37:12 -0500
parents 10db8c3a6b83
children
rev   line source
bgneal@32 1 # -*- coding: utf-8 -*-
bgneal@32 2 """Chapter 5.5, exercise 6 in Allen Downey's Think Complexity book.
bgneal@32 3
bgneal@32 4 1. Read Barabási and Albert’s paper and implement their algorithm for generating
bgneal@32 5 graphs. See if you can replicate their Figure 2(A), which shows P(k) versus
bgneal@32 6 k for a graph with 150 000 vertices.
bgneal@32 7
bgneal@32 8 """
bgneal@32 9 import random
bgneal@32 10 import sys
bgneal@32 11
bgneal@32 12 from matplotlib import pyplot
bgneal@32 13
bgneal@32 14 from Graph import Graph, Vertex, Edge
bgneal@32 15
bgneal@32 16
bgneal@32 17 class BAGraph(Graph):
bgneal@32 18 """BAGraph implements the algorithm described in the Barabási and
bgneal@32 19 Albert paper "Emergence of Scaling in Random Networks" from Science
bgneal@32 20 Magazine Vol. 286, 15 October 1999.
bgneal@32 21
bgneal@32 22 """
bgneal@32 23 def __init__(self, m0, m):
bgneal@32 24 """Create a graph with m0 vertices and m connecting edges.
bgneal@32 25
bgneal@32 26 """
bgneal@32 27 self.m0 = m0
bgneal@32 28 self.m = m
bgneal@32 29 self.histogram = []
bgneal@32 30
bgneal@32 31 initial_vertices = [Vertex() for i in xrange(m0)]
bgneal@32 32
bgneal@32 33 super(BAGraph, self).__init__(vs=initial_vertices)
bgneal@32 34
bgneal@32 35 # Add initial edges between nodes randomly
bgneal@32 36 n = 0
bgneal@32 37 while n != m:
bgneal@32 38 # pick two vertices at random
bgneal@32 39 v = random.choice(initial_vertices)
bgneal@32 40 w = random.choice(initial_vertices)
bgneal@32 41
bgneal@32 42 # if they aren't the same and don't already have an edge, add one
bgneal@32 43 if v is not w and not self.get_edge(v, w):
bgneal@32 44 self.add_edge(Edge(v, w))
bgneal@32 45 n += 1
bgneal@32 46
bgneal@32 47 def add_edge(self, edge):
bgneal@32 48 """Our version of add_edge() adds the two vertices on either end of the
bgneal@32 49 edge to a histogram. This allows us to more easily pick popular vertices
bgneal@32 50 when adding edges as part of the step() method.
bgneal@32 51
bgneal@32 52 """
bgneal@32 53 super(BAGraph, self).add_edge(edge) # invoke base class version
bgneal@32 54
bgneal@32 55 v, w = edge
bgneal@32 56 self.histogram.append(v)
bgneal@32 57 self.histogram.append(w)
bgneal@32 58
bgneal@32 59 def step(self):
bgneal@32 60 """This method adds a new vertex to the graph, then adds m edges that
bgneal@32 61 link the new vertex to m different vertices already present in the
bgneal@32 62 graph. Preferential treatment is given towards vertices that already
bgneal@32 63 have high connectivity.
bgneal@32 64
bgneal@32 65 The paper describes this preferential choosing as creating a probability
bgneal@32 66 P that a new vertex will be connected to vertex i depends on the
bgneal@32 67 connectivity ki of that vertex, so that P(ki) = ki / sum(kj).
bgneal@32 68
bgneal@32 69 We implement that by keeping a list of vertices (histogram), where we
bgneal@32 70 insert a vertex into this list whenever it gets an edge added to it. We
bgneal@32 71 then randomly choose a vertex from this list. Thus the vertices with
bgneal@32 72 more edges will be more likely chosen.
bgneal@32 73
bgneal@32 74 """
bgneal@32 75 # pick m unique vertices to attach to the new vertex
bgneal@32 76 vs = set()
bgneal@32 77 while len(vs) < self.m:
bgneal@32 78 w = random.choice(self.histogram)
bgneal@32 79 if w not in vs:
bgneal@32 80 vs.add(w)
bgneal@32 81
bgneal@32 82 # Add the new vertex to the graph and create edges
bgneal@32 83 v = Vertex()
bgneal@32 84 self.add_vertex(v)
bgneal@32 85 for w in vs:
bgneal@32 86 self.add_edge(Edge(v, w))
bgneal@32 87
bgneal@32 88
bgneal@32 89 def main(script, m0, m, n):
bgneal@32 90
bgneal@32 91 # create a BAGraph with parameters m0 & m:
bgneal@32 92 m0, m, n = int(m0), int(m), int(n)
bgneal@32 93 g = BAGraph(m0, m)
bgneal@32 94
bgneal@32 95 # step the graph n times:
bgneal@32 96 for i in xrange(n):
bgneal@32 97 g.step()
bgneal@32 98
bgneal@32 99 # retrieve probabilities
bgneal@32 100 p = g.get_p()
bgneal@32 101
bgneal@32 102 # plot P(k) versus k on a log-log scale
bgneal@32 103
bgneal@32 104 vals = p.items()
bgneal@32 105 vals.sort(key=lambda t: t[0])
bgneal@32 106 x, y = zip(*vals)
bgneal@32 107
bgneal@34 108 assert abs(sum(y) - 1.0) < 1e-6
bgneal@34 109
bgneal@32 110 pyplot.clf()
bgneal@32 111 pyplot.xscale('log')
bgneal@32 112 pyplot.yscale('log')
bgneal@32 113 pyplot.title('P(k) versus k')
bgneal@32 114 pyplot.xlabel('k')
bgneal@32 115 pyplot.ylabel('P(k)')
bgneal@32 116 pyplot.plot(x, y, label='P(k) vs. k', color='green', linewidth=3)
bgneal@32 117 pyplot.legend(loc='upper right')
bgneal@32 118 pyplot.show()
bgneal@32 119
bgneal@32 120
bgneal@32 121 if __name__ == '__main__':
bgneal@32 122 main(*sys.argv)