Metis.jlでグラフを分割する

今回はJuliaのパッケージMetis.jlでグラフを分割してみます。

github.com

以下の隣接行列からなるグラフを２つに分割してみます。

A=[0 1 0 0 1 1 0;
0 0 0 1 0 0 1;
0 1 0 1 0 0 1;
0 1 1 0 1 0 1;
0 0 0 1 0 1 0;
1 0 0 0 1 0 0;
0 1 1 1 0 0 0]

Metis.partition(G,分割数)でグラフGを所定の分割数で分割できます。 コードは以下になります。

using LightGraphs
using GraphPlot
using Metis

A=[0 1 0 0 1 1 0;
0 0 0 1 0 0 1;
0 1 0 1 0 0 1;
0 1 1 0 1 0 1;
0 0 0 1 0 1 0;
1 0 0 0 1 0 0;
0 1 1 1 0 0 0]

G = DiGraph(A)

group=Metis.partition(G,2) 

gplot(G,nodelabel = group,nodelabelc= "black")

これにより以下の２つのグラフに分割されます。

基本的に分割はクラスター外へのリンクの数を小さくすることと、クラスター自体を小さくすることの間にトレードオフが発生します。今回はもとのグラフの形状も分割しやすものだったせいかうまく分割できました。

今回はここまでにします。