Random Graphs Generators

Erdos.jl implements some common random graph generators:

# Erdos.barabasi_albert! — Method.

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.

source

# Erdos.barabasi_albert — Method.

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.

source

# Erdos.erdos_renyi — Method.

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.

source

# Erdos.random_configuration_model — Method.

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

Creates a random undirected graph according to the configuraton 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).

source

# Erdos.random_regular_digraph — Method.

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. The default is dir=:out.

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

source

# Erdos.random_regular_graph — Method.

random_regular_graph(n::Int, k::Int; 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.

source

# Erdos.static_fitness_model — Method.

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.

source

# Erdos.static_scale_free — Method.

function 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|).

function 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.

source

# Erdos.stochastic_block_model — Method.

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.

source

# Erdos.watts_strogatz — Method.

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).

source