random_regular_graph

random_regular_graph(d, n, seed=None)

Returns a random \(d\)-regular graph on \(n\) nodes.

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 \times d\) must be even.

seedinteger, random_state, or None (default)

Indicator of random number generation state. See Randomness.

Raises

NetworkXError

If \(n \times d\) is odd or \(d\) is greater than or equal to \(n\).

Notes

The nodes are numbered from \(0\) to \(n - 1\).

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(n^{1 / 3 - \epsilon})\).

References

1

A. Steger and N. Wormald, Generating random regular graphs quickly, Probability and Computing 8 (1999), 377-396, 1999. http://citeseer.ist.psu.edu/steger99generating.html

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