Random Graphs Generators

barabasi_albert!(g, n::Int, k::Int; seed::Int = -1)

Grows the graph g according to Barabási–Albert process into a graph with n vertices. At each step a new vertex is attached by preferential attachment to k different vertices already present in the graph.

See also barabasi_albert.

barabasi_albert(n, k, G=Graph; seed=-1)
barabasi_albert(n, n0, k, G=Graph; seed=-1)

Creates a random graph of type G with n vertices according to Barabási–Albert model. It is grown by adding new vertices to an initial graph with n0 vertices (n0=k if not specified). Each new vertex is attached with k edges to k different vertices already present in the system by preferential attachment. The initial graph is empty by default.

Undirected graphs are created by default. Directed graphs can be created passing a directed graph type as last argument (e.g. DiGraph).

See also barabasi_albert! for growing a given graph.

erdos_renyi(n::Int, p::Real, G=Graph; seed=-1)
erdos_renyi(n::Int, m::Int, G=Graph; seed=-1)

Creates an Erdős–Rényi random graph of type G with n vertices. Edges are added between pairs of vertices with probability p in the first method. In the second method m edges are randomly chosen insted.

Undirected graphs are created by default. Directed graphs can be created passing a directed graph type as last argument (e.g. DiGraph)

Note also that Erdős–Rényi graphs may be generated quickly using erdos_renyi(n, ne) or the Graph(nv, ne) constructor, which randomly select ne edges among all the potential edges.

random_bipartite_configuration_model(
                                n1::Int, n2::Int, 
                                k1::Vector{Int}, k2::Vector{Int}, 
                                G=Graph; seed=-1)

Create a random bipartie undirected graph according to the configuration model. It contains n1+n2 vertices. The vertex i in the first set will have degree k1[i], while the vertex i in the second set will have degree k2[i].

G is the resulting graph type.

random_bipartite_regular_graph(n1, n2, k1, k2, G=Graph; seed=-1)

Creates a random undirected nipartite regular graph with n1+n2 vertices, the first n1 with degree k1, the others with degree k2

See also random_regular_graph and random_bipartite_configuration_model.

random_configuration_model(n::Int, k::Vector{Int}, G=Graph; seed=-1, check_graphical=false)

Creates a random undirected graph according to the configuration model. It contains n vertices, the vertex i having degree k[i].

Defining c = mean(k), it allocates an array of nc Ints, and takes approximately $nc^2$ time.

If check_graphical=true makes sure that k is a graphical sequence (see is_graphical).

G is the resulting graph type.

random_regular_digraph(n::Int, k::Int; dir::Symbol=:out, seed=-1)

Creates a random directed regular graph with n vertices, each with degree k. The degree (in or out) can be specified using dir=:in or dir=:out.

For directed graphs, allocates an $n imes n$ sparse matrix of boolean as an adjacency matrix and uses that to generate the graph.

random_regular_graph(n::Int, k::Int, G=Graph; seed=-1)

Creates a random undirected regular graph with n vertices, each with degree k.

For undirected graphs, allocates an array of nk Ints, and takes approximately $nk^2$ time. For $k > n/2$, generates a graph of degree n-k-1 and returns its complement.

G is the resulting graph type.

static_fitness_model(m, fitness, G=Graph; seed=-1)
static_fitness_model(m, fitness_out, fitness_in, G=DiGraph; seed=-1)

Generates a random graph with length(fitness) nodes and m edges, in which the probability of the existence of edge (i, j) is proportional to fitness[i]*fitness[j]. Time complexity is O(|V| + |E| log |E|).

In and out fitness have to be supplied for generating directed graphs.

Reference:

• Goh K-I, Kahng B, Kim D: Universal behaviour of load distribution

in scale-free networks. Phys Rev Lett 87(27):278701, 2001.

static_scale_free(n, m, α, G=Graph;
                seed=-1, finite_size_correction=true)

Generates a random graph with n vertices, m edges and expected power-law degree distribution with exponent α. finite_size_correction determines whether to use the finite size correction proposed by Cho et al. This generator calls internally the static_fitness_model function. Time complexity is O(|V| + |E| log |E|).

static_scale_free(n, m, α_out, α_in, G=DiGraph;
                seed=-1, finite_size_correction=true)

Generates a random digraph.

References:

• Goh K-I, Kahng B, Kim D: Universal behaviour of load distribution in scale-free networks. Phys Rev Lett 87(27):278701, 2001.

• Chung F and Lu L: Connected components in a random graph with given degree sequences. Annals of Combinatorics 6, 125-145, 2002.

• Cho YS, Kim JS, Park J, Kahng B, Kim D: Percolation transitions in scale-free networks under the Achlioptas process. Phys Rev Lett 103:135702, 2009.

stochastic_block_model(c::Matrix{Float64}, n::Vector{Int}; seed::Int = -1)
stochastic_block_model(cin::Float64, coff::Float64, n::Vector{Int}; seed::Int = -1)

Returns a Graph generated according to the Stochastic Block Model (SBM).

c[a,b] : Mean number of neighbors of a vertex in block a belonging to block b. Only the upper triangular part is considered, since the lower traingular is determined by $c[b,a] = c[a,b] * n[a]/n[b]$. n[a] : Number of vertices in block a

The second form samples from a SBM with c[a,a]=cin, and c[a,b]=coff.

For a dynamic version of the SBM see the StochasticBlockModel type and related functions.

watts_strogatz(n, k, β, G=Graph; seed=-1)

Creates a Watts-Strogatz small model random graph with n vertices, each with degree k. Edges are randomized per the model based on probability β.

Undirected graphs are created by default. Directed graphs can be created passing a directed graph type as last argument (e.g. DiGraph).