# Generators for common graphs

*Graphs.jl* defines generators for various families of deterministic and random graphs.

## Index

`Graphs.SimpleGraphs.SimpleDiGraph`

`Graphs.SimpleGraphs.SimpleGraph`

`Graphs.SimpleGraphs.SimpleGraph`

`Graphs.SimpleGraphs.SimpleGraph`

`Graphs.SimpleGraphs.StochasticBlockModel`

`Graphs.SimpleGraphs.barabasi_albert`

`Graphs.SimpleGraphs.barabasi_albert`

`Graphs.SimpleGraphs.barabasi_albert!`

`Graphs.SimpleGraphs.barbell_graph`

`Graphs.SimpleGraphs.binary_tree`

`Graphs.SimpleGraphs.blockcounts`

`Graphs.SimpleGraphs.circular_ladder_graph`

`Graphs.SimpleGraphs.clique_graph`

`Graphs.SimpleGraphs.complete_bipartite_graph`

`Graphs.SimpleGraphs.complete_digraph`

`Graphs.SimpleGraphs.complete_graph`

`Graphs.SimpleGraphs.complete_multipartite_graph`

`Graphs.SimpleGraphs.cycle_digraph`

`Graphs.SimpleGraphs.cycle_graph`

`Graphs.SimpleGraphs.dorogovtsev_mendes`

`Graphs.SimpleGraphs.double_binary_tree`

`Graphs.SimpleGraphs.erdos_renyi`

`Graphs.SimpleGraphs.erdos_renyi`

`Graphs.SimpleGraphs.euclidean_graph`

`Graphs.SimpleGraphs.euclidean_graph`

`Graphs.SimpleGraphs.expected_degree_graph`

`Graphs.SimpleGraphs.grid`

`Graphs.SimpleGraphs.kronecker`

`Graphs.SimpleGraphs.ladder_graph`

`Graphs.SimpleGraphs.lollipop_graph`

`Graphs.SimpleGraphs.make_edgestream`

`Graphs.SimpleGraphs.nearbipartiteaffinity`

`Graphs.SimpleGraphs.newman_watts_strogatz`

`Graphs.SimpleGraphs.path_digraph`

`Graphs.SimpleGraphs.path_graph`

`Graphs.SimpleGraphs.randbn`

`Graphs.SimpleGraphs.random_configuration_model`

`Graphs.SimpleGraphs.random_orientation_dag`

`Graphs.SimpleGraphs.random_pair`

`Graphs.SimpleGraphs.random_regular_digraph`

`Graphs.SimpleGraphs.random_regular_graph`

`Graphs.SimpleGraphs.random_tournament_digraph`

`Graphs.SimpleGraphs.roach_graph`

`Graphs.SimpleGraphs.sbmaffinity`

`Graphs.SimpleGraphs.smallgraph`

`Graphs.SimpleGraphs.star_digraph`

`Graphs.SimpleGraphs.star_graph`

`Graphs.SimpleGraphs.static_fitness_model`

`Graphs.SimpleGraphs.static_fitness_model`

`Graphs.SimpleGraphs.static_scale_free`

`Graphs.SimpleGraphs.static_scale_free`

`Graphs.SimpleGraphs.stochastic_block_model`

`Graphs.SimpleGraphs.stochastic_block_model`

`Graphs.SimpleGraphs.turan_graph`

`Graphs.SimpleGraphs.uniform_tree`

`Graphs.SimpleGraphs.watts_strogatz`

`Graphs.SimpleGraphs.wheel_digraph`

`Graphs.SimpleGraphs.wheel_graph`

## Full docs

`Graphs.SimpleGraphs.euclidean_graph`

— Method`euclidean_graph(N, d; rng=nothing, seed=nothing, L=1., p=2., cutoff=-1., bc=:open)`

Generate `N`

uniformly distributed points in the box $[0,L]^{d}$ and return a Euclidean graph, a map containing the distance on each edge and a matrix with the points' positions.

**Examples**

```
julia> using Graphs
julia> g, dists = euclidean_graph(5, 2, cutoff=0.3);
julia> g
{5, 4} undirected simple Int64 graph
julia> dists
Dict{Graphs.SimpleGraphs.SimpleEdge{Int64},Float64} with 4 entries:
Edge 1 => 5 => 0.205756
Edge 2 => 5 => 0.271359
Edge 2 => 4 => 0.247703
Edge 4 => 5 => 0.168372
```

`Graphs.SimpleGraphs.euclidean_graph`

— Method`euclidean_graph(points)`

Given the `d×N`

matrix `points`

build an Euclidean graph of `N`

vertices and return a graph and Dict containing the distance on each edge.

**Optional Arguments**

`L=1`

: used to bound the`d`

dimensional box from which points are selected.`p=2`

`bc=:open`

**Implementation Notes**

Defining the `d`

-dimensional vectors `x[i] = points[:,i]`

, an edge between vertices `i`

and `j`

is inserted if `norm(x[i]-x[j], p) < cutoff`

. In case of negative `cutoff`

instead every edge is inserted. For `p=2`

we have the standard Euclidean distance. Set `bc=:periodic`

to impose periodic boundary conditions in the box $[0,L]^d$.

**Examples**

```
julia> using Graphs
julia> pts = rand(3, 10); # 10 vertices in R^3
julia> g, dists = euclidean_graph(pts, p=1, bc=:periodic) # Taxicab-distance (L^1);
julia> g
{10, 45} undirected simple Int64 graph
```

`Graphs.SimpleGraphs.SimpleDiGraph`

— Method`SimpleDiGraph{T}(nv, ne; rng=nothing, seed=nothing)`

Construct a random `SimpleDiGraph{T}`

with `nv`

vertices and `ne`

edges. The graph is sampled uniformly from all such graphs. If `seed >= 0`

, a random generator is seeded with this value. If not specified, the element type `T`

is the type of `nv`

.

**See also**

**Examples**

```
julia> using Graphs
julia> SimpleDiGraph(5, 7)
{5, 7} directed simple Int64 graph
```

`Graphs.SimpleGraphs.SimpleGraph`

— Method`SimpleGraph{T}(nv, ne, edgestream::Channel)`

Construct a `SimpleGraph{T}`

with `nv`

vertices and `ne`

edges from `edgestream`

. Can result in less than `ne`

edges if the channel `edgestream`

is closed prematurely. Duplicate edges are only counted once. The element type is the type of `nv`

.

`Graphs.SimpleGraphs.SimpleGraph`

— Method`SimpleGraph{T}(nv, ne, smb::StochasticBlockModel)`

Construct a random `SimpleGraph{T}`

with `nv`

vertices and `ne`

edges. The graph is sampled according to the stochastic block model `smb`

. The element type is the type of `nv`

.

`Graphs.SimpleGraphs.SimpleGraph`

— Method`SimpleGraph{T}(nv, ne; rng=nothing, seed=nothing)`

Construct a random `SimpleGraph{T}`

with `nv`

vertices and `ne`

edges. The graph is sampled uniformly from all such graphs. If `seed >= 0`

, a random generator is seeded with this value. If not specified, the element type `T`

is the type of `nv`

.

**See also**

**Examples**

```
julia> using Graphs
julia> SimpleGraph(5, 7)
{5, 7} undirected simple Int64 graph
```

`Graphs.SimpleGraphs.StochasticBlockModel`

— Type`StochasticBlockModel{T,P}`

A type capturing the parameters of the SBM. Each vertex is assigned to a block and the probability of edge `(i,j)`

depends only on the block labels of vertex `i`

and vertex `j`

.

The assignment is stored in nodemap and the block affinities a `k`

by `k`

matrix is stored in affinities.

`affinities[k,l]`

is the probability of an edge between any vertex in block `k`

and any vertex in block `l`

.

**Implementation Notes**

Graphs are generated by taking random $i,j ∈ V$ and flipping a coin with probability `affinities[nodemap[i],nodemap[j]]`

.

`Graphs.SimpleGraphs.barabasi_albert!`

— Method`barabasi_albert!(g::AbstractGraph, n::Integer, k::Integer)`

Create a Barabási–Albert model random graph with `n`

vertices. It is grown by adding new vertices to an initial graph `g`

. Each new vertex is attached with `k`

edges to `k`

different vertices already present in the system by preferential attachment.

**Optional Arguments**

`rng=nothing`

: set the Random Number Generator.`seed=nothing`

: set the RNG seed.

**Examples**

```
julia> using Graphs
julia> g = cycle_graph(4)
{4, 4} undirected simple Int64 graph
julia> barabasi_albert!(g, 16, 3);
julia> g
{16, 40} undirected simple Int64 graph
```

`Graphs.SimpleGraphs.barabasi_albert`

— Method`barabasi_albert(n::Integer, n0::Integer, k::Integer)`

Create a Barabási–Albert model random graph with `n`

vertices. It is grown by adding new vertices to an initial graph with `n0`

vertices. Each new vertex is attached with `k`

edges to `k`

different vertices already present in the system by preferential attachment. Initial graphs are undirected and consist of isolated vertices by default.

**Optional Arguments**

`is_directed=false`

: if true, return a directed graph.`complete=false`

: if true, use a complete graph for the initial graph.`rng=nothing`

: set the Random Number Generator.`seed=nothing`

: set the RNG seed.

**Examples**

```
julia> using Graphs
julia> barabasi_albert(10, 3, 2)
{10, 14} undirected simple Int64 graph
julia> barabasi_albert(100, Int8(10), 3, is_directed=true, seed=123)
{100, 270} directed simple Int8 graph
```

`Graphs.SimpleGraphs.barabasi_albert`

— Method`barabasi_albert(n, k)`

Create a Barabási–Albert model random graph with `n`

vertices. It is grown by adding new vertices to an initial graph with `k`

vertices. Each new vertex is attached with `k`

edges to `k`

different vertices already present in the system by preferential attachment. Initial graphs are undirected and consist of isolated vertices by default.

**Optional Arguments**

`is_directed=false`

: if true, return a directed graph.`complete=false`

: if true, use a complete graph for the initial graph.`rng=nothing`

: set the Random Number Generator.`seed=nothing`

: set the RNG seed.

**Examples**

```
julia> using Graphs
julia> barabasi_albert(50, 3)
{50, 141} undirected simple Int64 graph
julia> barabasi_albert(100, Int8(10), is_directed=true, complete=true, seed=123)
{100, 990} directed simple Int8 graph
```

`Graphs.SimpleGraphs.blockcounts`

— Method`blockcounts(sbm, A)`

Count the number of edges that go between each block.

`Graphs.SimpleGraphs.dorogovtsev_mendes`

— Method`dorogovtsev_mendes(n)`

Generate a random `n`

vertex graph by the Dorogovtsev-Mendes method (with `n \ge 3`

).

The Dorogovtsev-Mendes process begins with a triangle graph and inserts `n-3`

additional vertices. Each time a vertex is added, a random edge is selected and the new vertex is connected to the two endpoints of the chosen edge. This creates graphs with many triangles and a high local clustering coefficient.

It is often useful to track the evolution of the graph as vertices are added, you can access the graph from the `t`

th stage of this algorithm by accessing the first `t`

vertices with `g[1:t]`

.

**References**

- http://graphstream-project.org/doc/Generators/Dorogovtsev-Mendes-generator/
- https://arxiv.org/pdf/cond-mat/0106144.pdf#page=24

**Examples**

```
julia> using Graphs
julia> dorogovtsev_mendes(10)
{10, 17} undirected simple Int64 graph
julia> dorogovtsev_mendes(11, seed=123)
{11, 19} undirected simple Int64 graph
```

`Graphs.SimpleGraphs.erdos_renyi`

— Method`erdos_renyi(n, ne::Integer)`

Create an Erdős–Rényi random graph with `n`

vertices and `ne`

edges.

**Optional Arguments**

`is_directed=false`

: if true, return a directed graph.`rng=nothing`

: set the Random Number Generator.`seed=nothing`

: set the RNG seed.

**Examples**

```
julia> using Graphs
julia> erdos_renyi(10, 30)
{10, 30} undirected simple Int64 graph
julia> erdos_renyi(10, 30, is_directed=true, seed=123)
{10, 30} directed simple Int64 graph
```

`Graphs.SimpleGraphs.erdos_renyi`

— Method`erdos_renyi(n, p::Real)`

Create an Erdős–Rényi random graph with `n`

vertices. Edges are added between pairs of vertices with probability `p`

.

Note that there exists another definition of the Erdös-Rényi model in which the total number of edges is kept constant, rather than the probability `p`

. To access this definition, use `erdos_renyi(n, ne::Integer)`

(specifically: `erdos_renyi(n, 1) != erdos_renyi(n, 1.0)`

).

**Optional Arguments**

`is_directed=false`

: if true, return a directed graph.`rng=nothing`

: set the Random Number Generator.`seed=nothing`

: set the RNG seed.

**Examples**

```
julia> using Graphs
julia> erdos_renyi(10, 0.5)
{10, 20} undirected simple Int64 graph
```

```
julia> using Graphs
julia> erdos_renyi(10, 0.5, is_directed=true, seed=123)
{10, 49} directed simple Int64 graph
```

`Graphs.SimpleGraphs.expected_degree_graph`

— Method`expected_degree_graph(ω)`

Given a vector of expected degrees `ω`

indexed by vertex, create a random undirected graph in which vertices `i`

and `j`

are connected with probability `ω[i]*ω[j]/sum(ω)`

.

**Optional Arguments**

`rng=nothing`

: set the Random Number Generator.`seed=nothing`

: set the RNG seed.

**Implementation Notes**

The algorithm should work well for `maximum(ω) << sum(ω)`

. As `maximum(ω)`

approaches `sum(ω)`

, some deviations from the expected values are likely.

**References**

- Connected Components in Random Graphs with Given Expected Degree Sequences, Linyuan Lu and Fan Chung. https://link.springer.com/article/10.1007%2FPL00012580
- Efficient Generation of Networks with Given Expected Degrees, Joel C. Miller and Aric Hagberg. https://doi.org/10.1007/978-3-642-21286-4_10

**Examples**

```
# 1)
julia> using Graphs
julia> g = expected_degree_graph([3, 1//2, 1//2, 1//2, 1//2])
{5, 3} undirected simple Int64 graph
julia> print(degree(g))
[3, 0, 1, 1, 1]
# 2)
julia> g = expected_degree_graph([0.5, 0.5, 0.5], seed=123)
{3, 1} undirected simple Int64 graph
julia> print(degree(g))
[1, 0, 1]
```

`Graphs.SimpleGraphs.kronecker`

— Function`kronecker(SCALE, edgefactor, A=0.57, B=0.19, C=0.19; rng=nothing, seed=nothing)`

Generate a directed Kronecker graph with the default Graph500 parameters.

References

- http://www.graph500.org/specifications#alg:generator

`Graphs.SimpleGraphs.make_edgestream`

— Method`make_edgestream(sbm; rng=nothing, seed=nothing)`

Take an infinite sample from the Stochastic Block Model `sbm`

. Pass to `Graph(nvg, neg, edgestream)`

to get a Graph object based on `sbm`

.

`Graphs.SimpleGraphs.nearbipartiteaffinity`

— Method`nearbipartiteaffinity(sizes, between, intra)`

Construct the affinity matrix for a near bipartite SBM. `between`

is the affinity between the two parts of each bipartite community. `intra`

is the probability of an edge within the parts of the partitions.

This is a specific type of SBM with ``\frac{k}{2} blocks each with two halves. Each half is connected as a random bipartite graph with probability`

intra`The blocks are connected with probability`

between`.

`Graphs.SimpleGraphs.newman_watts_strogatz`

— Method`newman_watts_strogatz(n, k, β)`

Return a Newman-Watts-Strogatz small world random graph with `n`

vertices, each with expected degree `k(1 + β)`

(or `(k - 1)(1 + β)`

if `k`

is odd). Edges are randomized per the model based on probability `β`

.

The algorithm proceeds as follows. First, a perfect 1-lattice is constructed, where each vertex has exacly `div(k, 2)`

neighbors on each side (i.e., `k`

or `k - 1`

in total). Then the following steps are repeated for a hop length `i`

of `1`

through `div(k, 2)`

.

Consider each vertex

`s`

in turn, along with the edge to its`i`

th nearest neighbor`t`

, in a clockwise sense.Generate a uniformly random number

`r`

. If`r < β`

,`s`

is connected to some vertex`d`

, chosen uniformly at random from the entire graph, excluding`s`

and its neighbors. (Note that`t`

is a valid candidate.)

For `β = 0`

, the graph will remain a 1-lattice, and for `β = 1`

, all edges will be rewired randomly.

Note: In the original paper by Newman and Watts, self-loops and double edges were allowed, which is not the case here. However, for large enough networks and small enough `p`

and `k`

, this should not deviate much from the original model.

**Optional Arguments**

`is_directed=false`

: if true, return a directed graph.`rng=nothing`

: set the Random Number Generator.`seed=nothing`

: set the RNG seed.

**Examples**

```
julia> using Graphs
julia> newman_watts_strogatz(10, 4, 0.3)
{10, 26} undirected simple Int64 graph
````
```

jldoctest

julia> newman*watts*strogatz(Int8(10), 4, 0.8, is_directed=true, seed=123) {10, 36} directed simple Int8 graph ```

**References**

- Scaling and percolation in the small-world network model, M. E. J. Newman, Duncan J. Watts. https://doi.org/10.1103/PhysRevE.60.7332

`Graphs.SimpleGraphs.randbn`

— Method`randbn(n, p; rng=nothing, seed=nothing)`

Return a binomially-distributed random number with parameters `n`

and `p`

and optional `seed`

.

**References**

- "Non-Uniform Random Variate Generation," Luc Devroye, p. 522. Retrieved via http://www.eirene.de/Devroye.pdf.
- http://stackoverflow.com/questions/23561551/a-efficient-binomial-random-number-generator-code-in-java

`Graphs.SimpleGraphs.random_configuration_model`

— Method`random_configuration_model(n, ks)`

Create a random undirected graph according to the configuration model containing `n`

vertices, with each node `i`

having degree `k[i]`

.

**Optional Arguments**

`rng=nothing`

: set the Random Number Generator.`seed=nothing`

: set the RNG seed.`check_graphical=false`

: if true, ensure that`k`

is a graphical sequence

(see `isgraphical`

).

**Performance**

Time complexity is approximately $\mathcal{O}(n \bar{k}^2)$.

**Implementation Notes**

Allocates an array of $n \bar{k}$ `Int`

s.

`Graphs.SimpleGraphs.random_orientation_dag`

— Method`random_orientation_dag(g)`

Generate a random oriented acyclical digraph. The function takes in a simple graph and a random number generator as an argument. The probability of each directional acyclic graph randomly being generated depends on the architecture of the original directed graph.

DAG's have a finite topological order; this order is randomly generated via "order = randperm()".

**Examples**

```
julia> using Graphs
julia> random_orientation_dag(complete_graph(10))
{10, 45} directed simple Int64 graph
julia> random_orientation_dag(star_graph(Int8(10)), seed=123)
{10, 9} directed simple Int8 graph
```

`Graphs.SimpleGraphs.random_pair`

— Method`random_pair(rng, n)`

Generate a stream of random pairs in `1:n`

using random number generator `RNG`

.

`Graphs.SimpleGraphs.random_regular_digraph`

— Method`random_regular_digraph(n, k)`

Create a random directed regular graph with `n`

vertices, each with degree `k`

.

**Optional Arguments**

`dir=:out`

: the direction of the edges for the degree parameter.`rng=nothing`

: set the Random Number Generator.`seed=nothing`

: set the RNG seed.

**Implementation Notes**

Allocates an $n × n$ sparse matrix of boolean as an adjacency matrix and uses that to generate the directed graph.

`Graphs.SimpleGraphs.random_regular_graph`

— Method`random_regular_graph(n, k)`

Create a random undirected regular graph with `n`

vertices, each with degree `k`

.

**Optional Arguments**

`rng=nothing`

: set the Random Number Generator.`seed=nothing`

: set the RNG seed.

**Performance**

Time complexity is approximately $\mathcal{O}(nk^2)$.

**Implementation Notes**

Allocates an array of `nk`

`Int`

s, and . For $k > \frac{n}{2}$, generates a graph of degree $n-k-1$ and returns its complement.

`Graphs.SimpleGraphs.random_tournament_digraph`

— Method`random_tournament_digraph(n)`

Create a random directed tournament graph with `n`

vertices.

**Optional Arguments**

`rng=nothing`

: set the Random Number Generator.`seed=nothing`

: set the RNG seed.

**Examples**

```
julia> using Graphs
julia> random_tournament_digraph(5)
{5, 10} directed simple Int64 graph
julia> random_tournament_digraph(Int8(10), seed=123)
{10, 45} directed simple Int8 graph
```

`Graphs.SimpleGraphs.sbmaffinity`

— Method`sbmaffinity(internalp, externalp, sizes)`

Produce the sbm affinity matrix with internal probabilities `internalp`

and external probabilities `externalp`

.

`Graphs.SimpleGraphs.static_fitness_model`

— Method`static_fitness_model(m, fitness)`

Generate a random graph with $|fitness|$ vertices and `m`

edges, in which the probability of the existence of $Edge_{ij}$ is proportional to $fitness_i × fitness_j$.

**Optional Arguments**

`rng=nothing`

: set the Random Number Generator.`seed=nothing`

: set the RNG seed.

**Performance**

Time complexity is $\mathcal{O}(|V| + |E| log |E|)$.

**References**

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

**Examples**

```
julia> g = static_fitness_model(5, [1, 1, 0.5, 0.1])
{4, 5} undirected simple Int64 graph
julia> edges(g) |> collect
5-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
Edge 1 => 2
Edge 1 => 3
Edge 1 => 4
Edge 2 => 3
Edge 2 => 4
```

```
julia> using Graphs
julia> g = static_fitness_model(5, [1, 1, 0.5, 0.1], seed=123)
{4, 5} undirected simple Int64 graph
julia> edges(g) |> collect
5-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
Edge 1 => 2
Edge 1 => 3
Edge 2 => 3
Edge 2 => 4
Edge 3 => 4
```

`Graphs.SimpleGraphs.static_fitness_model`

— Method`static_fitness_model(m, fitness_out, fitness_in)`

Generate a random directed graph with $|fitness\_out + fitness\_in|$ vertices and `m`

edges, in which the probability of the existence of $Edge_{ij}$ is proportional with respect to $i ∝ fitness\_out$ and $j ∝ fitness\_in$.

**Optional Arguments**

`rng=nothing`

: set the Random Number Generator.`seed=nothing`

: set the RNG seed.

**Performance**

Time complexity is $\mathcal{O}(|V| + |E| log |E|)$.

**References**

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

**Examples**

```
julia> using Graphs
julia> g = static_fitness_model(6, [1, 0.2, 0.2, 0.2], [0.1, 0.1, 0.1, 0.9]; seed=123)
{4, 6} directed simple Int64 graph
julia> edges(g) |> collect
6-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
Edge 1 => 2
Edge 1 => 3
Edge 1 => 4
Edge 2 => 3
Edge 2 => 4
Edge 3 => 4
```

`Graphs.SimpleGraphs.static_scale_free`

— Method`static_scale_free(n, m, α_out, α_in)`

Generate a random graph with `n`

vertices, `m`

edges and expected power-law degree distribution with exponent `α_out`

for outbound edges and `α_in`

for inbound edges.

**Optional Arguments**

`rng=nothing`

: set the Random Number Generator.`seed=nothing`

: set the RNG seed.`finite_size_correction=true`

: determines whether to use the finite size correction

proposed by Cho et al.

**Performance**

Time complexity is $\mathcal{O}(|V| + |E| log |E|)$.

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

`Graphs.SimpleGraphs.static_scale_free`

— Method`static_scale_free(n, m, α)`

Generate a random graph with `n`

vertices, `m`

edges and expected power-law degree distribution with exponent `α`

.

**Optional Arguments**

`rng=nothing`

: set the Random Number Generator.`seed=nothing`

: set the RNG seed.`finite_size_correction=true`

: determines whether to use the finite size correction

proposed by Cho et al.

**Performance**

Time complexity is $\mathcal{O}(|V| + |E| log |E|)$.

**References**

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

`Graphs.SimpleGraphs.stochastic_block_model`

— Method`stochastic_block_model(c, n)`

Return 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 triangular is determined by $c[b,a] = c[a,b] * \frac{n[a]}{n[b]}$. `n[a]`

: Number of vertices in block `a`

**Optional Arguments**

`rng=nothing`

: set the Random Number Generator.`seed=nothing`

: set the RNG seed.

For a dynamic version of the SBM see the `StochasticBlockModel`

type and related functions.

`Graphs.SimpleGraphs.stochastic_block_model`

— Method`stochastic_block_model(cint, cext, n)`

Return a Graph generated according to the Stochastic Block Model (SBM), sampling from an SBM with $c_{a,a}=cint$, and $c_{a,b}=cext$.

`Graphs.SimpleGraphs.uniform_tree`

— Method`uniform_tree(n)`

Generates a random labelled tree, drawn uniformly at random over the $n^{n-2}$ such trees. A uniform word of length `n-2`

over the alphabet `1:n`

is generated (Prüfer sequence) then decoded. See also the `prufer_decode`

function and this page on Prüfer codes.

**Optional Arguments**

`rng=nothing`

: set the Random Number Generator.

**Examples**

```
julia> using Graphs
julia> uniform_tree(10)
{10, 9} undirected simple Int64 graph
```

`Graphs.SimpleGraphs.watts_strogatz`

— Method`watts_strogatz(n, k, β)`

Return a Watts-Strogatz small world random graph with `n`

vertices, each with expected degree `k`

(or `k - 1`

if `k`

is odd). Edges are randomized per the model based on probability `β`

.

The algorithm proceeds as follows. First, a perfect 1-lattice is constructed, where each vertex has exacly `div(k, 2)`

neighbors on each side (i.e., `k`

or `k - 1`

in total). Then the following steps are repeated for a hop length `i`

of `1`

through `div(k, 2)`

.

Consider each vertex

`s`

in turn, along with the edge to its`i`

th nearest neighbor`t`

, in a clockwise sense.Generate a uniformly random number

`r`

. If`r ≥ β`

, then the edge`(s, t)`

is left unaltered. Otherwise, the edge is deleted and*rewired*so that`s`

is connected to some vertex`d`

, chosen uniformly at random from the entire graph, excluding`s`

and its neighbors. (Note that`t`

is a valid candidate.)

For `β = 0`

, the graph will remain a 1-lattice, and for `β = 1`

, all edges will be rewired randomly.

**Optional Arguments**

`remove_edges=true`

: if false, do not remove the original edges.`is_directed=false`

: if true, return a directed graph.`rng=nothing`

: set the Random Number Generator.`seed=nothing`

: set the RNG seed.

**Examples**

```
julia> using Graphs
julia> watts_strogatz(10, 4, 0.3)
{10, 20} undirected simple Int64 graph
julia> watts_strogatz(Int8(10), 4, 0.8, is_directed=true, seed=123)
{10, 20} directed simple Int8 graph
```

**References**

- Collective dynamics of ‘small-world’ networks, Duncan J. Watts, Steven H. Strogatz. https://doi.org/10.1038/30918
- Small Worlds, Duncan J. watts. https://en.wikipedia.org/wiki/Special:BookSources?isbn=978-0691005416

`Graphs.SimpleGraphs.smallgraph`

— Method```
smallgraph(s)
smallgraph(s)
```

Create a small graph of type `s`

. Admissible values for `s`

are:

`s` | graph type |
---|---|

:bull | A bull graph. |

:chvatal | A Chvátal graph. |

:cubical | A Platonic cubical graph. |

:desargues | A Desarguesgraph. |

:diamond | A diamond graph. |

:dodecahedral | A Platonic dodecahedral graph. |

:frucht | A Frucht graph. |

:heawood | A Heawood graph. |

:house | A graph mimicing the classic outline of a house. |

:housex | A house graph, with two edges crossing the bottom square. |

:icosahedral | A Platonic icosahedral graph. |

:karate | A social network graph called Zachary's karate club. |

:krackhardtkite | A Krackhardt-Kite social network graph. |

:moebiuskantor | A Möbius-Kantor graph. |

:octahedral | A Platonic octahedral graph. |

:pappus | A Pappus graph. |

:petersen | A Petersen graph. |

:sedgewickmaze | A simple maze graph used in Sedgewick's Algorithms in C++: Graph Algorithms (3rd ed.) |

:tetrahedral | A Platonic tetrahedral graph. |

:truncatedcube | A skeleton of the truncated cube graph. |

:truncatedtetrahedron | A skeleton of the truncated tetrahedron graph. |

:truncatedtetrahedron_dir | A skeleton of the truncated tetrahedron digraph. |

:tutte | A Tutte graph. |

`Graphs.SimpleGraphs.barbell_graph`

— Method`barbell_graph(n1, n2)`

Create a barbell graph consisting of a clique of size `n1`

connected by an edge to a clique of size `n2`

.

**Implementation Notes**

Preserves the eltype of `n1`

and `n2`

. Will error if the required number of vertices exceeds the eltype. `n1`

and `n2`

must be at least 1 so that both cliques are non-empty. The cliques are organized with nodes `1:n1`

being the left clique and `n1+1:n1+n2`

being the right clique. The cliques are connected by and edge `(n1, n1+1)`

.

**Examples**

```
julia> using Graphs
julia> barbell_graph(3, 4)
{7, 10} undirected simple Int64 graph
julia> barbell_graph(Int8(5), Int8(5))
{10, 21} undirected simple Int8 graph
```

`Graphs.SimpleGraphs.binary_tree`

— Method`binary_tree(k::Integer)`

Create a binary tree of depth `k`

.

**Examples**

```
julia> using Graphs
julia> binary_tree(4)
{15, 14} undirected simple Int64 graph
julia> binary_tree(Int8(5))
{31, 30} undirected simple Int8 graph
```

`Graphs.SimpleGraphs.circular_ladder_graph`

— Method`circular_ladder_graph(n)`

Create a circular ladder graph consisting of `2n`

nodes and `3n`

edges. This is also known as the prism graph.

**Implementation Notes**

Preserves the eltype of the partitions vector. Will error if the required number of vertices exceeds the eltype. `n`

must be at least 3 to avoid self-loops and multi-edges.

**Examples**

```
julia> using Graphs
julia> circular_ladder_graph(3)
{6, 9} undirected simple Int64 graph
julia> circular_ladder_graph(Int8(4))
{8, 12} undirected simple Int8 graph
```

`Graphs.SimpleGraphs.clique_graph`

— Method`clique_graph(k, n)`

Create a graph consisting of `n`

connected `k`

-cliques.

**Examples**

```
julia> using Graphs
julia> clique_graph(4, 10)
{40, 70} undirected simple Int64 graph
julia> clique_graph(Int8(10), Int8(4))
{40, 184} undirected simple Int8 graph
```

`Graphs.SimpleGraphs.complete_bipartite_graph`

— Method`complete_bipartite_graph(n1, n2)`

Create an undirected complete bipartite graph with `n1 + n2`

vertices.

**Examples**

```
julia> using Graphs
julia> complete_bipartite_graph(3, 4)
{7, 12} undirected simple Int64 graph
julia> complete_bipartite_graph(Int8(3), Int8(4))
{7, 12} undirected simple Int8 graph
```

`Graphs.SimpleGraphs.complete_digraph`

— Method`complete_digraph(n)`

Create a directed complete graph with `n`

vertices.

**Examples**

```
julia> using Graphs
julia> complete_digraph(5)
{5, 20} directed simple Int64 graph
julia> complete_digraph(Int8(6))
{6, 30} directed simple Int8 graph
```

`Graphs.SimpleGraphs.complete_graph`

— Method`complete_graph(n)`

Create an undirected complete graph with `n`

vertices.

**Examples**

```
julia> using Graphs
julia> complete_graph(5)
{5, 10} undirected simple Int64 graph
julia> complete_graph(Int8(6))
{6, 15} undirected simple Int8 graph
```

`Graphs.SimpleGraphs.complete_multipartite_graph`

— Method`complete_multipartite_graph(partitions)`

Create an undirected complete bipartite graph with `sum(partitions)`

vertices. A partition with `0`

vertices is skipped.

**Implementation Notes**

Preserves the eltype of the partitions vector. Will error if the required number of vertices exceeds the eltype.

**Examples**

```
julia> using Graphs
julia> complete_multipartite_graph([1,2,3])
{6, 11} undirected simple Int64 graph
julia> complete_multipartite_graph(Int8[5,5,5])
{15, 75} undirected simple Int8 graph
```

`Graphs.SimpleGraphs.cycle_digraph`

— Method`cycle_digraph(n)`

Create a directed cycle graph with `n`

vertices.

**Examples**

```
julia> using Graphs
julia> cycle_digraph(3)
{3, 3} directed simple Int64 graph
julia> cycle_digraph(Int8(5))
{5, 5} directed simple Int8 graph
```

`Graphs.SimpleGraphs.cycle_graph`

— Method`cycle_graph(n)`

Create an undirected cycle graph with `n`

vertices.

**Examples**

```
julia> using Graphs
julia> cycle_graph(3)
{3, 3} undirected simple Int64 graph
julia> cycle_graph(Int8(5))
{5, 5} undirected simple Int8 graph
```

`Graphs.SimpleGraphs.double_binary_tree`

— Method`double_binary_tree(k::Integer)`

Create a double complete binary tree with `k`

levels.

**References**

- Used as an example for spectral clustering by Guattery and Miller 1998.

**Examples**

```
julia> using Graphs
julia> double_binary_tree(4)
{30, 29} undirected simple Int64 graph
julia> double_binary_tree(Int8(5))
{62, 61} undirected simple Int8 graph
```

`Graphs.SimpleGraphs.grid`

— Method`grid(dims; periodic=false)`

Create a $|dims|$-dimensional cubic lattice, with length `dims[i]`

in dimension `i`

.

**Optional Arguments**

`periodic=false`

: If true, the resulting lattice will have periodic boundary

condition in each dimension.

**Examples**

```
julia> using Graphs
julia> grid([2,3])
{6, 7} undirected simple Int64 graph
julia> grid(Int8[2, 2, 2], periodic=true)
{8, 12} undirected simple Int8 graph
julia> grid((2,3))
{6, 7} undirected simple Int64 graph
```

`Graphs.SimpleGraphs.ladder_graph`

— Method`ladder_graph(n)`

Create a ladder graph consisting of `2n`

nodes and `3n-2`

edges.

**Implementation Notes**

Preserves the eltype of `n`

. Will error if the required number of vertices exceeds the eltype.

**Examples**

```
julia> using Graphs
julia> ladder_graph(3)
{6, 7} undirected simple Int64 graph
julia> ladder_graph(Int8(4))
{8, 10} undirected simple Int8 graph
```

`Graphs.SimpleGraphs.lollipop_graph`

— Method`lollipop_graph(n1, n2)`

Create a lollipop graph consisting of a clique of size `n1`

connected by an edge to a path of size `n2`

.

**Implementation Notes**

Preserves the eltype of `n1`

and `n2`

. Will error if the required number of vertices exceeds the eltype. `n1`

and `n2`

must be at least 1 so that both the clique and the path have at least one vertex. The graph is organized with nodes `1:n1`

being the clique and `n1+1:n1+n2`

being the path. The clique is connected to the path by an edge `(n1, n1+1)`

.

**Examples**

```
julia> using Graphs
julia> lollipop_graph(2, 5)
{7, 6} undirected simple Int64 graph
julia> lollipop_graph(Int8(3), Int8(4))
{7, 7} undirected simple Int8 graph
```

`Graphs.SimpleGraphs.path_digraph`

— Method`path_digraph(n)`

Creates a directed path graph with `n`

vertices.

**Examples**

```
julia> using Graphs
julia> path_digraph(5)
{5, 4} directed simple Int64 graph
julia> path_digraph(Int8(10))
{10, 9} directed simple Int8 graph
```

`Graphs.SimpleGraphs.path_graph`

— Method`path_graph(n)`

Create an undirected path graph with `n`

vertices.

**Examples**

```
julia> using Graphs
julia> path_graph(5)
{5, 4} undirected simple Int64 graph
julia> path_graph(Int8(10))
{10, 9} undirected simple Int8 graph
```

`Graphs.SimpleGraphs.roach_graph`

— Method`roach_graph(k)`

Create a Roach graph of size `k`

.

**References**

- Guattery and Miller 1998

**Examples**

```
julia> using Graphs
julia> roach_graph(10)
{40, 48} undirected simple Int64 graph
```

`Graphs.SimpleGraphs.star_digraph`

— Method`star_digraph(n)`

Create a directed star graph with `n`

vertices.

**Examples**

```
julia> using Graphs
julia> star_digraph(3)
{3, 2} directed simple Int64 graph
julia> star_digraph(Int8(10))
{10, 9} directed simple Int8 graph
```

`Graphs.SimpleGraphs.star_graph`

— Method`star_graph(n)`

Create an undirected star graph with `n`

vertices.

**Examples**

```
julia> using Graphs
julia> star_graph(3)
{3, 2} undirected simple Int64 graph
julia> star_graph(Int8(10))
{10, 9} undirected simple Int8 graph
```

`Graphs.SimpleGraphs.turan_graph`

— Method`turan_graph(n, r)`

Creates a Turán Graph, a complete multipartite graph with `n`

vertices and `r`

partitions.

**Examples**

```
julia> using Graphs
julia> turan_graph(6, 2)
{6, 9} undirected simple Int64 graph
julia> turan_graph(Int8(7), 2)
{7, 12} undirected simple Int8 graph
```

`Graphs.SimpleGraphs.wheel_digraph`

— Method`wheel_digraph(n)`

Create a directed wheel graph with `n`

vertices.

**Examples**

```
julia> using Graphs
julia> wheel_digraph(5)
{5, 8} directed simple Int64 graph
julia> wheel_digraph(Int8(6))
{6, 10} directed simple Int8 graph
```

`Graphs.SimpleGraphs.wheel_graph`

— Method`wheel_graph(n)`

Create an undirected wheel graph with `n`

vertices.

**Examples**

```
julia> using Graphs
julia> wheel_graph(5)
{5, 8} undirected simple Int64 graph
julia> wheel_graph(Int8(6))
{6, 10} undirected simple Int8 graph
```