kernighan_lin_bisection

kernighan_lin_bisection(G, partition=None, max_iter=10, weight='weight', seed=None)

使用Kernighan-Lin算法将图划分为两个块。

该算法通过迭代交换节点对来减少两个集合之间的边割，从而将网络划分为两个集合。选择的节点对是根据Kernighan-Lin的修改形式[1]，该形式单独移动节点，交替在两侧以保持二分平衡。

Parameters:

GNetworkX图

图必须是无向的。

partition元组

包含初始分区的可迭代对象对。如果未指定，则使用随机平衡分区。

max_iterint

放弃前尝试交换以找到改进的最大次数。

weight键

用作权重的边数据键。如果为None，则所有权重都设置为1。

seed整数, random_state, 或 None (默认)

随机数生成状态的指示器。 参见 随机性 。 仅在partition为None时使用

Returns:

partition元组

表示二分的一对节点集合。

Raises:

NetworkXError

如果partition不是图节点的有效分区。

References

[1]

Kernighan, B. W.; Lin, Shen (1970). “一种用于图分割的有效启发式程序。” 贝尔系统技术期刊 49: 291–307. Oxford University Press 2011.