maybe_regular_expander

maybe_regular_expander(n, d, *, create_using=None, max_tries=100, seed=None)

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 % 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

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)