maybe_regular_expander

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

用于创建随机正则展开图的工具函数。

返回一个具有很高概率是展开图的、在 \(n\) 个节点上的随机 \(d\)-正则图。

参数：

nint

节点数量。

dint

每个节点的度。

create_using图实例或构造函数

指示返回的图的类型。如果是一个 Graph 类型的实例，则清除并使用它。如果是一个构造函数，则调用它来创建一个空图。默认为 Graph 构造函数。

max_triesint. (默认: 100)

生成每个独立环时允许的最大尝试次数

seed(默认: None)

用于设置随机数生成状态的种子。参见 :ref`随机性<randomness>`。

返回：

G图

构建的无向图。

抛出：

NetworkXError

如果 \(d % 2 != 0\)，因为度必须是偶数。如果 \(n - 1\) 小于 :math:` 2d `，因为图至多是一个完全图。如果达到 max_tries 最大尝试次数

另请参阅

is_regular_expander

random_regular_expander_graph

注意

节点编号从 \(0\) 到 \(n - 1\)。

图是通过取 \(d / 2\) 个随机独立环生成的。

Joel Friedman 证明了在此模型中，生成的图是展开图的概率为 \(1 - O(n^{-\tau})\)，其中 \(\tau = \lceil (\sqrt{d - 1}) / 2 \rceil - 1\)。 [1]

参考文献

[1]

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

示例

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