ベクトルにラプラシアン行列を掛けてみる
ここ数日でラプラシアン行列について勉強したこと
グラフ
グラフはG (V , E) と定義されます。
この時、Vはグラフを構成する点の集合で、Eは点の連結情報。
Eは辺とよばれますね。
点に関しては一意な整数を付けてあげるのが普通みたいですね。
この辺にもし向きがあるなら、例えば１→２はいけるけどその逆の２→１はダメとか、有向グラフと呼びます。
そういう向きがないなら無向グラフと呼びます。
例えば、Webのリンク構造を単純に考えるなら向きが関係あるので有向グラフですね。
隣接グラフ
グラフGに対して点の総数をNとします。N×Nの行列を作り、そのi,j成分を辺のある無しで１か０を代入してあげると隣接グラフになります。
対角成分は普通なら０をいれます。
例えば、１、２、３という三つの点と１ー２、２ー３のふたつの辺からなるグラフは
0 1 0 1 0 1 0 1 0
と書けます。
ちなみに、例えば駅の路線図や交通網、ネットワークなら隣接行列の成分を１ではなく例えば点間の距離や料金とか意味のある重みをつけてあげます。
度数
ある点の関係がある辺の総数を度数といいます。
Webのリンク構造なら被リンク数ですね。
先ほどのグラフなら、１の点は１ー２の辺しか関係ないから度数は１。
２の点は１ー２、２ー３と関係があるので度数は２
３の点は２ー３の辺だけなので度数は１
ラプラシアン行列
この前の日記にも書きましたが、ラプラシアン行列の正しい定義は
対角成分に度数を並べた行列 - 隣接行列
と書きます。
先ほどのグラフでいうと
|1 0 0| |0 1 0| |0 2 0| - |1 0 1| |0 0 1| |0 1 0|
なので
| 1 -1 0| |-1 2 -1| | 0 -1 1|
となります。
ベクトルと隣接行列
話はもどって隣接行列に。
グラフの各点にある重み付けがされていたとします。
ここでは重みに意味がないです、例えば交通網を考えるならある場所の現時点の車の数とかでいいです。
これを隣接行列と同じ順序に並べたベクトルを考えます。
先ほどの例なら
１には３
２には４
３には５
| 3 | | 4 | | 5 |
隣接行列に掛けると
| 0 1 0 | | 3 | | 4 | | 1 0 1 | * | 4 | = | 8 | | 0 1 0 | | 5 | | 4 |
重み付け無しの無向グラフなんであまりすごい意味がないですが…。
有向グラフで重み付けがあるなら各点のつぎの時間の車の量とかになりますね。
つまり、各点の流量を考える事ができるはずです。
ベクトルとラプラシアン行列
隣接行列の時と同様に、今度はラプラシアン行列とベクトルの積を考えてみます。
| 1 -1 0| | 3 | | 3 - 4 | |-1 2 -1| * | 4 | = | 8 -3 -5 | | 0 -1 1| | 5 | | 5 -4 |
この計算はある成分に着目すると、例えばi成分なら
（i点の度数×i点の重み) - Σ(i点に辺を経由して隣接している成分の重み)
とも見れるとおもいます。
ラプラシアン行列の固有値と固有ベクトル
各点の重みを成分としたベクトルをv
ラプラシアン行列をL
その演算結果のベクトルwとして
w = L * v
について考えてみます。wがv'の定数倍になるなら
w = λv' = L * v'
