kernighan_lin_bisection#
- kernighan_lin_bisection(G, partition=None, max_iter=10, weight='weight', seed=None)[源]#
使用 Kernighan-Lin 算法将图划分为两个块。
该算法通过迭代交换节点对来减少两个集合之间的边割，从而将网络划分为两个集合。选择节点对的依据是 Kernighan-Lin 算法的修改形式 [1]，它独立地移动节点，在两边交替以保持二分平衡。
- 参数：
- GNetworkX 图
图必须是无向的。
- partition元组
包含初始划分的一对可迭代对象。如果未指定，则使用随机平衡划分。
- max_iterint
在放弃之前尝试交换以寻找改进的最大次数。
- weight键
用作权重的边数据键。如果为 None，则所有权重都设置为一。
- seed整数, random_state, 或 None (默认)
随机数生成状态的指示器。参见 随机性。仅当 partition 为 None 时使用。
- 返回：
- partition元组
表示二分划分的一对节点集合。
- 抛出：
- NetworkXError
如果 partition 不是图中节点的有效划分。
参考文献
[1]Kernighan, B. W.; Lin, Shen (1970). “An efficient heuristic procedure for partitioning graphs.” Bell Systems Technical Journal 49: 291–307. Oxford University Press 2011.