kernighan_lin_bisection

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

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 [1], which moves nodes individually, alternating between sides to keep the bisection balanced.

Kernighan-Lin is an approximate algorithm for maximal modularity bisection. In [2] they suggest that fine-tuned improvements can be made using greedy node swapping, (see greedy_node_swap_bipartition). The improvements are typically only a few percent of the modularity value. But they claim that can make a difference between a good and excellent method. This function does not perform any improvements. But you can do that yourself.

Parameters:

GNetworkX graph

Graph must be undirected.

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 improvement before giving up.

weightstring or function (default: “weight”)

If this is a string, then edge weights will be accessed via the edge attribute with this key (that is, the weight of the edge joining u to v will be G.edges[u, v][weight]). If no such edge attribute exists, the weight of the edge is assumed to be one.

If this is a function, the weight of an edge is the value returned by the function. The function must accept exactly three positional arguments: the two endpoints of an edge and the dictionary of edge attributes for that edge. The function must return a number or None to indicate a hidden edge.

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.

[2]

M. E. J. Newman, “Modularity and community structure in networks”, PNAS, 103 (23), p. 8577-8582, https://doi.org/10.1073/pnas.0601602103