METIS-一种图切分的软件包（简介）

METIS是由Karypis Lab开发的一个具有强大功能的图切分软件包。准确来说，METIS是一个串行图切分的软件包，Karypis Lab还提供了并行版的图切分软件包parMETIS和支持超图和电路划分的hMETIS。METIS的算法设计主要基于多层次递归二分切分法、多层次K路切分法以及多约束划分机制。用户使用METIS软件包时，可以根据需要选择相应的切分方式。

METIS主要的特性如下。首先，METIS具有高质量的划分结果，据称比通常的谱聚类（spectral clustering）要精确10%-50%。其中Chaco支持谱聚类算法。其次，METIS执行效率非常高，比常见的划分算方法快1-2个数量级。百万级顶点的图几秒钟之内就可以切分为256个类。最后，METIS具有很低的注入元（fill-in ），从而降低了存储负载和计算量。

METIS的工作原理：以k路多层次划分为例。

左图是无权重图，第一行是顶点个数和边的条数。除第一行之外，第 i 行表示 i-1 节点连接的顶点编 。比如第2行表示的是顶点1与5,3,2顶点之间有边直接相连。右图是有权图，第一行表示顶点个数和边的条数，以及format格式为带权重图。第 i 行表示 i-1 节点连接的顶点编 ，紧跟边的权重值。

图划分输出文件格式非常简单，一共有n行（n个顶点的图），每行一个整数表示该节点所属cluster的编 。