graph - METISのグラフパーティションの通信量を削減

Question

METIS を使用してグラフを分割しています。今のところ、私は特別なオプションを使用していないので、METIS はエッジ カットを最小限に抑えながらグラフを分割していると思います。

問題は、私が取り組んでいるグラフには、多くの隣接点を持つ頂点がほとんどないということです。つまり、エッジカットではなく、通信量を減らすオプションを渡す必要があるということです。

どうすればいいですか？セクション 5.8 の 26 ページの vsize パラメータの意味がわかりません。ncon、vwgt、または objval をいじる必要がありますか? options[METIS_OPTION_OBJTYPE] = METIS_OBJTYPE_VOL を実行して関数に渡すだけですか?

また、頂点の数が 2 のべき乗でない可能性があるグラフの場合、関数のどのバリアントを使用すればよいですか? k-way（おそらく）または二等分？

METIS フォーラムでこれらの質問をしたはずですが、残念ながら、METIS フォーラムに登録してからしばらく経ち、ウェブサイトからの返信がないので、ここで質問します。

Answer 1

「vsize」は、頂点に関連付けられた通信量を指定するためのものです。ほとんどのアプリケーションでは、1 つであると想定されるため、これを指定する必要はありません。バランスの制約がない場合は、ncon と vwgt を無視できます。objval 変数は、生成されたパーティションの目的の値 (カット エッジの合計の重みまたは合計の通信量) を単に通知します。

k-way パーティションはより高速になる傾向があり、より高品質の結果が得られる可能性があるため、多数のパーティションに対して使用することをお勧めします。どちらも 2 の累乗以外のパーティション数を処理します。頂点の数は関係ありません。