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 :ref`Randomness<randomness>`.

Returns:

Ggraph

The constructed undirected graph.

Raises:

NetworkXError

If $d$ 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

See also

is_regular_expander

random_regular_expander_graph

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)