random_regular_graph#

random_regular_graph(d, n, seed=None, *, create_using=None)[source]#

Returns a random d-regular graph on n nodes.

A regular graph is a graph where each node has the same number of neighbors.

The resulting graph has no self-loops or parallel edges.

Parameters:
dint

The degree of each node.

ninteger

The number of nodes. The value of n×d must be even.

seedinteger, random_state, or None (default)

Indicator of random number generation state. See Randomness.

create_usingGraph constructor, optional (default=nx.Graph)

Graph type to create. If graph instance, then cleared before populated. Multigraph and directed types are not supported and raise a NetworkXError.

Raises:
NetworkXError

If n×d is odd or d is greater than or equal to n.

Notes

The nodes are numbered from 0 to n1.

Kim and Vu’s paper [2] shows that this algorithm samples in an asymptotically uniform way from the space of random graphs when d=O(n1/3ϵ).

References

[1]

A. Steger and N. Wormald, Generating random regular graphs quickly, Probability and Computing 8 (1999), 377-396, 1999. https://doi.org/10.1017/S0963548399003867

[2]

Jeong Han Kim and Van H. Vu, Generating random regular graphs, Proceedings of the thirty-fifth ACM symposium on Theory of computing, San Diego, CA, USA, pp 213–222, 2003. http://portal.acm.org/citation.cfm?id=780542.780576