rustworkx.undirected_gnp_random_graph#
- undirected_gnp_random_graph(num_nodes, probability, /, seed=None)#
Return a \(G_{np}\) random undirected 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)/2\) 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)/2\). 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 undirected graph has \(n (n - 1)/2\) 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)/2)\), 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 PyGraph object
- Return type: