Laplacian)がなぜラプラシアンと呼ばれるのかを、普通の関数に対するラプラシアンオペレータと比較して直観的に説明する。ついでに普通の関数のときにラプラシアンとまとめて紹介されるナブラについて、それに対応する接続行列について紹介する。グラフラプラシアンってカタカナで書くとめちゃくちゃ読みにくいな。Laplacianなら全然読めるけど両方カタカナで空白つけないのが良くない。いうのGraphが漢字なら日本語にしたとき丁度よいのだが。Laplacianといい、グラフ\(G\)が何を指すか明らかなときは単に\(L\)とかく。\(\mathcal{L}\)のときもある。V\)は\(i\)番目の頂点を示す。\(\deg\)は頂点の次数。念のため次数とはその頂点につながっている辺の数のこと。グラフの次数行列\(D\)と隣接行列\(A\)を用いるとグラフラプラシアンは次のようにかける。\end{equation}\]いずれも\(G\)によって決まる行列だが明らかなので省略する。matrix)とは\(\{0,1\}\)のみを要素にもつ行列で\(i,j\)間のエッジが存在すれば\(1\)、そうでなければ\(0\)を取る。\end{gather}\]Graphラプラシアンの例こういうグラフの場合を考えると、それぞれ次のようになる。\end{gather}\]ここまでは普通の話。名前からして実関数に対するラプラシアンオペレータと関係とおかしいだろうということで実際関係していることを直観的に示していく。簡単な場合を使って2変数関数\(f(x,y)\)に対するラプラシアンを考える。\end{equation}\]となる。Laplacianと結びつけるために、この値を離散化して数値計算しようと試みてみる。単純な離散化のやり方は次だろう。\end{align}\]小さい\(h\)をとって素朴に前進差分と後退差分を使って勾配を計算し、さらにその差から2階微分を求めている。\(y\)についても同じことをやると次がすぐにわかる。\end{multline}\]もう言いたいこと分かったと思うがこれは実平面を拡張したような次のグラフに対応している。直観的に符号が定義と異なるが、このグラフから向きという概念をなくすということを考えればいい。このグラフはもともとの実平面の性質から数字の大小という意味で「向き」をもっているが、無向グラフの世界ではそのような概念は無いのでラプラシアンをグラフに作用させることを考えるにあたって「自分引く相手の総和」を用いることはまぁアナロジーとして許せる範囲だろう。ついでにグラフ上の調和関数を考える時はゼロかゼロでないかが重要なので符号が逆転していても構わない。Laplacianは普通のラプラシアンのグラフに対する拡張っぽくなっていることが気持ち的には分かった。うまい説明は無数にある気がしているが次にいく。グラフに対するLaplacianと調和関数ここまでの話を踏まえてグラフの頂点を定義域とする関数\(f:V\to\mathbb{R}\)を考えると、実関数に対するラプラシアンから得た「自分引く相手の総和」というアナロジーから次の値をおもいつく。function)で引数内が成り立つなら1、それ以外の場合にはゼロとなる便利なヤツ。実関数にたいするLaplacianがある種の演算子であったことを考えるとグラフに対するLaplacianも\(f\)という関数を介することなく定義されるべきだろう。Laplacianの定義そのもの。これは式をいじるまでもなく簡単に確かめられる。\end{equation}\]とでも定義してやれば同じように使える。注意しておくとこれは行列の計算でもなんでもなくてただ\(Lf\)をこう定義しただけ。ようは\(L\)が\(f\)によらずに決定されていてこの\(L\)を用いることで\(i=1,\dots,n\)に対する\(f(v_i)\)のラプラシアンが計算できていればいい。関数\(f:V\to\mathbb{R}\)についても調和関数かどうかがこれによって定義できる。\end{equation}\]を満たすこと。いくらでも他の書き方は存在します。実関数の場合には\(\Delta=\nabla\cdot\nabla\)というような式があったがこれに対応するものが有向グラフの場合にはある。一度いうと有向グラフの場合にはある。無向グラフには向きという概念が無いから勾配という概念に対応するものも無くてまぁ不思議ではないね。e_j\)はそれぞれ\(i\)番目の頂点と\(j\)番目の辺のこと。有向グラフの場合には次のようにやるのが自然だろう。w\}\)において\(v\)と\(w\)の順番に意味があるので集合ではなくベクトルのような記法\(e=(v,w)\)を用いることが多い。集合の場合には要素の順番は考慮されないがベクトルの場合は考慮するので。e\)なんかの使い方はゆるす。例をみたほうが早いだろう。Graphラプラシアンのときと同じグラフを用いる。\end{equation}\]が各要素の値となる。行が頂点に対応していて列が辺に対応している。列の値を埋めるなら必ず2つの要素が1になる列に注目して辺の両端に対応する所に1を埋めていくのが易しい。次に有向グラフの場合の例、さっきのグラフの各辺に適当に向きを入れてみる。この場合も簡単で、結果は次のようになる。\end{equation}\]有向グラフの場合は各列で\(1,-1\)がそれぞれ1回ずつあらわれる。f\)を次のように与えるのが自然だろう。\end{equation}\]少し書き方はビミョーな感じはするが、ようするにある点\(v\)における勾配は、そこに接続している辺ごとに定義されていてその辺の向きによってどっちかの差分で定義されるというもの。これを実関数のときのアナロジーでいうと、関数\(f(x,y)\)のある点\((a,b)\)における勾配は\(x\)成分\(f_x(a,b)\)と\(y\)成分\(f_y(a,b)\)が存在するということに対応する。3変数関数なら3成分あるし4変数なら4成分というようにある点に対していくつかの勾配成分があることは自然なことだ。ちなみに無向グラフに対しては差分を取るときの符号が決められないのでこのようにしてグラフ上の関数の勾配を考えることはできない。Laplacianと同じようにして勾配をあたえる計算式を作り出せる。\end{equation}\]に対応していることがわかる。接続行列とグラフラプラシアンの関係ここまでくると\(\Delta=\nabla\cdot\nabla\)のアナロジーにより\(L=BB^\top\)であってほしいが実際これは成り立つ。次のようにして示せる。\end{align}\]次のようにしてってわけでもなんでもないが2行目の式から左辺の行列の\(i,j\)要素は接続行列の\(i\)行目と\(j\)行目の内積で表せるということがわかるので、あとは具体例も参照しつつ\(i=j\)の場合とそうでない場合において何が起こるかを確かめていけばいい。明らかなように無向グラフの場合は接続行列の要素に負の値が無いからどうやっても\(L=BB^\top\)とはならないことに注意。以上でグラフラプラシアンを普通のラプラシアンのグラフに対する拡張であるという風に解釈できた。ついでに勾配のナブラに対する接続行列も有向グラフの場合にはちゃんとイケてることも確認した。PostAbout個人的メモサイト的電子ノート。誰かに見られる可能性のある場所に置いておく事に意味があることもある。実際に誰か見ているかどうかはそんなに気にしないし後から見たら間違ったことも書いている。ノートだし消すこともないかということで置いたまま悪しからず。JsonSitemapXMLContact万が一何か言いたいことがあればコチラまで。