1
2 """
3 Generators for random graphs
4
5 """
6
7
8
9
10
11
12 __author__ = """Aric Hagberg (hagberg@lanl.gov)\nPieter Swart (swart@lanl.gov)\nDan Schult(dschult@colgate.edu)"""
13 __date__ = "$Date: 2005-06-17 08:06:22 -0600 (Fri, 17 Jun 2005) $"
14 __credits__ = """"""
15 __revision__ = "$Revision: 1049 $"
16 import random
17 import math
18 import networkx
19 from networkx.generators.classic import empty_graph, path_graph, complete_graph
20
21
22
23
24
25
27 """
28 Return a random graph G_{n,p}.
29
30 The G_{n,p} graph choses each of the possible [n(n-1)]/2 edges
31 with probability p.
32
33 Sometimes called Erdős-Rényi graph, or binomial graph.
34
35 :Parameters:
36 - `n`: the number of nodes
37 - `p`: probability for edge creation
38 - `seed`: seed for random number generator (default=None)
39
40 This algorithm is O(n+m) where m is the expected number of
41 edges m=p*n*(n-1)/2.
42
43 It should be faster than gnp_random_graph when p is small, and
44 the expected number of edges is small, (sparse graph).
45
46 See:
47
48 Batagelj and Brandes, "Efficient generation of large random networks",
49 Phys. Rev. E, 71, 036113, 2005.
50
51 """
52 G=empty_graph(n)
53 G.name="fast_gnp_random_graph(%s,%s)"%(n,p)
54
55 if not seed is None:
56 random.seed(seed)
57
58 v=1
59 w=-1
60 lp=math.log(1.0-p)
61
62 while v<n:
63 lr=math.log(1.0-random.random())
64 w=w+1+int(lr/lp)
65 while w>=v and v<n:
66 w=w-v
67 v=v+1
68 if v<n:
69 G.add_edge(v,w)
70 return G
71
72
74 """
75 Return a random graph G_{n,p}.
76
77 Choses each of the possible [n(n-1)]/2 edges with probability p.
78 This is the same as binomial_graph and erdos_renyi_graph.
79
80 Sometimes called Erdős-Rényi graph, or binomial graph.
81
82 :Parameters:
83 - `n`: the number of nodes
84 - `p`: probability for edge creation
85 - `seed`: seed for random number generator (default=None)
86
87 This is an O(n^2) algorithm. For sparse graphs (small p) see
88 fast_gnp_random_graph.
89
90 P. Erdős and A. Rényi, On Random Graphs, Publ. Math. 6, 290 (1959).
91 E. N. Gilbert, Random Graphs, Ann. Math. Stat., 30, 1141 (1959).
92
93 """
94 G=empty_graph(n)
95 G.name="gnp_random_graph(%s,%s)"%(n,p)
96
97 if not seed is None:
98 random.seed(seed)
99
100 for u in xrange(n):
101 for v in xrange(u+1,n):
102 if random.random() < p:
103 G.add_edge(u,v)
104 return G
105
106
107 binomial_graph=gnp_random_graph
108 erdos_renyi_graph=gnp_random_graph
109
111 """
112 Return the random graph G_{n,m}.
113
114 Gives a graph picked randomly out of the set of all graphs
115 with n nodes and m edges.
116 This algorithm should be faster than gnm_random_graph for dense graphs.
117
118 :Parameters:
119 - `n`: the number of nodes
120 - `m`: the number of edges
121 - `seed`: seed for random number generator (default=None)
122
123
124 Algorithm by Keith M. Briggs Mar 31, 2006.
125 Inspired by Knuth's Algorithm S (Selection sampling technique),
126 in section 3.4.2 of
127
128 The Art of Computer Programming by Donald E. Knuth
129 Volume 2 / Seminumerical algorithms
130 Third Edition, Addison-Wesley, 1997.
131
132 """
133 mmax=n*(n-1)/2
134 if m>=mmax:
135 G=complete_graph(n)
136 else:
137 G=empty_graph(n)
138
139 G.name="dense_gnm_random_graph(%s,%s)"%(n,m)
140
141 if n==1 or m>=mmax:
142 return G
143
144 if seed is not None:
145 random.seed(seed)
146
147 u=0
148 v=1
149 t=0
150 k=0
151 while True:
152 if random.randrange(mmax-t)<m-k:
153 G.add_edge(u,v)
154 k+=1
155 if k==m: return G
156 t+=1
157 v+=1
158 if v==n:
159 u+=1
160 v=u+1
161
163 """
164 Return the random graph G_{n,m}.
165
166 Gives a graph picked randomly out of the set of all graphs
167 with n nodes and m edges.
168
169 :Parameters:
170 - `n`: the number of nodes
171 - `m`: the number of edges
172 - `seed`: seed for random number generator (default=None)
173 """
174 G=empty_graph(n)
175 G.name="gnm_random_graph(%s,%s)"%(n,m)
176
177 if seed is not None:
178 random.seed(seed)
179
180 if n==1:
181 return G
182
183 if m>=n*(n-1)/2:
184 return complete_graph(n)
185
186 nlist=G.nodes()
187 edge_count=0
188 while edge_count < m:
189
190 u = random.choice(nlist)
191 v = random.choice(nlist)
192 if u==v or G.has_edge(u,v):
193 continue
194
195
196
197
198 else:
199 G.add_edge(u,v)
200 edge_count=edge_count+1
201 return G
202
204 """
205 Return a Newman-Watts-Strogatz small world graph.
206
207 First create a ring over n nodes. Then each node in the ring is
208 connected with its k nearest neighbors. Then shortcuts are
209 created by adding new edges as follows: for each edge u-v in the
210 underlying "n-ring with k nearest neighbors"; with probability p
211 add a new edge u-w with randomly-chosen existing node w.
212 In contrast with watts_strogatz_graph(), no edges are removed.
213
214 :Parameters:
215 - `n`: the number of nodes
216 - `k`: each node is connected to k nearest neighbors in ring topology
217 - `p`: the probability of adding a new edge for each edge
218 - `seed`: seed for random number generator (default=None)
219
220 """
221 if seed is not None:
222 random.seed(seed)
223 G=empty_graph(n)
224 G.name="newman_watts_strogatz_graph(%s,%s,%s)"%(n,k,p)
225 nlist = G.nodes()
226 fromv = nlist
227
228 for n in range(1, k/2+1):
229 tov = fromv[n:] + fromv[0:n]
230 for i in range(len(fromv)):
231 G.add_edge(fromv[i], tov[i])
232
233
234 e = G.edges()
235 for (u, v) in e:
236 if random.random() < p:
237 w = random.choice(nlist)
238
239
240 while w == u or G.has_edge(u, w):
241 w = random.choice(nlist)
242 G.add_edge(u,w)
243 return G
244
246 """
247 Return a Watts-Strogatz small world graph.
248
249 First create a ring over n nodes. Then each node in the ring is
250 connected with its k nearest neighbors. Then shortcuts are
251 created by rewiring existing edges as follows: for each edge u-v
252 in the underlying "n-ring with k nearest neighbors"; with
253 probability p replace u-v with a new edge u-w with
254 randomly-chosen existing node w. In contrast with
255 newman_watts_strogatz_graph(), the random rewiring does not
256 increase the number of edges.
257
258
259 :Parameters:
260 - `n`: the number of nodes
261 - `k`: each node is connected to k neighbors in the ring topology
262 - `p`: the probability of rewiring an edge
263 - `seed`: seed for random number generator (default=None)
264
265 """
266 if seed is not None:
267 random.seed(seed)
268 G=empty_graph(n)
269 G.name="watts_strogatz_graph(%s,%s,%s)"%(n,k,p)
270 nlist = G.nodes()
271 fromv = nlist
272
273 for n in range(1, k/2+1):
274 tov = fromv[n:] + fromv[0:n]
275 for i in range(len(fromv)):
276 G.add_edge(fromv[i], tov[i])
277
278
279 e = G.edges()
280 for (u, v) in e:
281 if random.random() < p:
282 newv = random.choice(nlist)
283
284
285 while newv == u or G.has_edge(u, newv):
286 newv = random.choice(nlist)
287 G.delete_edge(u,v)
288 G.add_edge(u,newv)
289 return G
290
291
292
294 """Return a random regular graph of n nodes each with degree d, G_{n,d}.
295 Return False if unsuccessful.
296
297 n*d must be even
298
299 Nodes are numbered 0...n-1.
300 To get a uniform sample from the space of random graphs
301 you should chose d<n^{1/3}.
302
303 For algorith see Kim and Vu's paper.
304
305 Reference::
306
307 @inproceedings{kim-2003-generating,
308 author = {Jeong Han Kim and Van H. Vu},
309 title = {Generating random regular graphs},
310 booktitle = {Proceedings of the thirty-fifth ACM symposium on Theory of computing},
311 year = {2003},
312 isbn = {1-58113-674-9},
313 pages = {213--222},
314 location = {San Diego, CA, USA},
315 doi = {http://doi.acm.org/10.1145/780542.780576},
316 publisher = {ACM Press},
317 }
318
319 The algorithm is based on an earlier paper::
320
321 @misc{ steger-1999-generating,
322 author = "A. Steger and N. Wormald",
323 title = "Generating random regular graphs quickly",
324 text = "Probability and Computing 8 (1999), 377-396.",
325 year = "1999",
326 url = "citeseer.ist.psu.edu/steger99generating.html",
327 }
328
329 """
330
331 def _suitable(stubs):
332 for s in stubs:
333 for t in stubs:
334 if not seen_edges[s].has_key(t) and s!=t:
335 return True
336
337
338 return False
339
340 if not n*d%2==0:
341 raise networkx.NetworkXError, "n * d must be even"
342
343 if seed is not None:
344 random.seed(seed)
345
346
347 G=empty_graph(n)
348 G.name="random_regular_graph(%s,%s)"%(d,n)
349
350
351 seen_edges={}
352 [seen_edges.setdefault(v,{}) for v in range(n)]
353
354 vv=[ [v]*d for v in range(n)]
355 stubs=reduce(lambda x,y: x+y ,vv)
356
357 while len(stubs) > 0:
358 source=random.choice(stubs)
359 target=random.choice(stubs)
360 if source!=target and not seen_edges[source].has_key(target):
361 stubs.remove(source)
362 stubs.remove(target)
363 seen_edges[source][target]=1
364 seen_edges[target][source]=1
365 G.add_edge(source,target)
366 else:
367
368 s=_suitable(stubs)
369 if not s:
370 return False
371 return G
372
373
374
376 """Return random graph using Barabási-Albert preferential attachment model.
377
378 A graph of n nodes is grown by attaching new nodes
379 each with m edges that are preferentially attached
380 to existing nodes with high degree.
381
382 :Parameters:
383 - `n`: the number of nodes
384 - `m`: number of edges to attach from a new node to existing nodes
385 - `seed`: seed for random number generator (default=None)
386
387 The initialization is a graph with with m nodes and no edges.
388
389 Reference::
390
391 @article{barabasi-1999-emergence,
392 title = {Emergence of scaling in random networks},
393 author = {A. L. Barabási and R. Albert},
394 journal = {Science},
395 volume = {286},
396 number = {5439},
397 pages = {509 -- 512},
398 year = {1999},
399 }
400
401
402 """
403
404 if m < 1 or n < m:
405 raise networkx.NetworkXError,\
406 "NetworkXError must have m>1 and m<n, m=%d,n=%d"%(m,n)
407
408 if seed is not None:
409 random.seed(seed)
410
411 G=empty_graph(m)
412 G.name="barabasi_albert_graph(%s,%s)"%(n,m)
413 edge_targets=range(m)
414 repeated_nodes=[]
415
416 source=m
417 while source<n:
418 G.add_edges_from(zip([source]*m,edge_targets))
419 repeated_nodes.extend(edge_targets)
420 repeated_nodes.extend([source]*m)
421
422
423
424
425 edge_targets=random.sample(repeated_nodes,m)
426 source += 1
427 return G
428
430 """
431 Holme and Kim algorithm for growing graphs with powerlaw
432 degree distribution and approximate average clustering.
433
434 :Parameters:
435 - `n`: the number of nodes
436 - `m`: the number of random edges to add for each new node
437 - `p`: probability of adding a triangle after adding a random edge
438 - `seed`: seed for random number generator (default=None)
439
440 Reference::
441
442 @Article{growing-holme-2002,
443 author = {P. Holme and B. J. Kim},
444 title = {Growing scale-free networks with tunable clustering},
445 journal = {Phys. Rev. E},
446 year = {2002},
447 volume = {65},
448 number = {2},
449 pages = {026107},
450 }
451
452 The average clustering has a hard time getting above
453 a certain cutoff that depends on m. This cutoff is often quite low.
454 Note that the transitivity (fraction of triangles to possible
455 triangles) seems to go down with network size.
456
457 It is essentially the Barabási-Albert growth model with an
458 extra step that each random edge is followed by a chance of
459 making an edge to one of its neighbors too (and thus a triangle).
460
461 This algorithm improves on B-A in the sense that it enables a
462 higher average clustering to be attained if desired.
463
464 It seems possible to have a disconnected graph with this algorithm
465 since the initial m nodes may not be all linked to a new node
466 on the first iteration like the BA model.
467
468 """
469
470 if m < 1 or n < m:
471 raise networkx.NetworkXError,\
472 "NetworkXError must have m>1 and m<n, m=%d,n=%d"%(m,n)
473
474 if p > 1 or p < 0:
475 raise networkx.NetworkXError,\
476 "NetworkXError p must be in [0,1], p=%f"%(p)
477
478
479 if seed is not None:
480 random.seed(seed)
481
482 G=empty_graph(m)
483 G.name="Powerlaw-Cluster Graph"
484 repeated_nodes=G.nodes()
485
486 source=m
487 while source<n:
488 possible_targets=random.sample(repeated_nodes,m)
489
490 target=possible_targets.pop()
491 G.add_edge(source,target)
492 repeated_nodes.append(target)
493 count=1
494 while count<m:
495 if random.random()<p:
496 neighborhood=[nbr for nbr in G.neighbors(target) \
497 if not G.has_edge(source,nbr) \
498 and not nbr==source]
499 if neighborhood:
500 nbr=random.choice(neighborhood)
501 G.add_edge(source,nbr)
502 repeated_nodes.append(nbr)
503 count=count+1
504 continue
505
506 target=possible_targets.pop()
507 G.add_edge(source,target)
508 repeated_nodes.append(target)
509 count=count+1
510
511 repeated_nodes.extend([source]*m)
512 source += 1
513 return G
514
516 """Return a random lobster.
517
518 A caterpillar is a tree that reduces to a path graph when pruning
519 all leaf nodes (p2=0).
520 A lobster is a tree that reduces to a caterpillar when pruning all
521 leaf nodes.
522
523 :Parameters:
524 - `n`: the expected number of nodes in the backbone
525 - `p1`: probability of adding an edge to the backbone
526 - `p2`: probability of adding an edge one level beyond backbone
527 - `seed`: seed for random number generator (default=None)
528
529 """
530
531 if seed is not None:
532 random.seed(seed)
533 llen=int(2*random.random()*n + 0.5)
534 L=path_graph(llen)
535 L.name="random_lobster(%d,%s,%s)"%(n,p1,p2)
536
537 current_node=llen-1
538 for n in xrange(llen):
539 if random.random()<p1:
540 current_node+=1
541 L.add_edge(n,current_node)
542 if random.random()<p2:
543 current_node+=1
544 L.add_edge(current_node-1,current_node)
545 return L
546
548 """
549 Return a random shell graph for the constructor given.
550
551 - constructor: a list of three-tuples [(n1,m1,d1),(n2,m2,d2),..]
552 one for each shell, starting at the center shell.
553 - n : the number of nodes in the shell
554 - m : the number or edges in the shell
555 - d : the ratio of inter (next) shell edges to intra shell edges.
556 d=0 means no intra shell edges.
557 d=1 for the last shell
558 - `seed`: seed for random number generator (default=None)
559
560 >>> constructor=[(10,20,0.8),(20,40,0.8)]
561 >>> G=random_shell_graph(constructor)
562
563 """
564 G=empty_graph(0)
565 G.name="random_shell_graph(constructor)"
566
567 if seed is not None:
568 random.seed(seed)
569
570 glist=[]
571 intra_edges=[]
572 nnodes=0
573
574 for (n,m,d) in constructor:
575 inter_edges=int(m*d)
576 intra_edges.append(m-inter_edges)
577 g=networkx.operators.convert_node_labels_to_integers(
578 gnm_random_graph(n,inter_edges),
579 first_label=nnodes)
580 glist.append(g)
581 nnodes+=n
582 G=networkx.operators.union(G,g)
583
584
585 for gi in range(len(glist)-1):
586 nlist1=glist[gi].nodes()
587 nlist2=glist[gi+1].nodes()
588 total_edges=intra_edges[gi]
589 edge_count=0
590 while edge_count < total_edges:
591 u = random.choice(nlist1)
592 v = random.choice(nlist2)
593 if u==v or G.has_edge(u,v):
594 continue
595 else:
596 G.add_edge(u,v)
597 edge_count=edge_count+1
598 return G
599
600
602 """
603 Return a tree with a powerlaw degree distribution.
604
605 A trial powerlaw degree sequence is chosen and then elements are
606 swapped with new elements from a powerlaw distribution until
607 the sequence makes a tree (#edges=#nodes-1).
608
609 :Parameters:
610 - `n`: the number of nodes
611 - `gamma`: exponent of power law is gamma
612 - `tries`: number of attempts to adjust sequence to make a tree
613 - `seed`: seed for random number generator (default=None)
614
615 """
616 from networkx.generators.degree_seq import degree_sequence_tree
617 try:
618 s=random_powerlaw_tree_sequence(n,
619 gamma=gamma,
620 seed=seed,
621 tries=tries)
622 except:
623 raise networkx.NetworkXError,\
624 "Exceeded max (%d) attempts for a valid tree sequence."%tries
625 G=degree_sequence_tree(s)
626 G.name="random_powerlaw_tree(%s,%s)"%(n,gamma)
627 return G
628
629
631 """
632 Return a degree sequence for a tree with a powerlaw distribution.
633
634 A trial powerlaw degree sequence is chosen and then elements are
635 swapped with new elements from a powerlaw distribution until
636 the sequence makes a tree (#edges=#nodes-1).
637
638 :Parameters:
639 - `n`: the number of nodes
640 - `gamma`: exponent of power law is gamma
641 - `tries`: number of attempts to adjust sequence to make a tree
642 - `seed`: seed for random number generator (default=None)
643
644 """
645 if seed is not None:
646 random.seed(seed)
647
648
649 z=networkx.utils.powerlaw_sequence(n,exponent=gamma)
650
651 zseq=[min(n, max( int(round(s)),0 )) for s in z]
652
653
654 z=networkx.utils.powerlaw_sequence(tries,exponent=gamma)
655
656 swap=[min(n, max( int(round(s)),0 )) for s in z]
657
658 for deg in swap:
659 if n-sum(zseq)/2.0 == 1.0:
660 return zseq
661 index=random.randint(0,n-1)
662 zseq[index]=swap.pop()
663
664 raise networkx.NetworkXError, \
665 "Exceeded max (%d) attempts for a valid tree sequence."%tries
666 return False
667
668
669
670
671
673 import doctest
674 suite = doctest.DocFileSuite('tests/generators/random_graphs.txt',package='networkx')
675 return suite
676
677 if __name__ == "__main__":
678 import os
679 import sys
680 import unittest
681 if sys.version_info[:2] < (2, 4):
682 print "Python version 2.4 or later required for tests (%d.%d detected)." % sys.version_info[:2]
683 sys.exit(-1)
684
685 nxbase=sys.path[0]+os.sep+os.pardir
686 sys.path.insert(0,nxbase)
687 unittest.TextTestRunner().run(_test_suite())
688