图分区：Kernighan-Lin算法及其多种优化和实现（FM,

作者: Caucher | 来源:发表于2021-07-05 20:02 被阅读0次

标题：一个高效的图分区启发式算法

I. INTRODUCTION

1.1 Definition of the Problem

直接上问题定义。
对于图G，n个节点，节点有权重， $C=(c_{i,j})$ 是边集，有权重。我们的任务是将图G的所有节点分成k个部分，每个部分的节点总权重不大于p，同时要使得不同部分之间边的权重要最小。

这个问题由很多应用，比如集成电路要放到几块板子上，板子容量有限，不同板子之间通信代价大，如何分割集成电路。等等。

1.2 Exact Solutions

考虑节点权重都是1，n=kp的简易情况，选择的总数仍为：

image.png
这显然行不通，复杂度最多能接受的就是

n^2

，n是节点个数。

1.3 False Starts

有一些启发是不合理的，作者放在这里排雷。

1.3.1 Random Solutions

随机选择，定时停止的方案，质量非常之差，结果出现近似最优的概率极其小。

1.3.2 Max Flow-Min Cut

用最大流最小割来考虑这个问题。把边权重当做网络的边容量，最终找到一个最小割。
听起来挺合适的，但仍然有问题，这个最小割的两部分，容量没法限制，没法扩展这个算法来保证容量限制。有的时候，最小割很极端的时候，分割质量也会极差。

1.3.3 Clustering

聚类也是比较直观的方法。但是和最大流最小割一样，仍然没有容量限制保证；此外，聚类异常点如何处理，也是一个问题。

1.3.4 $\lambda$ -Opting

[暂时没看懂]

II. TWO-WAY UNIFORM PARTITIONS

2.1 Introduction

首先考虑二等分2n个顶点的无向图。
整体思路很简单：首先随意二等分成A和B，然后根据一个算法交换A中的子集和B中的子集，使得代价更小，直到找不到这样的代价。

image.png
可以看到，算法的核心，就是你怎么找到这些可以交换的子集。作者提供的算法也是基于代价近似的。下面给出几个定义：

image.png

image.png
很容易推导得到，如果

a \in A

b \in B

两个点互换，其净收益为

image.png

2.2 Phase 1 Optimization Algorithm

具体算法上，首先计算每个点的D值，这非常好算，每个是O(n)的。
然后，定位两个分区中，能使得净收益最大的两个点，计算收益。算好之后，就把他们暂时从图中抹去，将剩下的点的D值更新为：

image.png

然后重复该过程。重复n次，直到所有点对都被定位计算过，然后，我们找前k次最大的净收益，定位这个k，使得前k次交换的点就是两个子集，进行事实上的交换。

image.png

2.3 Effectiveness of the Procedure

作者给出的实验结论：对于结果是最优结果的概率 $p=2^{-n/30}$ .

2.4 Running Time of the Procedure

计算D值是 $O(E)$ ，D值更新V轮是 $O(V*(V+E))$ ，每一轮选择最优净收益点，可以通过排序来完成，V轮一共是 $O(V^2logV)$ ，从排好序的A、B里面选择净收益最大的最大是 $O(V^2)$ ，而且很容易剪枝。
当然也可以不排序，选择D值最大的几个点算一下就行了，虽然结果只是近似的，但近似质量很不错，复杂度为 $O(1)$ 。

最终，总的复杂度为 $O(V^2logV + VE)$ 或 $O(VE)$ 。

2.5 Improving the Phase 1 Optimal Partition

算法在初始选择的二分区质量比较好时，迭代次数就会很少，交换的子集会很小，性能会很好。因此初始位置是比较关键的。
由于算法实际上找到的是一个local minumum，为了能更加逼近真实解，可以随机多选几次初始二分区，重复这个算法，取最好的。
还有一种更好的方法，就是将第一次运行时的结果，随机互相交换一些节点，然后作为初始分区再次运行，实验效果很好。

2.6 Partitioning into Unequal-Sized Sets

将问题扩展到不止是二等分，而是任意二分，满足指定的容量条件即可，比如要求每个分区的节点个数为[ $n_1,n_2$ ]. $n_1+n_2=n$ ，这里改称n为图的节点总数。
方法也很简单，就是搞一些孤立点，度数为0，这些孤立点个数为 $2n_2 - n$ ，然后将图用上述方法二分，二分之后再去掉这些孤立点就行了，它们不影响D值和净收益。

2.7 Elementa of Unequal Size

对于图中节点的权重不为1的情况，作者的方案就是把权重为k的节点拆成k个权重为1的节点，节点之间全连通，边权重要设置的比较高。

III. MULTIPLE-WAY PARTITIONS

3.1 Reduction to 2-Way Partitioning Problem

本节讲的就不是2分了，是k分图。节点个数也设为kn。
方法也是比较简单，首先随机k分，然后成对进行二分式的算法，每一轮要进行C(2,k)次二分算法，然后要进行多轮，最终得出结果。
作者阐述，轮数不会很多，一般只用几轮就可以，可以在2轮之内快速收敛到95%近似的质量。但是作者也说了，二分算法执行次数越多，效果越好。

3.2 Starting Partition

选择初始分区，初始分区选的好，收敛速度快。
第一个方法就是，对于一个k分区，首先进行r分区，在每个结果分区上再进行s分区，持续进行，直到t。 k=rs...*t。
问题在于，第一次分区会让每个分区内尽量紧密（边权重大），但第二次分区时视图让该分区内产生多个小分区，这产生了目的上的矛盾，层层传递，导致效果不太好。

3.3 Expansion Factor

对于不限制分区k的情况，作者提供算法：对于kn个节点的图，首先分k个分区，得到算法结果。之后补充n个孤立节点，变成1个(k+1)分区的问题，执行算法，依次类推，直到出现一个分区包含的全部是孤立点，那么算法终止，扣除这个分区，剩下的就是最优分区解。

4. Fiduccia-Mattheyses implementation

FM实现的最大好处就是线性时间复杂度，同时允许二分的两个部分有一定的不平衡。

4.1 算法描述

其提升效率的主要思想是利用下图这样一个结构。

图的两个二分子图，每一个都维护一个有序数组，数组的元素都是值类型的，代表可能出现的D值域；
每个值类型后面还跟着一个双向链表，用来表示，目前收益为该值的节点有哪些；
每个节点会维护在两个buckets(有序数组)中对应元素的指针，因此可以直接通过节点id，找到节点在buckets中的位置；
因此节点如果要更新D值，在buckets中改变位置只需要O(1)的复杂度；
每一次只选择一个节点换边，在满足平衡因素的条件下，按照D值排列考虑。
其余部分和KL算法一致。

image.png

4.2 代价分析

计算D值是O(E)，每一次迭代选择一个顶点用来移动，选择这个过程只需要O(1)，V轮选择，总代价O(V)；更新选择的节点的邻居在有序表中的位置，每一个邻居代价O(1)，需要沿着所有边更新所有邻居，总代价O(E)。

最终总代价O(V+E)，线性时间。

5. Global Kernighan-Lin Refinement（GKLR算法）

这个算法的优点是K分，而且比较高效，很通用。
缺陷是对于初始分区就是不满足平衡条件的，算法很难正确运行。

5.1 算法描述

算法初始时将图中的顶点随机K分，然后遵循KL的思想，交换节点；
算法维护一个全局优先级队列（FM算法中的bucket），队列中存一些节点，队列的排序方式就是这些节点的最大交换收益，只有最大交换收益非负的节点才能在队列中；
- 交换收益(gain)：和2分图有所区别，对于节点v，要找到节点v直接相连的其他几个分区，计算如果v到了其中一个分区，整个图的edge-cut会减小多少，这就是v的交换收益。换一种说法，假设v目前在分区A，v和分区B有边相连，v交换到分区B的收益就是v和B之间的边的总权重，减去v在A中边的总权重；对于v相邻的分区，每个分区都算一下交换收益，按照最大的值进行PQ的排序。
算法从队列中依次去取节点，找到在满足分区平衡条件下的最大收益的分区，更新这个节点的邻居的收益，锁住该节点；
- 注意到，由于要满足平衡条件，所以最终选取的分区可能收益很小，甚至是负数。因此，如果有连续x个节点的总收益是负数，那么这x个节点全部undo，循环终止。
算法的终止条件是所有队列中的节点都被锁住（遍历过），或者是连续x个节点总负收益。终止之后，选择最前面的连续移动操作，使得总收益最大。
如此循环，可以迭代多次，直到一个给定的次数，或者算法收敛了（无累计净收益了）。

6. The Walshaw-Cross refinement algorithm

WC算法也是K分的，但是没有GKLR算法的缺陷，初始分区可以很不均衡。算法的目的是先找到初始各个分区的不平衡性，然后计算各个分区之间应该如何倾斜流量，即它们的距离。然后利用一个变形的GKLR，对图进行重分区。

6.1 分区距离计算

计算分区距离是要解一个线性代数方程。最终得到一个k维向量x， $x_i - x_j$ 就是i分区应该倾斜多少重量到j分区。
为了得到这个向量，我们首先计算一个偏斜度向量，意义很明显：

image.png
然后定义一个拉普拉斯矩阵

image.png
最后去解Mx=b的方程，得到分布结果。

6.2 变形的GKLR

得到分布结果之后，我们通过变形的GKLR重新得到分区：

算法初始阶段，能够进入优先级队列的只有分区中的边界顶点。由于迭代过程中会有顶点被移动，因此顶点的边界性要实时更新，实时维护，符合条件的进入，不合格的删除。
bucket首先根据收益，然后是权重进行排序。如果收益是正的，权重就增序；否则按权重降序。
移动过程中，不会去考虑收益。只要移动之后，对应的分区满足平衡条件，或者这次移动减少了分布流量，这次移动就可以被接受。
在每次迭代之后，新生成的分区结果Q，相比于之前最好的分区P，只要满足以下三个条件中的一个，就成为新的BSF:
- P不满足平衡条件，Q比P更平衡；
- Q的切割总权重更小；
- P，Q的切割总权重一致，但是P更平衡。
如果优先级队列中的某个节点，和两个分区A,B相邻，如果第一次和收益较大的A分区试图移动失败了，之后还可以在轮到gain(B)的位置时，重新试试和A分区，和B分区能否成功移动。因此一个节点可能会被尝试多次。

图分区：Kernighan-Lin算法及其多种优化和实现（FM,

I. INTRODUCTION

1.1 Definition of the Problem

1.2 Exact Solutions