ラプラシアン行列のソースを表示

{{Otheruses|グラフ理論で用いる行列|微分作用素のラプラシアン|ラプラス作用素}}
[[グラフ理論]]の[[数学]]的分野において、'''ラプラシアン行列'''（ラプラシアンぎょうれつ、{{lang-en-short|Laplacian matrix}}）は、[[グラフ (離散数学)|グラフ]]の[[行列]]表示（行列表現）である。'''アドミタンス行列''' (admittance matrix)、'''キルヒホッフ行列''' (Kirchhoff matrix)、'''離散ラプラシアン''' (discrete Laplacian)、または'''ラプラス行列'''と呼ばれることもある。ラプラシアン行列はグラフの多くの有用な性質を探るために使うことができる。{{仮リンク|キルヒホッフの定理|en|Kirchhoff's theorem}}と一緒に、任意のグラフについての[[全域木]]の数を計算するために使うことができる。グラフの[[カット (グラフ理論)|最疎カット]]は{{仮リンク|チーガー定数 (グラフ理論)|en|Cheeger constant (graph theory)|label=チーガーの不等式}}によってそのラプラシアンの2番目に小さい固有値を使って近似することができる 。また、{{仮リンク|非線形次元削減|en|Nonlinear dimensionality reduction|label=低次元埋め込み}}を構築するためにも使うことができる。これは、様々な[[機械学習]]応用のために有用かもしれない。

== 定義 ==
=== 単純グラフのラプラシアン行列 ===
''n''個の[[頂点 (グラフ理論)|頂点]]を持つ[[グラフ (離散数学)|単純グラフ]]（ループや多重辺を持たない無向グラフ）を考えると、そのラプラシアン行列<math display="inline">L_{n \times n}</math>は以下の式で定義される<ref name="mathworld">{{MathWorld |urlname=LaplacianMatrix |title=Laplacian Matrix}}</ref>。
: <math>L = D - A</math>
上式において、''D''はグラフの[[次数行列]]、''A''は[[隣接行列]]である。<math display="inline">G</math>は単純グラフであるから、<math display="inline">A</math>の成分は1または0のみであり、その対角要素は全て0である。

{{仮リンク|有向グラフ|en|Directed graph}}の場合は、[[次数 (グラフ理論)|入次数または出次数]]のいずれかが、用途に応じて用いられるであろう。

<math display="inline">L</math>の要素は式
: <math>L_{i,j} := \begin{cases}
  \deg(v_i) &\mbox{if}\ i = j \\
         -1 &\mbox{if}\ i \neq j\ \mbox{and}\ v_i \mbox{ is adjacent to } v_j \\
          0 &\mbox{otherwise}
\end{cases}</math>
により与えられる。上式において、<math>\operatorname{deg}(v_i)</math>は頂点<math>i</math>の次数である。

==== 対称正規化ラプラシアン ====
対称正規化ラプラシアン行列は
: <math>L^\text{sym} := D^{-\frac{1}{2}} L D^{-\frac{1}{2}} = I - D^{-\frac{1}{2}} A D^{-\frac{1}{2}}</math>,
として定義される<ref name="mathworld" />。

<math display="inline">L^\text{sym}</math>の要素は
:<math>L^\text{sym}_{i,j} := \begin{cases}
                                     1 &\mbox{if } i = j \mbox{ and } \deg(v_i) \neq 0\\
  -\frac{1}{\sqrt{\deg(v_i)\deg(v_j)}} &\mbox{if } i \neq j \mbox{ and } v_i \mbox{ is adjacent to } v_j \\
                                     0 &\mbox{otherwise}.
\end{cases}</math>
によって与えられる。

====酔歩正規化ラプラシアン ====
酔歩正規化ラプラシアン行列は
: <math>L^\text{rw} := D^{-1}L = I - D^{-1}A</math>
として定義される。

<math display="inline">L^\text{rw}</math>の要素は
:<math>L^\text{rw}_{i,j} := \begin{cases}
                     1 &\mbox{if } i = j \mbox{ and } \deg(v_i) \neq 0\\
  -\frac{1}{\deg(v_i)} &\mbox{if } i \neq j \mbox{ and } v_i \mbox{ is adjacent to } v_j \\
                     0 &\mbox{otherwise}.
\end{cases}</math>
によって与えられる。

==== 一般化ラプラシアン ====
一般化ラプラシアン''Q''は
: <math>\begin{cases}
        Q_{i,j} < 0 &\mbox{if } i \neq j \mbox{ and } v_i \mbox{ is adjacent to } v_j\\
        Q_{i,j} = 0 &\mbox{if } i \neq j \mbox{ and } v_i \mbox{ is not adjacent to } v_j \\
  \mbox{any number} &\mbox{otherwise}.
\end{cases}</math>
として定義される<ref>{{cite book |last1= Godsil |first1=C. |last2= Royle |first2=G. |date=2001 |title=Algebraic Graph Theory, Graduate Texts in Mathematics |publisher= Springer-Verlag}}</ref>。

普通のラプラシアンは一般化ラプラシアンであることが分かる。

== 例 ==
以下はラベル付けされた無向グラフとそのラプラシアン行列の単純な例である。

{|class="wikitable"
! {{仮リンク|グラフラベリング|en|Graph labeling|label=ラベル付けされたグラフ}}
! [[次数行列]]
! [[隣接行列]]
! ラプラシアン行列
|-
| [[画像:6n-graf.svg|175px]]
| <math display="inline">\left(\begin{array}{rrrrrr}
  2 &0 &0 &0 &0 &0 \\
  0 &3 &0 &0 &0 &0 \\
  0 &0 &2 &0 &0 &0 \\
  0 &0 &0 &3 &0 &0 \\
  0 &0 &0 &0 &3 &0 \\
  0 &0 &0 &0 &0 &1 \\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrrrrr}
  0 &1 &0 &0 &1 &0 \\
  1 &0 &1 &0 &1 &0 \\
  0 &1 &0 &1 &0 &0 \\
  0 &0 &1 &0 &1 &1 \\
  1 &1 &0 &1 &0 &0 \\
  0 &0 &0 &1 &0 &0 \\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrrrrr}
   2 &-1 &0  &0  &-1 &0 \\
  -1 & 3 &-1 &0  &-1 &0 \\
   0 &-1 &2  &-1 &0  &0 \\
   0 & 0 &-1 &3  &-1 &-1 \\
  -1 &-1 &0  &-1 &3  &0 \\
   0 & 0 &0  &-1 &0  &1 \\
\end{array}\right)</math>
|}

== 性質 ==
（無向）グラフ''G''と[[固有値]]<math display="inline">\lambda_0 \le \lambda_1 \le \cdots \le \lambda_{n-1}</math>を持つそのラプラシアン行列''L''について:
* ''L''は対称である。
* ''L''は[[行列の定値性|半正定値]]である（すなわち全ての<math display="inline">i</math>について<math display="inline">\lambda_i \ge 0</math>）。これは[[#接続行列|接続行列]]の節で検証される。これは、ラプラシアンが対称であり、{{仮リンク|優対角行列|en|Diagonally dominant matrix|label=優対角}}であるという事実からも見ることができる。
* ''L''は[[M-行列]]である（その非対角成分は非正であり、そのうえその固有値の実部は非負である）。
* ''L''の全ての行の和と列の和はゼロである。実際、和の計算において、頂点の次数には隣接する頂点ごとに「−1」が足される。
* その結果、<math display="inline">\lambda_0 = 0</math>となる。これは、ベクトル<math display="inline">\mathbf{v}_0 = (1, 1, \dots, 1)</math>が<math display="inline">L \mathbf{v}_0 = \mathbf{0} </math>を満たすためである。これは、ラプラシアン行列が特異行列であることも暗示する。
* グラフ中の{{仮リンク|成分 (グラフ理論)|en|Component (graph theory)|label=連結成分}}の数はラプラシアンの[[零空間]]の次元であり、0固有値の[[固有値と固有ベクトル|代数的多重度]]である。
* ''L''の最小の非ゼロ固有値は{{仮リンク|スペクトルギャップ|en|Spectral gap}}と呼ばれる。
* ''L''の2番目に小さな固有値（ゼロかもしれない）は''G''の{{仮リンク|代数的連結度|en|algebraic connectivity}}（Fiedler値）であり、グラフの最疎カットを近似する。
* [[ラプラシアン]]は、関数<math display="inline">f : V \to \mathbb{R}</math>（<math display="inline">V</math>は''G''の頂点セット、<math display="inline">n = |V|</math>）のn次元ベクトル空間上の作用素である。
* Gが[[k正則]]である時、正規化ラプラシアンは<math display="inline">\mathcal{L} = \tfrac{1}{k} L = I - \tfrac{1}{k} A</math>である（Aは隣接行列、Iは単位行列）。
* 複数の連結成分を持つグラフについて、''L''は[[区分行列|区分対角行列]]であり、それぞれの区分はそれぞれの成分についての（場合によると頂点を順序付けし直した後の）各ラプラシアン行列である（すなわち''L''は区分対角行列と置換相似である）。
* ラプラシアン行列''L''の[[跡 (線型代数学)|跡]]（トレース）は<math display="inline">2m</math>（<math display="inline">m</math>は考慮されているグラフの辺の数）と等しい。

== 接続行列 ==
:<math>M_{ev} = \left\{\begin{array}{rl}
   1, &\text{if } v = i\\
  -1, &\text{if } v = j\\
   0, &\text{otherwise}.
\end{array}\right.</math>
によって与えられる辺''e''（頂点''i''と''j''を連結している; ''i'' > ''j''）と頂点''v''について要素''M{{sub|ev}}''を持つ<math display="inline">|e| \times |v|</math>有向[[接続行列]]''M''を定義する。

次に、ラプラシアン行列''L''は
:<math>L = M^\textsf{T} M\,,</math>
を満たす（<math display="inline">M^\textsf{T}</math>は''M''の[[転置行列]]）。

ここで、単位ノルム固有値ベクトル<math display="inline">\mathbf{v}_i</math>および対応する固有値<math display="inline">\lambda_i</math>を使った<math display="inline">L</math>の[[固有値分解]]を考える。
:<math>\begin{align}
  \lambda_i &= \mathbf{v}_i^\textsf{T} L \mathbf{v}_i \\
            &= \mathbf{v}_i^\textsf{T} M^\textsf{T} M \mathbf{v}_i \\
            &= \left(M \mathbf{v}_i\right)^\textsf{T} \left(M \mathbf{v}_i\right) \\
\end{align}</math>

<math display="inline">\lambda_i</math>はベクトル<math display="inline">M \mathbf{v}_i</math>とそれ自身の内積として書くことができるため、これは<math display="inline">\lambda_i \ge 0</math>であり、したがって<math display="inline">L</math>の固有値は全て非負であることを示す。

== 変形ラプラシアン ==
'''変形ラプラシアン'''（deformed laplacian）は通常以下のように定義される。
:<math>\Delta(s) = I - sA + s^2(D - I)</math>
上式において、''I''は単位行列、''A''は隣接行列、''D''は次数行列、''s''は（複素）数である。ここで留意すべきは、標準的なラプラシアンは単に<math display="inline">\Delta(1)</math>となることである<ref>{{cite journal |title=The Deformed Consensus Protocol |first=F. |last=Morbidi |journal=Automatica |volume=49 |number=10 |pages=3049–3055 |year=2013 |doi=10.1016/j.automatica.2013.07.006}}</ref>。

== 対称正規化ラプラシアン ==
'''（対称）正規化ラプラシアン'''は以下のように定義される。
: <math>L^\text{sym} := D^{-\frac{1}{2}} L D^{-\frac{1}{2}} = I - D^{-\frac{1}{2}}AD^{-\frac{1}{2}}</math>
上式において、''L''は（非正規化）ラプラシアン、''A''は隣接行列、''D''は次数行列である。次数行列''D''は[[対角行列]]で正であるため、その逆数平方根<math display="inline">D^{-\frac{1}{2}}</math>は単にその対角成分が''D''の対角成分の正の平方根の逆数である対角行列となる。対称正規化ラプラシアンは[[対称行列]]である。

<math display="inline">L^\text{sym} = S S^*</math>が存在する。Sは、列が頂点によって添え字を付けられ、行がGの辺によって添え字が付けられた行列である。これらは、辺e = {u, v} に対応するそれぞれの行がuに対応する列において成分<math display="inline">\frac{1}{\sqrt{d_u}}</math>を、vに対応する列において成分<math display="inline">-\frac{1}{\sqrt{d_v}}</math>を、それ以外では0成分を持つことになるように索引付けされる（注: <math display="inline">S^*</math>はSの転置行列を示す）。

正規化ラプラシアンの全ての固有値は実数かつ非負である。これは以下のように見ることができる。<math display="inline">L^\text{sym}</math>は対称であるため、その固有値は実数である。これらの固有値は全て非負である。固有値&lambda;を持つ<math display="inline">L^\text{sym}</math>の固有ベクトル <math display="inline">g</math>を考え、<math display="inline">g = D^\frac{1}{2} f</math>を仮定する（gおよびfを頂点v上の実関数と見なすことができる）。すると、
:<math>
  \begin{align}
\lambda&=\frac{\langle g, L^\text{sym}g\rangle}{\langle g, g\rangle}\\
&= \frac{\langle g, D^{-\frac{1}{2}} L D^{-\frac{1}{2}} g\rangle}{\langle g, g\rangle}\\
&= \frac{\langle f, Lf\rangle}{\langle D^\frac{1}{2} f, D^\frac{1}{2} f\rangle}\\
&= \frac{\sum_{u \sim v}(f(u) - f(v))^2}{\sum_v f(v)^2 d_v}
\geq 0
\end{align}
</math>
となる。ここでは内積<math display="inline">\langle f,g\rangle = \sum_{v} f(v)g(v)</math>（全ての頂点vにわたる和）を用い、<math display="inline">\sum_{u\sim v}</math>は隣接頂点 {u,v} の全ての{{仮リンク|非順序対|en|Unordered pair}}にわたる和を示す。量<math display="inline">\sum_{u,v}(f(u) - f(v))^2</math>はfの「ディリクレ和」と呼ばれるが、式<math display="inline">\frac{\left\langle g, L^\text{sym}g\right\rangle}{\langle g, g\rangle} </math>はgの[[レイリー商]]と呼ばれる。

'''1'''をそれぞれの頂点上に値1を想定する関数とする。すると、<math display="inline">D^\frac{1}{2} 1</math>は固有値0を持つ<math display="inline">L^{\text{sym}}</math>の固有関数である<ref>{{Cite book |last=Chung |first=Fan R. K. |authorlink=金芳蓉|title=Spectral graph theory |year=1997 |publisher=American Math. Soc. |location=Providence, RI |isbn=978-0-8218-0315-8 |edition=Repr. with corr., 2. [pr.]}}</ref>。

実際、正規化対称ラプラシアンの固有値は0 = μ{{sub|0}} ≤ … ≤ μ{{sub|n−1}} ≤ 2を満たす。これらの固有値（正規化ラプラシアンのスペクトルと呼ばれる）は、一般グラフに対するその他のグラフ[[不変量]]とよく関連する<ref>{{Cite book |last=Chung |first=Fan |authorlink=金芳蓉 |title=Spectral Graph Theory |url=http://www.math.ucsd.edu/~fan/research/revised.html |origyear=1992 |year=1997 |publisher=American Mathematical Society |isbn=978-0821803158}}</ref>。

== 酔歩正規化ラプラシアン ==
'''酔歩''' (random walk) '''正規化ラプラシアン'''は
: <math>L^\text{rw} := D^{-1} L</math>
として定義される。''D''は次数行列である。次数行列''D''対角行列であるため、その逆行列<math display="inline">D^{-1}</math>は単純に対角行列として定義され、これは''D''の対応する正の対角成分の逆数である対角成分を持つ。

孤立した頂点（次数が0）について、一般的な選択は対応する要素<math display="inline">L^\text{rw}_{i,i}</math>を0にすることでる。

この慣習によって、固有値0の多重度がグラフの連結した構成要素の数と等しくなるという良い性質がもたらされる。

<math display="inline">L^\text{rw}</math>の行列要素は以下の式で与えられる。
: <math>L^{\text{rw}}_{i,j} := \begin{cases}
                     1 &\mbox{if}\ i = j\ \mbox{and}\ \deg(v_i) \neq 0\\
  -\frac{1}{\deg(v_i)} &\mbox{if}\ i \neq j\ \mbox{and}\ v_i \mbox{ is adjacent to } v_j \\
                     0 &\mbox{otherwise}
\end{cases}</math>

酔歩正規化ラプラシアンの名称は、この行列が<math display="inline">L^\text{rw} = I - P</math>（<math display="inline">P = D^{-1}A</math>は単純にグラフ上の[[ランダムウォーク|酔歩者]]〈ランダムウォーカー〉の遷移行列）という事実から来ている。例えば、<math display="inline"> e_i </math>がi番目の[[標準基底]]ベクトルを示すものとする。すると、<math display="inline">x = e_i P </math>は頂点<math display="inline">i</math>から一歩進んだ後の酔歩者の位置の分布を示す{{仮リンク|確率ベクトル|en|Probability vector}}である; すなわち、 <math display="inline">x_j = \mathbb{P}\left(v_i \to v_j\right)</math>。より一般的には、もしベクトル<math display="inline"> x </math>がグラフの頂点上の酔歩者の位置の確率分布であるとすれば、<math display="inline">x' = x P^t</math>は<math display="inline">t</math>歩後の酔歩者の確率分布である。

: <math>L^\text{rw} = I-D^{-\frac{1}{2}}\left(I - L^\text{sym}\right) D^\frac{1}{2}</math>
となることを確認することができる。

すなわち、<math display="inline">L^\text{rw}</math>は正規化ラプラシアン<math display="inline">L^\text{sym}</math>と類似している。この理由のため、<math display="inline">L^\text{rw}</math>がたとえ一般に[[エルミート行列]]でないとしても、実固有値を持つ。実際、その固有値は（エルミート行列である）<math display="inline">L^\text{sym}</math>のものと一致する。

=== グラフ ===
[[ランダムウォーク|グラフ上の酔歩]]に関する余談として、単純[[無向グラフ]]を考える。酔歩者が時間''t''に頂点''i''にいる確率を考え、酔歩者が時間''t-1''に頂点''j''にいた確率分布を仮定する（任意の頂点に結合したいかなる辺に沿った一歩について一様の見込みを仮定する）:
: <math>p_i(t) = \sum_j \frac{A_{ij}}{\deg\left(v_j\right)} p_j(t - 1),</math>
または行列-ベクトル記法で:
:<math>p(t) = A D^{-1} p(t - 1).</math>

（<math display="inline">t\rightarrow \infty</math>として設定される平衡は<math display="inline">p = A D^{-1} p </math>として定義される。）

この関係は
:<math>D^{-\frac{1}{2}} p(t) = \left[D^{-\frac{1}{2}} A D^{-\frac{1}{2}}\right] D^{-\frac{1}{2}} p(t - 1)</math>
と書き直すことができる。

<math display="inline">A_\text{reduced} \equiv D^{-\frac{1}{2}} A D^{-\frac{1}{2}}</math>は'''簡約隣接行列'''と呼ばれる対称行列である。したがって、この酔歩者の一歩は<math display="inline">A_\text{reduced}</math>の累乗を必要とする。<math display="inline">A_\text{reduced}</math>は対称行列であるため、これは単純な操作である。

== 離散ラプラス演算子としての解釈 ==
ラプラシアン行列は、{{仮リンク|離散ラプラス演算子|en|Discrete Laplace operator}}の特定の事例の行列表現として解釈することができる。このような解釈によって、例えば、ラプラシアン行列を無限の数の頂点と辺を持つグラフ（無限サイズのラプラシアン行列となる）の場合に一般化することが可能となる。

<math display="inline">\phi</math>がグラフにわたる熱分布を記述すると想定する（<math display="inline">\phi_i</math>は頂点<math display="inline">i</math>における熱である）。[[ニュートンの冷却の法則]]に従えば、節<math display="inline">i</math>と節<math display="inline">j</math>の間を移る熱は、もし節<math display="inline">i</math>と節<math display="inline">j</math>が連結されているならば、<math display="inline">\phi_i - \phi_j</math>に比例する（節が連結されていないならば、熱は移らない）。

すると、熱用量<math display="inline">k</math>について、

:<math>\begin{align}
  \frac{d \phi_i}{d t}
    &= -k \sum_j A_{ij} \left( \phi_i - \phi_j \right) \\
    &= -k \left( \phi_i \sum_j A_{ij} - \sum_j A_{ij} \phi_j \right) \\
    &= -k \left( \phi_i \ \deg(v_i) - \sum_j A_{ij} \phi_j \right) \\
    &= -k \sum_j \left( \delta_{ij} \ \deg(v_i) - A_{ij} \right) \phi_j \\
    &= -k \sum_j \left( \ell_{ij} \right) \phi_j.
\end{align}</math>

行列-ベクトル記法では、
:<math>\begin{align}
  \frac{d\phi}{dt} &= -k(D - A)\phi \\
                   &= -kL \phi
\end{align}</math>
これから、
:<math>\frac{d \phi}{d t} + kL\phi = 0</math>
が得られる。

この方程式が、行列 −''L''がラプラス演算子<math display="inline">\nabla^2</math>を置き換えている{{仮リンク|熱方程式|en|Heat equation|preserve=1}}と同じ形式であることに気付く。ゆえに、''L''は「グラフラプラシアン」と呼ばれる。

この微分方程式の解を探すため、1階の{{仮リンク|行列微分方程式|en|Matrix differential equation}}を解くための標準的な技法を適用する。すなわち、''L''の固有ベクトル<math display="inline">\mathbf{v}_i</math>（<math display="inline">L\mathbf{v}_i = \lambda_i \mathbf{v}_i</math>）の線形結合として<math display="inline">\phi</math>を書く。時間に依存する<math display="inline">\phi = \sum_i c_i \mathbf{v}_i</math>。

元の式に代入する（ここで留意すべきは、''L''が対称行列であるためにその単位ノルム固有ベクトル<math display="inline">\mathbf{v}_i</math>は直交であるという事実を用いる点である）:
:<math>\begin{align}
  \frac{d\left(\sum_i c_i \mathbf{v}_i\right)}{dt} + kL\left(\sum_i c_i \mathbf{v}_i\right) &= 0 \\
                    \sum_i \left[\frac{dc_i}{dt} \mathbf{v}_i + k c_i L \mathbf{v}_i\right] &= \\
            \sum_i \left[\frac{dc_i}{dt} \mathbf{v}_i + k c_i \lambda_i \mathbf{v}_i\right] &= \\
                                                          \frac{dc_i}{dt} + k \lambda_i c_i &= 0\\
\end{align}</math>

この解
:<math>c_i(t) = c_i(0) e^{-k \lambda_i t}</math>
である。

前掲のように、''L''の固有値<math display="inline">\lambda_i</math>は非負であり、これは微分方程式の解が（指数関数的に減衰するか一定に留まるかのいずれかのみであるため）平衡に近づくことを示している。これは、<math display="inline">\lambda_i</math>と初期条件<math display="inline">c_i(0)</math>が与えられれば、いかなる時点における解も見つけることができることも示している<ref>{{Cite book |last=Newman |first=Mark |authorlink=マーク・ニューマン |title=Networks: An Introduction |year=2010 |publisher=Oxford University Press |isbn=978-0199206650}}</ref>。全体の初期条件<math display="inline">\phi(0)</math>の観点からそれぞれの<math display="inline">i</math>に対する<math display="inline">c_i(0)</math>を探すためには、単純に<math display="inline">\phi(0)</math>を単位ノルム固有ベクトル<math display="inline">\mathbf{v}_i</math>へと射影する。
: <math>c_i(0) = \left\langle \phi(0), \mathbf{v}_i \right\rangle </math>
無向グラフの場合は、<math display="inline">L</math>が対称行列であるためこれはうまくいき、[[スペクトル定理]]によって、その固有ベクトルは全て直交する。そのため、<math display="inline">L</math>の固有ベクトルに対する射影は単純に、指数関数的に減衰し、互いに独立な一連の座標への初期条件の直交座標変換である。

=== 平衡挙動 ===
<math display="inline">\lim_{t \to \infty}\phi(t)</math>を理解するためには、残る項<math display="inline"> c_i(t) = c_i(0) e^{-k \lambda_i t}</math>は<math display="inline">\lambda_i = 0</math>のもののみであることに留意すべきである。これは
: <math>\lim_{t\to\infty} e^{-k \lambda_i t} = \left\{\begin{array}{rlr}
  0 &\text{if} &\lambda_i > 0 \\
  1 &\text{if} &\lambda_i = 0
\end{array}\right\}</math>
となるためである。

言い換えると、系の平衡状態は<math display="inline">L</math>の[[零空間|核]]によって完全に決定される。

なぜなら定義<math display="inline">\sum_{j}L_{ij} = 0</math>によれば、全てが1のベクトル<math display="inline">\mathbf{v}^1</math>は核内にある。また、グラフ中に<math display="inline">k</math>個の互いに素な[[連結成分]]が存在するならば、この全てが1のベクトルは1と0からなる<math display="inline">k</math>個の独立な<math display="inline">\lambda = 0</math>固有ベクトルの和へと分割できる。それぞれの連結成分は連結成分中の要素では1を持つ固有ベクトルと、その他の場所では0を持つ固有ベクトルと対応している。

この結果は、<math display="inline">N</math>個の頂点を持つグラフについて任意の初期条件<math display="inline">c(0)</math>では、
: <math>\lim_{t\to\infty}\phi(t) = \left\langle c(0), \mathbf{v^1} \right\rangle \mathbf{v^1}</math>
となる。上式において、
: <math>\mathbf{v^1} = \frac{1}{\sqrt{N}} [1, 1, ..., 1] </math>
である。

<math display="inline">\phi</math>の個々の要素<math display="inline">\phi_j</math>、すなわちグラフ中の個々の頂点<math display="inline">j</math>について、これを
: <math>\lim_{t\to\infty}\phi_j(t) = \frac{1}{N} \sum_{i = 1}^N c_i(0) </math>
と書き直すことができる。

言い換えると、定常状態では、<math display="inline">\phi</math>の値はグラフの個々の頂点において同じ値に収束する。この値は全ての頂点の初期値の平均である。これは熱拡散方程式の解であるため、直感的に完全に筋が通っている。グラフ中で隣接する要素は、エネルギーが互いに連結した全ての要素にわたって均等に広がるまでエネルギーを交換することが予測される。

=== グリッド上の作用素の例 ===
[[画像:Graph Laplacian Diffusion Example.gif|thumb|このGIFは、グラフラプラシアン法によって解かれたような拡散の進行を示している。グラフはグリッドにわたって構築され、グラフ中の個々のピクセルは隣接している8個のピクセルに連結している。次に、画像中の値はこれらの連結を介して隣接ピクセルへと滑らかに拡散する。この画像は、3つの点に強い値を持つ状態から始まり、この値はゆっくりと隣へ波及する。系全体は最終的に平衡に達すると同じ値に落ち着く。]]

本節では、グラフにわたって経時的に拡散する関数<math display="inline">\phi</math>の例を示す。この例中のグラフは2次元離散グリッド上に構築され、グリッド上の点は8個の隣接点と連結している。3つの初期点は正の値を持つと指定されているのに対し、グリッド中の残りの値は0である。経時的に、指数関数的減衰によってグリッド全体へとこれらの点上の値が均等に分布する。

このアニメーションを生成するために使われた完全な[[MATLAB]]のソースコードを以下に示す。ソースコードは、初期条件の指定、これらの初期条件のラプラシアン行列の固有値への射影、これらの射影された初期条件の指数関数的減衰のシミュレーションの過程を示す。

<syntaxhighlight lang=matlab>
N = 20;%The number of pixels along a dimension of the image
A = zeros(N, N);%The image
Adj = zeros(N*N, N*N);%The adjacency matrix

%Use 8 neighbors, and fill in the adjacency matrix
dx = [-1, 0, 1, -1, 1, -1, 0, 1];
dy = [-1, -1, -1, 0, 0, 1, 1, 1];
for x = 1:N
   for y = 1:N
       index = (x-1)*N + y;
       for ne = 1:length(dx)
           newx = x + dx(ne);
           newy = y + dy(ne);
           if newx > 0 && newx <= N && newy > 0 && newy <= N
               index2 = (newx-1)*N + newy;
               Adj(index, index2) = 1;
           end
       end
   end
end

%%%BELOW IS THE KEY CODE THAT COMPUTES THE SOLUTION TO THE DIFFERENTIAL
%%%EQUATION
Deg = diag(sum(Adj, 2));%Compute the degree matrix
L = Deg - Adj;%Compute the laplacian matrix in terms of the degree and adjacency matrices
[V, D] = eig(L);%Compute the eigenvalues/vectors of the laplacian matrix
D = diag(D);

%Initial condition (place a few large positive values around and
%make everything else zero)
C0 = zeros(N, N);
C0(2:5, 2:5) = 5;
C0(10:15, 10:15) = 10;
C0(2:5, 8:13) = 7;
C0 = C0(:);

C0V = V'*C0;%Transform the initial condition into the coordinate system
%of the eigenvectors
for t = 0:0.05:5
   %Loop through times and decay each initial component
   Phi = C0V.*exp(-D*t);%Exponential decay for each component
   Phi = V*Phi;%Transform from eigenvector coordinate system to original coordinate system
   Phi = reshape(Phi, N, N);
   %Display the results and write to GIF file
   imagesc(Phi);
   caxis([0, 10]);
   title(sprintf('Diffusion t = %3f', t));
   frame = getframe(1);
   im = frame2im(frame);
   [imind, cm] = rgb2ind(im, 256);
   if t == 0
      imwrite(imind, cm, 'out.gif', 'gif', 'Loopcount', inf, 'DelayTime', 0.1);
   else
      imwrite(imind, cm, 'out.gif', 'gif', 'WriteMode', 'append', 'DelayTime', 0.1);
   end
end
</syntaxhighlight>

== 負の連続的ラプラシアンに対する近似 ==
グラフラプラシアン行列は、[[有限差分法]]によって得られた（半正定値）[[ラプラス作用素|ラプラシアン]]作用素に対する近似の行列形式としてさらに見ることができる<ref>{{Citation |last1=Smola |first1=Alexander J. |last2=Kondor |first2=Risi |contribution=Kernels and regularization on graphs |doi=10.1007/978-3-540-45167-9_12 |pages=144-158 |publisher=Springer |series=Lecture Notes in Computer Science |title=Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24–27, 2003, Proceedings |volume=2777 |year=2003 |isbn=978-3-540-40720-1 |citeseerx=10.1.1.3.7020}}.</ref>。この解釈では、グラフの全ての頂点はグリッド点として扱われる; 頂点の局所連結性はグリッド点における有限差分近似{{仮リンク|ステンシル (数値解析)|en|Stencil (numerical analysis)|label=ステンシル}}を決定し、グリッドのサイズは常に全ての辺について1であり、いかなるグリッド点上にも制約はない。これは斉次な[[ノイマン境界条件]]、すなわち自由境界の場合に相当する。

== 有向多重グラフ ==
ラプラシアン行列の類似物は、有向多重グラフに対しても定義することができる<ref name="Chaiken1978">{{Cite journal |title=Matrix Tree Theorems |author1=Chaiken, S. |author2=Kleitman, D. |authorlink2=Daniel Kleitman |journal=Journal of Combinatorial Theory, Series A |volume=24 |number=3 |pages=377-381 |year=1978 |issn=0097-3165 |url=http://www.sciencedirect.com/science/article/pii/0097316578900675 |doi=10.1016/0097-3165(78)90067-5}}</ref>。この場合、ラプラシアン行列''L''は
:<math>L = D - A</math>
と定義される。上式において''D''は頂点''i''の出次数と等しい''D''{{sub|''i'',''i''}}を持つ対角行列、''A''は''i''から''j''への辺の数（ループを含む）と等しい''A''{{sub|''i'',''j''}}を持つ行列である。

== 出典 ==
{{Reflist}}

== 参考文献 ==
*{{Cite book|author=T. Sunada|chapter=Chapter 1. Analysis on combinatorial graphs. Discrete geometric analysis|title='Proceedings of Symposia in Pure Mathematics|editor=P. Exner, J. P. Keating, P. Kuchment, T. Sunada, A. Teplyaev|volume=77|year=2008|pages= 51–86|isbn= 978-0-8218-4471-7}}
*[[ベラ・バラバシ|B. Bollobás]], ''Modern Graph Theory'', Springer-Verlag (1998, corrected ed. 2013), {{ISBN2|0-387-98488-7}}, Chapters II.3 (Vector Spaces and Matrices Associated with Graphs), VIII.2 (The Adjacency Matrix and the Laplacian), IX.2 (Electrical Networks and Random Walks).

== 関連項目 ==
*[[剛性行列]]
*[[抵抗距離]]
*[[推移速度行列]]

== 外部リンク ==
*{{高校数学の美しい物語|1241|隣接行列，接続行列，ラプラシアン行列}}

{{DEFAULTSORT:らふらしあんきようれつ}}
[[Category:行列]]
[[Category:グラフ理論]]
[[Category:数学に関する記事]]
[[Category:代数的グラフ理論]]