# maybe_regular_expander#

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

Utility for creating a random regular expander.

Returns a random $$d$$-regular graph on $$n$$ nodes which is an expander graph with very good probability.

Parameters:
nint

The number of nodes.

dint

The degree of each node.

create_usingGraph Instance or Constructor

Indicator of type of graph to return. If a Graph-type instance, then clear and use it. If a constructor, call it to create an empty graph. Use the Graph constructor by default.

max_triesint. (default: 100)

The number of allowed loops when generating each independent cycle

seed(default: None)

Seed used to set random number generation state. See :refRandomness<randomness>.

Returns:
Ggraph

The constructed undirected graph.

Raises:
NetworkXError

If $$d % 2 != 0$$ as the degree must be even. If $$n - 1$$ is less than :math: 2d  as the graph is complete at most. If max_tries is reached

Notes

The nodes are numbered from $$0$$ to $$n - 1$$.

The graph is generated by taking $$d / 2$$ random independent cycles.

Joel Friedman proved that in this model the resulting graph is an expander with probability $$1 - O(n^{-\tau})$$ where $$\tau = \lceil (\sqrt{d - 1}) / 2 \rceil - 1$$. [1]

References

[1]

Joel Friedman, A Proof of Alon’s Second Eigenvalue Conjecture and Related Problems, 2004 https://arxiv.org/abs/cs/0405020

Examples

>>> G = nx.maybe_regular_expander(n=200, d=6, seed=8020)