is_regular_expander

is_regular_expander(G, *, epsilon=0)

Determines whether the graph G is a regular expander. [1]

An expander graph is a sparse graph with strong connectivity properties.

More precisely, this helper checks whether the graph is a regular \((n, d, \lambda)\)-expander with \(\lambda\) close to the Alon-Boppana bound and given by \(\lambda = 2 \sqrt{d - 1} + \epsilon\). [2]

In the case where \(\epsilon = 0\) then if the graph successfully passes the test it is a Ramanujan graph. [3]

A Ramanujan graph has spectral gap almost as large as possible, which makes them excellent expanders.

Parameters:

GNetworkX graph

epsilonint, float, default=0

Returns:

bool

Whether the given graph is a regular \((n, d, \lambda)\)-expander where \(\lambda = 2 \sqrt{d - 1} + \epsilon\).

See also

maybe_regular_expander

random_regular_expander_graph

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