networkx.generators.random_graphs.random_regular_graph

random_regular_graph(d, n, create_using=None, seed=None)

Return a random regular graph of n nodes each with degree d.

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

Parameters:

d : int

Degree

n : integer

Number of nodes. The value of n*d must be even.

create_using : graph, optional (default Graph)

The graph instance used to build the graph.

seed : hashable object

The seed for random number generator.

Notes

The nodes are numbered form 0 to n-1.

Kim and Vu’s paper [R78] shows that this algorithm samples in an asymptotically uniform way from the space of random graphs when d = O(n**(1/3-epsilon)).

References

[R77]

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

[R78]

(1, 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://doi.acm.org/10.1145/780542.780576