networkx.kernighan_lin_bisection¶

networkx.kernighan_lin_bisection(G, partition=None, max_iter=10, weight='weight')[source]¶

Partition a graph into two blocks using the Kernighan–Lin algorithm.

This algorithm paritions a network into two sets by iteratively swapping pairs of nodes to reduce the edge cut between the two sets.

Parameters:	G : graph partition : tuple Pair of iterables containing an intial partition. If not specified, a random balanced partition is used. max_iter : int Maximum number of times to attempt swaps to find an improvemement before giving up. weight : key Edge data key to use as weight. If None, the weights are all set to one.
Returns:	partition : tuple A pair of sets of nodes representing the bipartition.
Raises:	NetworkXError If partition is not a valid partition of the nodes of the graph.

References

[R1165]

Kernighan, B. W.; Lin, Shen (1970). “An efficient heuristic procedure for partitioning graphs.” Bell Systems Technical Journal 49: 291–307. Oxford University Press 2011.