Documentation

Overview

    Package gen provides random graph generation functions.

    Index

    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.