onyx.graph.randomgraph – This module has tools that support the generation of random graphs.

onyx.graph.randomgraph.make_ErdosRenyi(num_nodes, edge_prob, seed=None)

Creates an Erdos-Renyi random graph with num_nodes nodes and independent edge_prob probability of presence in the graph for each of the binomial “num_nodes choose two” possible edges in the graph.

Returns a Numpy array of integers with shape (2, num_edges) specifying the resulting random set of edges of the graph. Each pair of integers on the first axis specifies an edge, where each integer is in the inclusive range (0, num_nodes - 1). This shape is suitable for use in the constructors of sparse matrices in the scipy.sparse package.

If optional seed is anything other than None then the random results will be repeatable.

>>> make_ErdosRenyi(20, 0.05, seed=2)
array([[ 0,  3,  3,  4,  4,  5,  8,  9, 10, 10, 11, 13, 17, 18],
       [ 2,  5, 17, 12, 16, 12, 11, 13, 13, 17, 14, 17, 19, 19]])

There are many interesting properties of Erdos-Renyi graphs. Two of them are:

1. the almost sure probability that an ER graph will have no isolated nodes if edge_prob > log(num_nodes) / num_nodes
2. the almost sure probability that an ER graph will have some isolated nodes if edge_prob < log(num_nodes) / num_nodes.

>>> num_nodes = 1000
>>> import math
>>> isolated_threshold = math.log(num_nodes) / num_nodes
>>> isolated_threshold 
0.0069...

An edge_prob greater than the threshold gives a high probability of zero isolated nodes

>>> er1 = make_ErdosRenyi(num_nodes, 1.125 * isolated_threshold, seed=0)
>>> er1.shape[-1]
3918
>>> len(set(xrange(num_nodes)) - set(er1.flat))
0

An edge_prob less than the threshold gives a high probability of some isolated nodes

>>> er2 = make_ErdosRenyi(num_nodes, 0.872 * isolated_threshold, seed=0)
>>> er2.shape[-1]
3054
>>> len(set(xrange(num_nodes)) - set(er2.flat))
2