| Home | Trees | Indices | Help |
|---|
|
|
Date: $Date: 2005-06-17 08:06:22 -0600 (Fri, 17 Jun 2005) $
Author: Aric Hagberg (hagberg@lanl.gov) Pieter Swart (swart@lanl.gov) Dan Schult(dschult@colgate.edu)
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
__credits__ = |
|||
__revision__ = |
|||
|
|||
Return a random graph G_{n,p}. The G_{n,p} graph choses each of the possible [n(n-1)]/2 edges with probability p. Sometimes called Erdős-Rényi graph, or binomial graph. This algorithm is O(n+m) where m is the expected number of edges m=p*n*(n-1)/2. It should be faster than gnp_random_graph when p is small, and the expected number of edges is small, (sparse graph). See: Batagelj and Brandes, "Efficient generation of large random networks", Phys. Rev. E, 71, 036113, 2005.
|
Return a random graph G_{n,p}. Choses each of the possible [n(n-1)]/2 edges with probability p. This is the same as binomial_graph and erdos_renyi_graph. Sometimes called Erdős-Rényi graph, or binomial graph. This is an O(n^2) algorithm. For sparse graphs (small p) see fast_gnp_random_graph. P. Erdős and A. Rényi, On Random Graphs, Publ. Math. 6, 290 (1959). E. N. Gilbert, Random Graphs, Ann. Math. Stat., 30, 1141 (1959).
|
Return a random graph G_{n,p}. Choses each of the possible [n(n-1)]/2 edges with probability p. This is the same as binomial_graph and erdos_renyi_graph. Sometimes called Erdős-Rényi graph, or binomial graph. This is an O(n^2) algorithm. For sparse graphs (small p) see fast_gnp_random_graph. P. Erdős and A. Rényi, On Random Graphs, Publ. Math. 6, 290 (1959). E. N. Gilbert, Random Graphs, Ann. Math. Stat., 30, 1141 (1959).
|
Return a random graph G_{n,p}. Choses each of the possible [n(n-1)]/2 edges with probability p. This is the same as binomial_graph and erdos_renyi_graph. Sometimes called Erdős-Rényi graph, or binomial graph. This is an O(n^2) algorithm. For sparse graphs (small p) see fast_gnp_random_graph. P. Erdős and A. Rényi, On Random Graphs, Publ. Math. 6, 290 (1959). E. N. Gilbert, Random Graphs, Ann. Math. Stat., 30, 1141 (1959).
|
Return the random graph G_{n,m}. Gives a graph picked randomly out of the set of all graphs with n nodes and m edges. This algorithm should be faster than gnm_random_graph for dense graphs. Algorithm by Keith M. Briggs Mar 31, 2006. Inspired by Knuth's Algorithm S (Selection sampling technique), in section 3.4.2 of The Art of Computer Programming by Donald E. Knuth Volume 2 / Seminumerical algorithms Third Edition, Addison-Wesley, 1997.
|
Return the random graph G_{n,m}. Gives a graph picked randomly out of the set of all graphs with n nodes and m edges.
|
Return a Newman-Watts-Strogatz small world graph. First create a ring over n nodes. Then each node in the ring is connected with its k nearest neighbors. Then shortcuts are created by adding new edges as follows: for each edge u-v in the underlying "n-ring with k nearest neighbors"; with probability p add a new edge u-w with randomly-chosen existing node w. In contrast with watts_strogatz_graph(), no edges are removed.
|
Return a Watts-Strogatz small world graph. First create a ring over n nodes. Then each node in the ring is connected with its k nearest neighbors. Then shortcuts are created by rewiring existing edges as follows: for each edge u-v in the underlying "n-ring with k nearest neighbors"; with probability p replace u-v with a new edge u-w with randomly-chosen existing node w. In contrast with newman_watts_strogatz_graph(), the random rewiring does not increase the number of edges.
|
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",
}
|
Return random graph using Barabási-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 and no edges. Reference: @article{barabasi-1999-emergence,
title = {Emergence of scaling in random networks},
author = {A. L. Barabási and R. Albert},
journal = {Science},
volume = {286},
number = {5439},
pages = {509 -- 512},
year = {1999},
}
|
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. Note that the transitivity (fraction of triangles to possible triangles) seems to go down with network size. It is essentially the Barabási-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. It seems possible to have a disconnected graph with this algorithm since the initial m nodes may not be all linked to a new node on the first iteration like the BA model.
|
Return a random lobster. A caterpillar is a tree that reduces to a path graph when pruning all leaf nodes (p2=0). A lobster is a tree that reduces to a caterpillar when pruning all leaf nodes.
|
Return a random shell graph for the constructor given.
>>> constructor=[(10,20,0.8),(20,40,0.8)] >>> G=random_shell_graph(constructor) |
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).
|
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).
|
| Home | Trees | Indices | Help |
|---|
| Generated by Epydoc 3.0beta1 on Sun Aug 17 12:04:44 2008 | http://epydoc.sourceforge.net |