maybe_regular_expander

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

创建随机规则扩展图的实用工具。

返回一个具有非常高概率是扩展图的随机 \(d\)-正则图，包含 \(n\) 个节点。

Parameters:

nint

节点数量。

dint

每个节点的度数。

create_using图实例或构造函数

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

max_triesint. (默认: 100)

生成每个独立循环时允许的循环次数。

seed(默认: None)

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

Returns:

G图

构造的无向图。

Raises:

NetworkXError

如果 \(d % 2 != 0\)，因为度数必须是偶数。 如果 \(n - 1\) 小于 \(2d\)，因为图最多是完全图。 如果达到 max_tries。

See also

is_regular_expander

random_regular_expander_graph

Notes

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

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

Joel Friedman 证明了在此模型中，生成的图是扩展图的概率为 \(1 - O(n^{-\tau})\)，其中 \(\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)