random_regular_expander_graph

random_regular_expander_graph(n, d, *, epsilon=0, create_using=None, max_tries=100, seed=None)

返回一个具有 \(d\) 度且包含 \(n\) 个节点的随机正则扩边图。

扩边图是一种具有强连接性质的稀疏图。 [1]

更准确地说，返回的图是一个 \((n, d, \lambda)\)-扩边图，其中 \(\lambda = 2 \sqrt{d - 1} + \epsilon\)，接近 Alon-Boppana 界。 [2]

当 \(\epsilon = 0\) 时，它返回一个拉马努金图。拉马努金图具有几乎尽可能大的谱隙，这使得它们成为优秀的扩边图。 [3]

参数:

nint

节点数量。

dint

每个节点的度。

epsilonint, float, default=0

max_triesint, (默认值: 100)

允许的循环次数，也用于 maybe_regular_expander 工具

seed(默认值: None)

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

引发异常:

NetworkXError

如果达到 max_tries

另请参阅

maybe_regular_expander

is_regular_expander

说明

这会循环调用 maybe_regular_expander，当 \(n\) 过大或 \(\epsilon\) 过小时可能会很慢。

参考文献

[1]

扩边图，https://en.wikipedia.org/wiki/Expander_graph

[2]

Alon-Boppana 界，https://en.wikipedia.org/wiki/Alon%E2%80%93Boppana_bound

[3]

拉马努金图，https://en.wikipedia.org/wiki/Ramanujan_graph

示例

>>> G = nx.random_regular_expander_graph(20, 4)
>>> nx.is_regular_expander(G)
True