is_regular_expander#

is_regular_expander(G, *, epsilon=0)[source]#

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}+ϵ$. [2]

In the case where $ϵ=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}+ϵ$.

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