グラフのラプラシアンの復習

昔やっていたことを復習して、今関心を持っていることに結びつける。

点と線からなるグラフＧについて、隣接行列をＡ、対角成分に点の次数を並べた行列をＤとすると、Ｄ−Ａを組み合わせ論的なＧのラプラシアンという。
Ｇをｎ個の点からなるとき、i 番目の点から j 番目の点に辺があるときに
$A_{i,j} = 1$ 辺がないときに $A_{i,j} = 0$ とする。
Ｄは i 番目の点から出ている辺の本数を $\deg(i)$ とし、 $D_{i,i} = \deg(i)$ とし、対角成分以外は 0 とする。

たとえば次のような例だと

$A = \left( \begin{array}{ccccc} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ \end{array} \right)$

$D = \left( \begin{array}{ccccc} 2 & 0 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 & 0 \\ 0 & 0 & 0 & 3 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right)$

$\Delta = \left( \begin{array}{ccccc} 2 & -1 & -1 & 0 & 0 \\ -1 & 2 & 0 & -1 & 0 \\ -1 & 0 & 2 & -1 & 0 \\ 0 & -1 & -1 & 3 & -1 \\ 0 & 0 & 0 & -1 & 1 \\ \end{array} \right)$

Ａの代わりにグラフの推移行列Ｐ、Ｄのかわりに単位行列Ｉを使って、Ｉ−Ｐを確率論的なＧのラプラシアンという。これはグラフの点を状態とし、辺に沿って状態がある確率で変化するときに $P_{i,j}$ で i 番目から j 番目の点へ移動する確率をあらわしたものである。したがって、行列 P の列をすべて足すと 1 になる。*1

なぜ唐突にこういうことを思い出したのかというと、通常は微分方程式を離散化して解く場合に差分方程式を考えるが、逆に差分方程式から考えてその極限として微分方程式があると考えることもできることから、それと同様に、離散ラプラシアンを使って微分方程式をその極限として「見る」にはどうすればいいのかを考えてみたいわけである。

*1:つまり、いわゆるマルコフチェインを行列であらわしたもの

tkenichi の日記

毒舌皮肉系恥さらし日記

グラフのラプラシアンの復習