Version: v0.0.1 Latest Latest Go to latest
Published: Aug 16, 2019 License: BSD-3-Clause Documentation ¶

Overview ¶

Package gen provides random graph generation functions.

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 ¶

func Duplication(dst UndirectedMutator, n int, delta, alpha, sigma float64, src rand.Source) error

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 ¶

func Gnp(dst graph.Builder, n int, p float64, src rand.Source) error

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(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 ¶

func PowerLaw(dst graph.MultigraphBuilder, n, d int, src rand.Source) error

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 ¶

func PreferentialAttachment(dst graph.UndirectedBuilder, n, m int, src rand.Source) error

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 ¶

func SmallWorldsBB(dst GraphBuilder, n, d int, p float64, src rand.Source) error

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 ¶

type GraphBuilder interface {
HasEdgeBetween(xid, yid int64) bool
graph.Builder
}

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.