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