rustworkx.undirected_gnp_random_graph#

undirected_gnp_random_graph(num_nodes, probability, /, seed=None)#

Return a $G_{n p}$ 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:

PyGraph