Main Content

ラプラシアン行列によるグラフの分割

ライブ スクリプトを開く

この例では、グラフのラプラシアン行列を使用してフィードラー ベクトルを計算する方法を説明します。フィードラー ベクトルはグラフを 2 つの部分グラフに分割する際に使用できます。

データの読み込み

データ セット barbellgraph.mat を読み込みます。これには、バーベル グラフのスパース隣接行列とノード座標も含まれています。

load barbellgraph.mat

グラフのプロット

カスタム ノード座標 xy を使用してグラフをプロットします。

G = graph(A,'omitselfloops');
p = plot(G,'XData',xy(:,1),'YData',xy(:,2),'Marker','.');
axis equal

ラプラシアン行列とフィードラー ベクトルの計算

グラフのラプラシアン行列を計算します。その後、eigs を使用して 2 つの最小の固有値とそれに対応する固有ベクトルを計算します。

L = laplacian(G);
[V,D] = eigs(L,2,'smallestabs');

フィードラー ベクトルはこのグラフの 2 番目の最小固有値に対応する固有ベクトルです。"最小" 固有値はゼロとなり、このグラフに連結要素が 1 つあることがわかります。この場合、V の 2 番目の列が、2 番目の最小固有値 D(2,2) に対応します。

D
D = 2×2
10-3 ×

    0.0000         0
         0    0.2873


w = V(:,2);

eigs を使用したフィードラー ベクトルの計算は、比較的大規模なグラフに対しても拡張性があります。これは固有値と固有ベクトルはそのサブセットのみが計算されるためです。ただし、グラフの規模が比較的小さい場合は、ラプラシアン行列を非スパースのストレージ形式に変換して eig(full(L)) を使用することも可能です。

グラフの分割

フィードラー ベクトル w を使用して、グラフを 2 つの部分グラフに分割します。ノードの w に正の値がある場合は、このノードが部分グラフ A に割り当てられます。そうでない場合、ノードは部分グラフ B に割り当てられます。この方法は "符号カット" または "ゼロしきい値カット" と呼ばれます。符号カットでは、グラフにおける任意の自明ではないカットの重みの上限と下限に基づいて、カットの重みが最小になります。

符号カットを使用してグラフを分割します。w>=0 の場合はノードの部分グラフを赤色で強調表示し、w<0 の場合はそのノードを黒色で強調表示します。

highlight(p,find(w>=0),'NodeColor','r') % subgraph A
highlight(p,find(w<0),'NodeColor','k') % subgraph B

このバーベル グラフでは、この分割によってグラフが 2 つの均等なノード セットに正確に二等分されます。ただし、符号カットでは必ずしも均等なカットが生成されるとは限りません。

w の中央値を計算し、それをしきい値として使用することにより、グラフを二等分することも常に可能です。この分割は "中央値カット" と呼ばれ、それぞれの部分グラフのノード数が等しくなることが保証されます。

中央値カットを使用するには、まず w 内の値を中央値でシフトします。

w_med = w - median(w);

次に、w_med 内で符号によってグラフを分割します。このバーベル グラフでは、w の中央値はゼロに近いため、ほぼ均等な 2 つのカットが生成されます。

参考

| | |

関連するトピック