Mercurial > public > think_complexity

comparison ch5ex6.py @ 32:a13c00c0dfe5

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