Kernighan-Lin Graph Partitioning Problem

Kernighan-Lin, Graph Distance Metrics 858L Kernighan-Lin Graph Partitioning Kernighan-Lin Graph Partitioning Problem. Divide a weighted graph with 2n nodes into two parts, each of size n, to minimize the sum of the weights crossing the two parts. You could just use minimum cut if you didn’t have the restriction to each part being of size n. Idea (Kernighan-Lin, 1970): start with some partition that satisfies the size requirement and repeatedly swap nodes between the partitions. Kernighan-Lin More Detail Repeat until no more vertices are left: Divide the network into 2 parts A, B of equal size arbitrarily. Select a i ∈ A, b i ∈ B, such that the reduction in cost is as large as possible and neither a

i , b i has been chosen before Let C i be the cost of the partition after swapping a i ,b i Swap a i and b i Return (A’,B’) corresponding to the smallest C i observed. While cost continues to be reduced Call using the returned partition as the new starting point Improving this Solution A B Find the optimal partitions in A and B separately A’ B’ B’’A’’ Run KL procedure on all 3 of these starting partitions Three KL Extensions (1) Divide into partitions of unequal (but known) sizes: Start with a partition that satisfies the sizes you want. Stop when all the nodes on the smaller side have been swapped. (2) Divide into 2 partitions such that one has ≥ n 1 nodes and the other has ≤ n 2 (where n 1 + n 2 = n). Left as an exercise or exam problem, or whatnot. (3) What if you have node weights w u and want ∑w u for u ∈ A to equal some n 1 ? If w u are integers, replace u with a clique of w u nodes, connected by very high weight edges. KL Into ≥ 3 partitions Start with a partition that satisfies your k size requirements n 1 , n 2 , ..., n k Apply the 2-part procedure between every pair of parts (n choose 2 times) Repeat the above step until no improvement is obtained. Getting a starting partition Method 1. Suppose you want k partitions. Let k = k 1 k 2 k 3 ·…·k m Divide the graph into k 1 parts (starting, say from an arbitrary split) Divide each of those k 1 parts into k 2 parts ⠇ and so on. If the k i are small (say k is a power of 2) then as long as we’re OK at getting a 2-split, we get a good k-split. Method 2. Suppose you want k partitions in a graph of kn nodes. Use the 2-part algorithm to find a (n, k(n-1)) split. Let the n-sized set be one part, repeat. Clustering Using Graph Distances Distance Notions on Graphs • Apply standard clustering algorithms, need to define d(u,v) as ''distance’’ between nodes u and v. Czek ano wski-Dice( u, v ) := | N ( u ) ∆ N ( v ) | | N ( u ) ∪ N (...

Website: www.cs.cmu.edu | Filesize: -
No of Page(s): 20
Download Kernighan-Lin Graph Partitioning Problem.pdf