connected_double_edge_swap#

connected_double_edge_swap(G, nswap=1, _window_threshold=3, seed=None)[source]#

尝试在图 G 中进行指定数量的双边交换。

双边交换移除两个随机选择的边 (u, v) 和 (x, y) ，并创建新的边 (u, x) 和 (v, y)

u--v            u  v
       becomes  |  |
x--y            x  y

如果 (u, x) 或 (v, y) 已经存在，则不执行交换，因此实际交换的边数总是 最多 nswap 。

Parameters:
G图

一个无向图

nswap整数（可选，默认=1）

要执行的双边交换次数

_window_threshold整数

窗口大小，低于此大小将在每次交换后检查图的连通性。

此函数中的“窗口”是一个动态更新的整数，表示在检查图是否保持连通之前要进行的交换尝试次数。这是一种优化，用于减少算法的运行时间，以增加实现的复杂性为代价。

如果窗口大小低于此阈值，则算法在每次交换后检查图是否保持连通，方法是检查刚移除边的两个节点之间是否存在路径。如果窗口大小高于此阈值，则算法执行窗口中的所有交换，然后才检查图是否仍然连通。

seed整数，random_state，或 None（默认）

随机数生成状态的指示器。 参见 Randomness 。

Returns:
int

成功交换的次数

Raises:
NetworkXError

如果输入图不连通，或者图的节点数少于四个。

Notes

初始图 G 必须是连通的，并且生成的图也是连通的。图 G 在原地修改。

References

[1]

C. Gkantsidis 和 M. Mihail 和 E. Zegura, 使用马尔可夫链模拟方法生成连通的幂律随机图，2003年。 http://citeseer.ist.psu.edu/gkantsidis03markov.html

On this page