kernighan_lin_bisection#
- kernighan_lin_bisection(G, partition=None, max_iter=10, weight='weight', seed=None)[source]#
Partition a graph into two blocks using the Kernighan–Lin algorithm.
This algorithm partitions a network into two sets by iteratively swapping pairs of nodes to reduce the edge cut between the two sets. The pairs are chosen according to a modified form of Kernighan-Lin, which moves node individually, alternating between sides to keep the bisection balanced.
- Parameters:
- Ggraph
- partitiontuple
Pair of iterables containing an initial partition. If not specified, a random balanced partition is used.
- max_iterint
Maximum number of times to attempt swaps to find an improvemement before giving up.
- weightkey
Edge data key to use as weight. If None, the weights are all set to one.
- seedinteger, random_state, or None (default)
Indicator of random number generation state. See Randomness. Only used if partition is None
- Returns:
- partitiontuple
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
[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.