fast_gnp_random_graph(n, p, seed=None, directed=False)[source]

Returns a \(G_{n,p}\) random graph, also known as an Erdős-Rényi graph or a binomial graph.

  • n (int) – The number of nodes.

  • p (float) – Probability for edge creation.

  • seed (integer, random_state, or None (default)) – Indicator of random number generation state. See Randomness.

  • directed (bool, optional (default=False)) – If True, this function returns a directed graph.


The \(G_{n,p}\) graph algorithm chooses each of the \([n (n - 1)] / 2\) (undirected) or \(n (n - 1)\) (directed) possible edges with probability \(p\).

This algorithm 1 runs in \(O(n + m)\) time, where m is the expected number of edges, which equals \(p n (n - 1) / 2\). This should be faster than gnp_random_graph() when \(p\) is small and the expected number of edges is small (that is, the graph is sparse).



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