Package networkx :: Package generators :: Module random_graphs
[hide private]
[frames] | no frames]

Source Code for Module networkx.generators.random_graphs

  1  # -*- coding: utf-8 -*- 
  2  """ 
  3  Generators for random graphs 
  4   
  5  """ 
  6  #    Copyright (C) 2004,2005,2006 by  
  7  #    Aric Hagberg <hagberg@lanl.gov> 
  8  #    Dan Schult <dschult@colgate.edu> 
  9  #    Pieter Swart <swart@lanl.gov> 
 10  #    Distributed under the terms of the GNU Lesser General Public License 
 11  #    http://www.gnu.org/copyleft/lesser.html 
 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  #  Some Famous Random Graphs 
 23  #------------------------------------------------------------------------- 
 24   
 25   
26 -def fast_gnp_random_graph(n, p, seed=None):
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 # Nodes in graph are from 0,n-1 (this is the second node index). 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
73 -def gnp_random_graph(n, p, seed=None):
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 # add some aliases to common names 107 binomial_graph=gnp_random_graph 108 erdos_renyi_graph=gnp_random_graph 109
110 -def dense_gnm_random_graph(n, m, seed=None):
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: # go to next row of adjacency matrix 159 u+=1 160 v=u+1
161
162 -def gnm_random_graph(n, m, seed=None):
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 # generate random edge,u,v 190 u = random.choice(nlist) 191 v = random.choice(nlist) 192 if u==v or G.has_edge(u,v): 193 continue 194 # is this faster? 195 # (u,v)=random.sample(nlist,2) 196 # if G.has_edge(u,v): 197 # continue 198 else: 199 G.add_edge(u,v) 200 edge_count=edge_count+1 201 return G
202
203 -def newman_watts_strogatz_graph(n, k, p, seed=None):
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 # connect the k/2 neighbors 228 for n in range(1, k/2+1): 229 tov = fromv[n:] + fromv[0:n] # the first n are now last 230 for i in range(len(fromv)): 231 G.add_edge(fromv[i], tov[i]) 232 # for each edge u-v, with probability p, randomly select existing 233 # node w and add new edge u-w 234 e = G.edges() 235 for (u, v) in e: 236 if random.random() < p: 237 w = random.choice(nlist) 238 # no self-loops and reject if edge u-w exists 239 # is that the correct NWS model? 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
245 -def watts_strogatz_graph(n, k, p, seed=None):
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 # connect the k/2 neighbors 273 for n in range(1, k/2+1): 274 tov = fromv[n:] + fromv[0:n] # the first n are now last 275 for i in range(len(fromv)): 276 G.add_edge(fromv[i], tov[i]) 277 # for each edge u-v, with probability p, randomly replace with 278 # edge u-w 279 e = G.edges() 280 for (u, v) in e: 281 if random.random() < p: 282 newv = random.choice(nlist) 283 # avoid self-loops and reject if edge u-newv exists 284 # is that the correct WS model? 285 while newv == u or G.has_edge(u, newv): 286 newv = random.choice(nlist) 287 G.delete_edge(u,v) # conserve number of edges 288 G.add_edge(u,newv) 289 return G
290 291 292
293 -def random_regular_graph(d, n, seed=None):
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 # helper subroutine to check for suitable edges 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 # else no suitable possible edges 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 # keep track of the edges we have seen 351 seen_edges={} 352 [seen_edges.setdefault(v,{}) for v in range(n)] 353 354 vv=[ [v]*d for v in range(n)] # List of degree-repeated vertex numbers 355 stubs=reduce(lambda x,y: x+y ,vv) # flatten the list of lists to a list 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 # further check to see if suitable 368 s=_suitable(stubs) 369 if not s: 370 return False 371 return G 372 373 374
375 -def barabasi_albert_graph(n , m, seed=None):
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) # add m initial nodes (m0 in barabasi-speak) 412 G.name="barabasi_albert_graph(%s,%s)"%(n,m) 413 edge_targets=range(m) # possible targets for new edges 414 repeated_nodes=[] # list of existing nodes, 415 # with nodes repeated once for each adjacent edge 416 source=m # next node is m 417 while source<n: # Now add the other n-1 nodes 418 G.add_edges_from(zip([source]*m,edge_targets)) # add links to m nodes 419 repeated_nodes.extend(edge_targets) # add one node for each new link 420 repeated_nodes.extend([source]*m) # and new node "source" has m links 421 # choose m nodes randomly from existing nodes 422 # N.B. during each step of adding a new node the probabilities 423 # are fixed, is this correct? or should they be updated. 424 # Also, random sampling prevents some parallel edges. 425 edge_targets=random.sample(repeated_nodes,m) 426 source += 1 427 return G
428
429 -def powerlaw_cluster_graph(n, m, p, seed=None):
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) # add m initial nodes (m0 in barabasi-speak) 483 G.name="Powerlaw-Cluster Graph" 484 repeated_nodes=G.nodes() # list of existing nodes to sample from 485 # with nodes repeated once for each adjacent edge 486 source=m # next node is m 487 while source<n: # Now add the other n-1 nodes 488 possible_targets=random.sample(repeated_nodes,m) 489 # do one preferential attachment for new node 490 target=possible_targets.pop() 491 G.add_edge(source,target) 492 repeated_nodes.append(target) # add one node to list for each new link 493 count=1 494 while count<m: # add m-1 more new links 495 if random.random()<p: # clustering step: add triangle 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: # if there is a neighbor without a link 500 nbr=random.choice(neighborhood) 501 G.add_edge(source,nbr) # add triangle 502 repeated_nodes.append(nbr) 503 count=count+1 504 continue # go to top of while loop 505 # else do preferential attachment step if above fails 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) # add source node to list m times 512 source += 1 513 return G
514
515 -def random_lobster(n, p1, p2, seed=None):
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 # a necessary ingredient in any self-respecting graph library 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 # build caterpillar: add edges to path graph with probability p1 537 current_node=llen-1 538 for n in xrange(llen): 539 if random.random()<p1: # add fuzzy caterpillar parts 540 current_node+=1 541 L.add_edge(n,current_node) 542 if random.random()<p2: # add crunchy lobster bits 543 current_node+=1 544 L.add_edge(current_node-1,current_node) 545 return L # voila, un lobster!
546
547 -def random_shell_graph(constructor, seed=None):
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 # create gnm graphs for each shell 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 # connect the shells randomly 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
601 -def random_powerlaw_tree(n, gamma=3, seed=None, tries=100):
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
630 -def random_powerlaw_tree_sequence(n, gamma=3, seed=None, tries=100):
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 # get trial sequence 649 z=networkx.utils.powerlaw_sequence(n,exponent=gamma) 650 # round to integer values in the range [0,n] 651 zseq=[min(n, max( int(round(s)),0 )) for s in z] 652 653 # another sequence to swap values from 654 z=networkx.utils.powerlaw_sequence(tries,exponent=gamma) 655 # round to integer values in the range [0,n] 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: # is a tree, return sequence 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
672 -def _test_suite():
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 # directory of networkx package (relative to this) 685 nxbase=sys.path[0]+os.sep+os.pardir 686 sys.path.insert(0,nxbase) # prepend to search path 687 unittest.TextTestRunner().run(_test_suite()) 688