connected_double_edge_swap#

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

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

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

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

如果 (u, x) 或 (v, y) 中的任何一条边已经存在，则不执行交换，因此实际交换的边数始终至多为 nswap。

参数:
G图

无向图

nswap整数 (可选，默认为 1)

要执行的双边交换次数

_window_threshold整数

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

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

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

seed整数，random_state 或 None (默认)

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

返回:
int

成功交换的次数

引发:
NetworkXError

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

注意事项

初始图 G 必须是连通的，并且结果图也是连通的。图 G 会被原地修改。

参考文献

[1]

C. Gkantsidis and M. Mihail and E. Zegura, The Markov chain simulation method for generating connected power law random graphs, 2003. http://citeseer.ist.psu.edu/gkantsidis03markov.html

在本页