Skip to main content
`Ctrl`+`K`

# 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:
    n int

      The number of nodes.

    d int

      The degree of each node.

    create_using Graph 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_tries int. (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:
    G graph

      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)