Home | Trees | Index | Help |
|
---|
Package networkx :: Package generators :: Module random_graphs |
|
Generators for random graphs
Function Summary | |
---|---|
Return random graph using Barabasi-Albert preferential attachment model. | |
Return a binomial random graph G_{n,p}. | |
Return the Erdos-Renyi random graph G_{n,m}. | |
Return a Newman-Watts-Strogatz small world graph. | |
Holme and Kim algorithm for growing graphs with powerlaw degree distribution and approximate average clustering. | |
Return a random lobster. | |
Return a tree with a powerlaw degree distribution. | |
Return a degree sequence for a tree with a powerlaw distribution. | |
Return a random regular graph of n nodes each with degree d, G_{n,d}. | |
Return a random shell graph for the constructor given. | |
Return a Watts-Strogatz small world graph. |
Variable Summary | |
---|---|
str |
__author__ = 'Aric Hagberg (hagberg@lanl.gov)\nPieter Sw...
|
str |
__credits__ = ''
|
str |
__date__ = '$Date: 2005-06-17 08:06:22 -0600 (Fri, 17 Ju...
|
str |
__revision__ = '$Revision: 1049 $'
|
Function Details |
---|
barabasi_albert_graph(n, m, seed=None)Return random graph using Barabasi-Albert preferential attachment model. A graph of n nodes is grown by attaching new nodes each with m edges that are preferentially attached to existing nodes with high degree. The initialization is a graph with with m nodes. Reference: @ARTICLE{barabasi-1999-emergence, TITLE = {Emergence of scaling in random networks}, AUTHOR = {A. L. Barabasi and R. Albert}, JOURNAL = {SCIENCE}, VOLUME = {286}, NUMBER = {5439}, PAGES = {509 -- 512}, MONTH = {OCT}, YEAR = {1999}, }
|
binomial_graph(n, p, seed=None)Return a binomial random graph G_{n,p}.
|
erdos_renyi_graph(n, m, seed=None)Return the Erdos-Renyi random graph G_{n,m}.
|
newman_watts_strogatz_graph(n, k, p, seed=None)Return a Newman-Watts-Strogatz small world graph. The graph is a ring with k neighbors with new edges (shortcuts) added randomly with probability p for each edge. No edges are removed.
|
powerlaw_cluster_graph(n, m, p, seed=None)Holme and Kim algorithm for growing graphs with powerlaw degree distribution and approximate average clustering. Reference: @Article{growing-holme-2002, author = {P. Holme and B. J. Kim}, title = {Growing scale-free networks with tunable clustering}, journal = {Phys. Rev. E}, year = {2002}, volume = {65}, number = {2}, pages = {026107}, } The average clustering has a hard time getting above a certain cutoff that depends on m. This cutoff is often quite low. It is essentially the Barabasi-Albert growth model with an extra step that each random edge is followed by a chance of making an edge to one of its neighbors too (and thus a triangle). This algorithm improves on B-A in the sense that it enables a higher average clustering to be attained if desired. The largest average clustering seems to be independent of n and attained with m=1 and p=1 (cc=0.74 or so).
|
random_lobster(n, p1, p2, seed=None)Return a random lobster. A caterpillar is a tree that reduces to a path graph when pruning all leave nodes. A lobster is a tree that reduces to a caterpillar when pruning all leave nodes.
|
random_powerlaw_tree(n, gamma=3, seed=None, tries=100)Return a tree with a powerlaw degree distribution. A trial powerlaw degree sequence is chosen and then elements are swapped with new elements from a powerlaw distribution until the sequence makes a tree (#edges=#nodes-1).
|
random_powerlaw_tree_sequence(n, gamma=3, seed=None, tries=100)Return a degree sequence for a tree with a powerlaw distribution. A trial powerlaw degree sequence is chosen and then elements are swapped with new elements from a powerlaw distribution until the sequence makes a tree (#edges=#nodes-1).
|
random_regular_graph(d, n, seed=None)Return a random regular graph of n nodes each with degree d, G_{n,d}. Return False if unsuccessful. n*d must be even Nodes are numbered 0...n-1. To get a uniform sample from the space of random graphs you should chose d<n^{1/3}. . For algorith see Kim and Vu's paper. Reference: @inproceedings{kim-2003-generating, author = {Jeong Han Kim and Van H. Vu}, title = {Generating random regular graphs}, booktitle = {Proceedings of the thirty-fifth ACM symposium on Theory of computing}, year = {2003}, isbn = {1-58113-674-9}, pages = {213--222}, location = {San Diego, CA, USA}, doi = {http://doi.acm.org/10.1145/780542.780576}, publisher = {ACM Press}, } The algorithm is based on an earlier paper: @misc{ steger-1999-generating, author = "A. Steger and N. Wormald", title = "Generating random regular graphs quickly", text = "Probability and Computing 8 (1999), 377-396.", year = "1999", url = "citeseer.ist.psu.edu/steger99generating.html", } |
random_shell_graph(constructor, seed=None)Return a random shell graph for the constructor given.
>>> constructor=[(10,20,0.8),(20,40,0.8)] >>> G=random_shell_graph(constructor) |
watts_strogatz_graph(n, k, p, seed=None)Return a Watts-Strogatz small world graph. The graph is a ring with k neighbors with edges rewired randomly with probability p.
|
Variable Details |
---|
__author__
|
__credits__
|
__date__
|
__revision__
|
Home | Trees | Index | Help |
|
---|
Generated by Epydoc 2.1 on Sun Aug 21 08:06:58 2005 | http://epydoc.sf.net |