random_regular_expander_graph

random_regular_expander_graph(n, d, *, epsilon=0, create_using=None, max_tries=100, seed=None)

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

[1]

Expander graph, https://en.wikipedia.org/wiki/Expander_graph

[2]

Alon-Boppana bound, https://en.wikipedia.org/wiki/Alon%E2%80%93Boppana_bound

[3]

Ramanujan graphs, https://en.wikipedia.org/wiki/Ramanujan_graph

Examples

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