Warning

The documentation for retworkx has migrated to:

https://qiskit.org/documentation/retworkx

These docs will no longer be updated.

retworkx.directed_gnp_random_graph¶

directed_gnp_random_graph(num_nodes, probability, seed=None, /)

Return a $$G_{np}$$ directed random graph, also known as an Erdős-Rényi graph or a binomial graph.

For number of nodes $$n$$ and probability $$p$$, the $$G_{n,p}$$ graph algorithm creates $$n$$ nodes, and for all the $$n (n - 1)$$ possible edges, each edge is created independently with probability $$p$$. In general, for any probability $$p$$, the expected number of edges returned is $$m = p n (n - 1)$$. If $$p = 0$$ or $$p = 1$$, the returned graph is not random and will always be an empty or a complete graph respectively. An empty graph has zero edges and a complete directed graph has $$n (n - 1)$$ edges. The run time is $$O(n + m)$$ where $$m$$ is the expected number of edges mentioned above. When $$p = 0$$, run time always reduces to $$O(n)$$, as the lower bound. When $$p = 1$$, run time always goes to $$O(n + n (n - 1))$$, as the upper bound. For other probabilities, this algorithm 1 runs in $$O(n + m)$$ time.

For $$0 < p < 1$$, the algorithm is based on the implementation of the networkx function fast_gnp_random_graph 2

Parameters
• num_nodes (int) – The number of nodes to create in the graph

• probability (float) – The probability of creating an edge between two nodes

• seed (int) – An optional seed to use for the random number generator

Returns

A PyDiGraph object

Return type

PyDiGraph

1

Vladimir Batagelj and Ulrik Brandes, “Efficient generation of large random networks”, Phys. Rev. E, 71, 036113, 2005.

2

https://github.com/networkx/networkx/blob/networkx-2.4/networkx/generators/random_graphs.py#L49-L120