减少METIS中图划分的通信量

Question

我一直在使用METIS对图进行分区。到目前为止，我没有使用任何特殊的选项，所以我假设METIS正在对图进行分区，同时最小化边切割。

问题是，我正在处理的图中有很少的顶点有很多邻居。我猜这意味着我将不得不通过减少通信量的选项，而不是边缘切割。

我该怎么做呢？我不明白第5.8节第26页中的vsize参数的意义。我需要处理ncon或vwgt，还是objval？我是否只是执行optionsMETIS_OPTION_OBJTYPE = METIS_OBJTYPE_VOL并将其传递给函数？

另外，对于一个顶点数可能不是2的幂的图，我应该使用函数的哪个变体？K-way(最有可能)还是一分为二？

我会在METIS论坛上问这些问题，但不幸的是，自从我注册以来已经有一段时间了，他们的网站没有任何回复，所以我在这里问。

Answer 1

‘'vsize’用于指定与顶点关联的通信量。对于大多数应用程序，您不需要指定它，因为假定它是一个。如果没有平衡约束，可以忽略ncon和vwgt。objval变量只是让您知道生成的分区的目标值是什么(切割边的总权重或总通信量)。

您将希望对更多的分区使用k-way分区，因为它往往会更快，并可能产生更高质量的结果。两者都将处理两个分区数的非幂。顶点的数量并不重要。