Note

This documents the development version of NetworkX. Documentation for the current release can be found here.

networkx.algorithms.community.kernighan_lin.kernighan_lin_bisection

kernighan_lin_bisection(G, partition=None, max_iter=10, weight='weight', seed=None)[源代码]

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

该算法通过迭代交换节点对将网络划分为两个集合,以减少两个集合之间的边割。这些对是根据Kernighan-Lin的一种改进形式来选择的,它可以单独移动节点,在两边交替以保持平分平衡。

参数
  • G图表

  • 分区元组 )--一对包含初始分区的iterables。如果未指定,则使用随机平衡分区。

  • max_iterint )--尝试交换以在放弃前找到改进的最大次数。

  • 重量key )--要用作权重的边缘数据键。如果没有,则所有权重都设置为1。

  • seedinteger, random_state, or None (default) )--随机数生成状态的指示器。见 Randomness . 仅在分区为“无”时使用

返回

分区 --表示二部的一对节点。

返回类型

tuple

引发

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

引用

1

Kernighan,B.W.;Lin,Shen(1970年)。”对图进行分区的有效启发式过程。” 贝尔系统技术杂志 49:291—307。牛津大学出版社2011年。