Documentation
¶
Overview ¶
Package gen provides random graph generation functions.
Index ¶
- func BipartitePowerLaw(dst graph.MultigraphBuilder, n, d int, src rand.Source) (p1, p2 []graph.Node, err error)
- func Duplication(dst UndirectedMutator, n int, delta, alpha, sigma float64, src rand.Source) error
- func Gnm(dst GraphBuilder, n, m int, src rand.Source) error
- func Gnp(dst graph.Builder, n int, p float64, src rand.Source) error
- func NavigableSmallWorld(dst GraphBuilder, dims []int, p, q int, r float64, src rand.Source) (err error)
- func PowerLaw(dst graph.MultigraphBuilder, n, d int, src rand.Source) error
- func PreferentialAttachment(dst graph.UndirectedBuilder, n, m int, src rand.Source) error
- func SmallWorldsBB(dst GraphBuilder, n, d int, p float64, src rand.Source) error
- func TunableClusteringScaleFree(dst graph.UndirectedBuilder, n, m int, p float64, src rand.Source) error
- type GraphBuilder
- type UndirectedMutator
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func BipartitePowerLaw ¶
func BipartitePowerLaw(dst graph.MultigraphBuilder, n, d int, src rand.Source) (p1, p2 []graph.Node, err error)
BipartitePowerLaw constructs a bipartite power-law degree graph by preferential attachment in dst with 2×n nodes and minimum degree d. BipartitePowerLaw does not consider nodes in dst prior to the call. The two partitions are returned in p1 and p2. If src is not nil it is used as the random source, otherwise rand.Intn is used. The graph is constructed in O(nd) — O(n+m) — time.
The algorithm used is described in http://algo.uni-konstanz.de/publications/bb-eglrn-05.pdf
func Duplication ¶
Duplication constructs a graph in the destination, dst, of order n. New nodes are created by duplicating an existing node and all its edges. Each new edge is deleted with probability delta. Additional edges are added between the new node and existing nodes with probability alpha/|V|. An exception to this addition rule is made for the parent node when sigma is not NaN; in this case an edge is created with probability sigma. With the exception of the sigma parameter, this corresponds to the completely correlated case in doi:10.1016/S0022-5193(03)00028-6. If src is not nil it is used as the random source, otherwise rand.Float64 is used.
func Gnm ¶
func Gnm(dst GraphBuilder, n, m int, src rand.Source) error
Gnm constructs a Erdős-Rényi model subgraph in the destination, dst, of order n and size m. If src is not nil it is used as the random source, otherwise rand.Intn is used. The graph is constructed in O(m) expected time for m ≤ (n choose 2)/2.
func Gnp ¶
Gnp constructs a Gilbert’s model subgraph in the destination, dst, of order n. Edges between nodes are formed with the probability, p. If src is not nil it is used as the random source, otherwise rand.Float64 is used. The graph is constructed in O(n+m) time where m is the number of edges added.
func NavigableSmallWorld ¶
func NavigableSmallWorld(dst GraphBuilder, dims []int, p, q int, r float64, src rand.Source) (err error)
NavigableSmallWorld constructs an N-dimensional grid with guaranteed local connectivity and random long-range connectivity as a subgraph in the destination, dst. The dims parameters specifies the length of each of the N dimensions, p defines the Manhattan distance between local nodes, and q defines the number of out-going long-range connections from each node. Long-range connections are made with a probability proportional to |d(u,v)|^-r where d is the Manhattan distance between non-local nodes.
The algorithm is essentially as described on p4 of http://www.cs.cornell.edu/home/kleinber/swn.pdf.
func PowerLaw ¶
PowerLaw constructs a power-law degree graph by preferential attachment in dst with n nodes and minimum degree d. PowerLaw does not consider nodes in dst prior to the call. If src is not nil it is used as the random source, otherwise rand.Intn is used. The graph is constructed in O(nd) — O(n+m) — time.
The algorithm used is described in http://algo.uni-konstanz.de/publications/bb-eglrn-05.pdf
func PreferentialAttachment ¶
PreferentialAttachment constructs a graph in the destination, dst, of order n. The graph is constructed successively starting from an m order graph with one node having degree m-1. At each iteration of graph addition, one node is added with m additional edges joining existing nodes with probability proportional to the nodes' degrees. If src is not nil it is used as the random source, otherwise rand.Float64 is used for the random number generator.
The algorithm is essentially as described in http://arxiv.org/abs/cond-mat/0110452 after 10.1126/science.286.5439.509.
func SmallWorldsBB ¶
SmallWorldsBB constructs a small worlds subgraph of order n in the destination, dst. Node degree is specified by d and edge replacement by the probability, p. If src is not nil it is used as the random source, otherwise rand.Float64 is used. The graph is constructed in O(nd) time.
The algorithm used is described in http://algo.uni-konstanz.de/publications/bb-eglrn-05.pdf
func TunableClusteringScaleFree ¶
func TunableClusteringScaleFree(dst graph.UndirectedBuilder, n, m int, p float64, src rand.Source) error
TunableClusteringScaleFree constructs a subgraph in the destination, dst, of order n. The graph is constructed successively starting from an m order graph with one node having degree m-1. At each iteration of graph addition, one node is added with m additional edges joining existing nodes with probability proportional to the nodes' degrees. The edges are formed as a triad with probability, p. If src is not nil it is used as the random source, otherwise rand.Float64 and rand.Intn are used for the random number generators.
The algorithm is essentially as described in http://arxiv.org/abs/cond-mat/0110452.
Types ¶
type GraphBuilder ¶
GraphBuilder is a graph that can have nodes and edges added.
type UndirectedMutator ¶
type UndirectedMutator interface {
graph.UndirectedBuilder
graph.EdgeRemover
}
UndirectedMutator is an undirected graph builder that can remove edges.
Source Files