グラフ理論パッケージと行列関連の機能を使うと、色々とグラフの性質を計算できるそうです。特に行列の固有値から色々な性質がわかる理論があり、「スペクトルグラフ理論」と呼ばれているようです。
なんだか響きもカッコイイですよね。「スペクトルグラフ理論」。
今回は次の定理を実際に試してみます。
定理：重み無し無向グラフの連結成分の個数は、そのグラフのラプラシアン行列のゼロ固有値の個数に等しい」
例えば次のPDFの10ページの下の方に「初等的な事実」として記載されています。
http://www.cs.yale.edu/homes/spielman/PAPERS/SGTChapter.pdf
では実際にグラフを作ってこの定理を確かめてみます。
(%i1) load(graphs)$
ランダムにグラフを作ります。13頂点で頂点間を結ぶ確率を0.15としてグラフを作りました。
(%i2) g:random_graph(13,0.15);
$$ \tag{%o2} \verb|GRAPH(13 vertices, 8 edges)| $$
このグラフを描画してみましょう。
(%i3) draw_graph(g);
$$ \tag{%o3} \mathbf{done} $$
結ぶ確率が低いためバラバラなグラフができました。連結成分の個数は目視で6とわかります。グラフの連結成分を求める関数connected_components(g)を呼ぶと、連結成分のリストが得られます。このリストの長さを求めれば、それが連結成分の個数です。
(%i4) length(connected_components(g));
$$ \tag{%o4} 6 $$
さて、では早速グラフgのラプラシアン行列を求めてみます。ちなみにラプラシアン行列とは、隣接行列に-1をかけて、次に対角要素に、その列に含まれる-1の個数を入れた行列です。
(%i5) m:laplacian_matrix(g);
$$ \tag{%o5} \begin{pmatrix}3&0&0&0&-1&0&0&-1&0&0&-1&0&0\\ 0&1&-1&0&0&0&0&0&0&0&0&0&0\\ 0&-1&1&0&0&0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0&0&0&0&0&0\\ -1&0&0&0&2&0&0&0&-1&0&0&0&0\\ 0&0&0&0&0&1&0&0&0&0&-1&0&0\\ 0&0&0&0&0&0&0&0&0&0&0&0&0\\ -1&0&0&0&0&0&0&2&0&0&-1&0&0\\ 0&0&0&0&-1&0&0&0&1&0&0&0&0\\ 0&0&0&0&0&0&0&0&0&1&-1&0&0\\ -1&0&0&0&0&-1&0&-1&0&-1&4&0&0\\ 0&0&0&0&0&0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0&0&0&0&0&0 \end{pmatrix} $$
ラプラシアン行列の定義から、各行の要素を足すと必ず0になることがわかります。この例でも確かになっていますね。
次に固有値を求めてみます。通常eigenパッケージを読み込んでeivals()関数を使うと、固有値、固有値の重複度、対応する固有ベクトルが求まります。
(%i6) load(eigen)$
(%i7) eivals(m);
part: fell off the end.
#0: eigenvalues(mat=matrix([3,0,0,0,-1,0,0,-1,0,0,-1,0,0],[0,1,-1,0,0,0,0,0,0,0,0,0,0],[0,-1,1,0,0,0,0,0,0,0,0,0,0],[0,0...)(eigen.mac line 94)
#1: eivals(mat=matrix([3,0,0,0,-1,0,0,-1,0,0,-1,0,0],[0,1,-1,0,0,0,0,0,0,0,0,0,0],[0,-1,1,0,0,0,0,0,0,0,0,0,0],[0,0...)(eigen.mac line 189)
-- an error. To debug this try: debugmode(true);
ただやってみると少し大きな行列になるとこのようなエラーが出てしまい、固有値が求まりません。
Maximaには行列の固有値を数値的に求める関数がいくつか実装されているので、そちらを使ってみます。ラプラシアン行列は対称行列でかつすべての要素が実数です。その場合、eigens_by_jacobi()という関数を使うことができます。
(%i8) first(eigens_by_jacobi(m));
$$ \tag{%o8} \left[ 5.122828203736173 , 2.0 , 0.0 , 0.0 , 1.189685513242651 , \\ 0.3679121302815039 , 0.0 , 2.373208566941235 , \\ 5.586951126992194 \times 10^{-17} , 0.9999999999999998 , \\ 3.946365585798438 , 0.0 , 0.0 \right] $$
これで固有値がすべて求まりました。絶対値が十分に小さいものを1に、そうでない値を0に置き換えてから、合計をとれば、絶対値が十分に小さい固有値の個数を数えられます。
(%i9) apply("+", map(lambda([x],if abs(x)<1.0e-15 then 1 else 0),%));
$$ \tag{%o9} 6 $$
ちゃんと6になりました。
最近のネットワーク解析（SNSの友達関係、Internetの接続状態、、、）ではこのような理論をベースとした解析が行われているそうです。
