random_regular_expander_graph#

random_regular_expander_graph(n, d, *, epsilon=0, create_using=None, max_tries=100, seed=None)[source]#

Returns a random regular expander graph on \(n\) nodes with degree \(d\).

An expander graph is a sparse graph with strong connectivity properties. [1]

More precisely the returned graph is a \((n, d, \lambda)\)-expander with \(\lambda = 2 \sqrt{d - 1} + \epsilon\), close to the Alon-Boppana bound. [2]

In the case where \(\epsilon = 0\) it returns a Ramanujan graph. A Ramanujan graph has spectral gap almost as large as possible, which makes them excellent expanders. [3]

Parameters:
nint

The number of nodes.

dint

The degree of each node.

epsilonint, float, default=0
max_triesint, (default: 100)

The number of allowed loops, also used in the maybe_regular_expander utility

seed(default: None)

Seed used to set random number generation state. See :ref`Randomness<randomness>`.

Raises:
NetworkXError

If max_tries is reached

See also

maybe_regular_expander
is_regular_expander

Notes

This loops over maybe_regular_expander and can be slow when \(n\) is too big or \(\epsilon\) too small.

References

Examples

>>> G = nx.random_regular_expander_graph(20, 4)
>>> nx.is_regular_expander(G)
True
On this page