Random Graphs

The group :graph contains generators of adjacency matrices of random graphs. They are returned as sparse matrices:

using MatrixDepot, Random
Random.seed!(0)
matrixdepot("erdrey", Int8, 5, 3)

5×5 SparseArrays.SparseMatrixCSC{Int8, Int64} with 6 stored entries:
 ⋅  1  ⋅  ⋅  ⋅
 1  ⋅  ⋅  1  ⋅
 ⋅  ⋅  ⋅  ⋅  1
 ⋅  1  ⋅  ⋅  ⋅
 ⋅  ⋅  1  ⋅  ⋅

erdrey

MatrixDepot.erdrey — Function

Erdos-Renyi Random Graph

Generate an adjacency matrix of an Edros-Renyi random graph: an undirected graph is chosen uniformly at random from the set of all symmetric graphs with n nodes and m edges.

Input options:

[type,] n, m: the dimension of the matrix is n. The number of 1's in the matrix is 2*m.
[type,] n: m = ceil(Int, n*log(n)/2).

Groups: ["sparse", "graph"]

References:

P. Erdos and A. Renyi, On Random Graphs, Publ. Math. Debrecen, 6, 1959, pp. 290-297

source

gilbert

MatrixDepot.gilbert — Function

Gilbert Random Graph

Generate an adjecency matrix of a Gilbert random graph: an undirected graph with pairs of nodes are connected with independent probability p.

Input options:

[type,] n, p: the dimension of the matrix is n and the probability that any two nodes are connected is p.
[type,] n: p = log(n)/n.

Groups: ["sparse", "graph"]

References:

E.N. Gilbert, Random Graphs, Ann. Math. Statist., 30, (1959) pp. 1141-1144.

source

smallworld

MatrixDepot.smallworld — Function

Small World Network

Generate an adjacency matrix for a small world network. We model it by adding shortcuts to a kth nearest neighbour ring network (nodes i and j are connected iff |i -j| <= k or |n - |i -j|| <= k.) with n nodes.

Input options:

[type,] n, k, p: the dimension of the matrix is n. The number of nearest-neighbours to connect is k. The probability of adding a shortcut in a given row is p.
[type,] n: k = 2 and p = 0.1.

References:

D. J. Watts and S. H. Strogatz, Collective Dynamics of Small World Networks, Nature 393 (1998), pp. 440-442.

source