Metis.jlでグラフを分割する
今回はJuliaのパッケージMetis.jlでグラフを分割してみます。
以下の隣接行列からなるグラフを2つに分割してみます。
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")
これにより以下の2つのグラフに分割されます。
基本的に分割はクラスター外へのリンクの数を小さくすることと、クラスター自体を小さくすることの間にトレードオフが発生します。今回はもとのグラフの形状も分割しやすものだったせいかうまく分割できました。
今回はここまでにします。