1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233 |
"""
Simulation for the verifying of "Emergence of a Small World from Local
Interactions: Modeling Acquaintance Network", Davidsen J. et al. 2002.
Public Variables:
- Iters: the interations of loop, used in loop()
Private Variables:
- _G: graph of the acquaintance network
- _N: the total of nodes
- _p: the death-and-birth probability, used in _step2()
- _run: a generator returned by loop()
Usage
=====
This module must run on a python shell with interative mode; and call
public functions e.g. runnext().
Example
-------
You can simply run this module with default settings.
> python -i acq2002.py
>>> runnext(10) # loops 10 times of Iters time-steps.
...
Setting parameters is allowed.
>>> start(1000, 0.04) # starts the simulation with new N, and p
>>> Iters=10000 # sets the iterations of each loop
>>> runnext(5) # loops 5 times of 10000 time-steps.
...
>>> Iters=100000 # sets the iterations of each loop
>>> runnext(2) # loops another 2 times of 100000 time-steps
...
After above, you may want to save the result.
>>> savepkfig()
>>> savenet()
"""
__author__ = "Jiang Yu-Kuan, yukuan.jiang(at)gmail.com"
__date__ = "2006/08/22~2006/10/02"
__revision__ = "1.10"
import random as rnd
import networkx as nx
def _create():
"""Create an empty acquaintance network.
Adds _N nodes to _G, and _G contains no any edges.
"""
global _G
_G = nx.Graph()
_G.add_nodes_from(xrange(_N))
def _step1():
"""Friend making of two persons.
One randomly chosen person picks any two his acquaintances and
introduces them to each another. If they have not met before, a new
link between them is formed. In case the person chosen has less than
two acquaintances, he introduces himself to one other random person.
"""
u, v = rnd.sample(xrange(_N), 2)
nb = _G.neighbors(u)
if len(nb) > 1:
u, v = rnd.sample(nb, 2)
_G.add_edge(u, v)
def _step2(p):
"""Death and Birth of a chosen person.
With probability p, one randomly chosen person is removed from the
network, including all links connected to this node, and replaced by
a new person with one randomly chosen acquaintance.
"""
if rnd.random() < p:
v = rnd.randrange(_N)
_G.delete_node(v)
_G.add_node(v)
def _avgK2():
"""Return the average square of degree of all nodes."""
kss = [k*k for k in _G.degree(_G.nodes())]
return sum(kss)/float(_N)
def _avgSPL():
"""Return the average shortest path length of Graph _G."""
pathlengths=[]
for v in _G.nodes():
pathlengths += nx.single_source_shortest_path_length(_G,v).values()
return sum(pathlengths) / float(len(pathlengths)-_N)
def _stat():
"""Gather statistics for Graph _G."""
print "N, p = %d, %f" % (_N, _p)
print "Degree histogram:", nx.degree_histogram(_G)
print "Avg. degree, <k>:", 2.*_G.number_of_edges()/_N
print "Avg. square of degree, <k^2>:", _avgK2()
print "Avg. clustering coefficient, C:", nx.average_clustering(_G)
print "Avg. shortest path length, L:", _avgSPL()
def savepkfig(fn='acq2002pk.png'):
"""Save the p(k) figure.
- fn: file name
"""
import pylab as mpl
dh = nx.degree_histogram(_G)
pk = mpl.array(dh)/float(_N)
mpl.loglog(pk, 'r--')
mpl.grid(True)
mpl.gca().xaxis.grid(True, which='minor')
mpl.xlabel('k')
mpl.ylabel('p(k)')
mpl.title('N=%d, p=%d' % (_N, _p) )
mpl.savefig(fn)
def savenet(fn='acq2002', fm='GPickle'):
"""Save the acquaintance network.
- fn: file name
- fm: file format
"""
save = {'edgelist':nx.write_edgelist, 'adjlist':nx.write_adjlist, 'yaml':nx.write_yaml, 'gpickle':nx.write_gpickle }
fm = fm.lower()
if fm not in save.keys():
fm = 'edgelist'
import os
fn, ext = os.path.splitext(fn)
ext = ext[1:].lower()
if ext in save.keys():
fm = ext
save[fm](_G, '.'.join([fn, fm]))
def _loop():
"""Loop _step1 and _step2 of Iters times and gather statistics.
This function uses yield statement and returns the total iterations of loop
"""
import time
t_start = time.time() t_ttl = 0 i_cnt = i_ttl = 0
_create()
while 1:
i_cnt += 1
_step1()
_step2(_p)
if i_cnt == Iters:
i_ttl += i_cnt
i_cnt = 0
_stat()
t_inc = time.time() - t_start
t_ttl += t_inc
print "Time spent (increment,total): (%f,%f)" % (t_inc, t_ttl)
yield i_ttl
t_start = time.time()
def runnext(n=1):
"""Call _run.next() of n times."""
for i in xrange(n):
print _run.next()
def start(N=100, p=0.04):
"""Start the module.
- N: the total of nodes of the network
- p: the death-and-birth probability
"""
global _N, _p, _run
_N, _p = N, p
_run = _loop()
Iters = 100000
if __name__ == "__main__":
try:
import psyco
psyco.full()
print "Psyco: OK"
except ImportError:
print "Psyco: FAIL"
start(100, .04)
"""
import profile, pstats
profile.run('runnext()', 'acq2002.prof')
s = pstats.Stats('acq2002.prof')
s.sort_stats('time','name').print_stats()
""" |
