1. 算法来源
来源论文
论文题目： Partial Parallelization of Graph Partitioning Algorithm METIS
2. METIS算法
主要用于将大规模稀疏图高效划分为多个均衡子图，用于并行计算任务分配，VLS布局优化，有限元网络剖分等领域。
核心思想是基于多层次递归二分和多层次的K路划分。
算法的三个步骤：
- 粗化（Coarsening）：在迭代合并顶点和边，缩小图规模
- 初始划分（Initial Partitioning）：在最粗层执行k路或者递归二分划分
- 精细化（UnCoarsening/Refinement）：逐层还原原图，微调划分
第一步骤，粗化
将原始图G0，转为G1，G2，G3，到Gk，满足 V0 V1 V2 Vk。Gk是G0的k级代表。一个好的划分Gk表示一个公平的G0的划分。
第二阶段，初始化划分
当Gk划分到足够小的时候，以Gk为一个初始化的划分。将Gk划分为若干个子图。
第三阶段，精细化
将Gk的划分方式，分为Pn-1，Pn-2，P0。在多次映射之后，使用贪心算法细化分区。0≤i≤k−1的每个分区Pi在投影到Pi+1之前被细化。
3. 示意图
METIS算法的示意图为
并行化：
METIS算法适合并行化计算，在粗化中涉及大量计算的情况下可以使用。所以算法可以适用于大规模图数据上。
4. 参考文献
METIS - Serial Graph Partitioning and Fill-reducing Matrix Ordering
METIS - Family of Multilevel Partitioning Algorithms
[PDF]Partial Parallelization of Graph Partitioning Algorithm METIS