対称正規化ラプラシアン
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/09/13 00:05 UTC 版)
「ラプラシアン行列」の記事における「対称正規化ラプラシアン」の解説
対称正規化ラプラシアン行列は L sym := D − 1 2 L D − 1 2 = I − D − 1 2 A D − 1 2 {\displaystyle L^{\text{sym}}:=D^{-{\frac {1}{2}}}LD^{-{\frac {1}{2}}}=I-D^{-{\frac {1}{2}}}AD^{-{\frac {1}{2}}}} , として定義される。 L sym {\textstyle L^{\text{sym}}} の要素は L i , j sym := { 1 if i = j and deg ( v i ) ≠ 0 − 1 deg ( v i ) deg ( v j ) if i ≠ j and v i is adjacent to v j 0 otherwise . {\displaystyle L_{i,j}^{\text{sym}}:={\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}}} によって与えられる。
※この「対称正規化ラプラシアン」の解説は、「ラプラシアン行列」の解説の一部です。
「対称正規化ラプラシアン」を含む「ラプラシアン行列」の記事については、「ラプラシアン行列」の概要を参照ください。
対称正規化ラプラシアン
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/09/13 00:05 UTC 版)
「ラプラシアン行列」の記事における「対称正規化ラプラシアン」の解説
（対称）正規化ラプラシアンは以下のように定義される。 L sym := D − 1 2 L D − 1 2 = I − D − 1 2 A D − 1 2 {\displaystyle L^{\text{sym}}:=D^{-{\frac {1}{2}}}LD^{-{\frac {1}{2}}}=I-D^{-{\frac {1}{2}}}AD^{-{\frac {1}{2}}}} 上式において、Lは（非正規化）ラプラシアン、Aは隣接行列、Dは次数行列である。次数行列Dは対角行列で正であるため、その逆数平方根 D − 1 2 {\textstyle D^{-{\frac {1}{2}}}} は単にその対角成分がDの対角成分の正の平方根の逆数である対角行列となる。対称正規化ラプラシアンは対称行列である。 L sym = S S ∗ {\textstyle L^{\text{sym}}=SS^{*}} が存在する。Sは、列が頂点によって添え字を付けられ、行がGの辺によって添え字が付けられた行列である。これらは、辺e = {u, v} に対応するそれぞれの行がuに対応する列において成分 1 d u {\textstyle {\frac {1}{\sqrt {d_{u}}}}} を、vに対応する列において成分 − 1 d v {\textstyle -{\frac {1}{\sqrt {d_{v}}}}} を、それ以外では0成分を持つことになるように索引付けされる（注: S ∗ {\textstyle S^{*}} はSの転置行列を示す）。 正規化ラプラシアンの全ての固有値は実数かつ非負である。これは以下のように見ることができる。 L sym {\textstyle L^{\text{sym}}} は対称であるため、その固有値は実数である。これらの固有値は全て非負である。固有値λを持つ L sym {\textstyle L^{\text{sym}}} の固有ベクトル g {\textstyle g} を考え、 g = D 1 2 f {\textstyle g=D^{\frac {1}{2}}f} を仮定する（gおよびfを頂点v上の実関数と見なすことができる）。すると、 λ = ⟨ g , L sym g ⟩ ⟨ g , g ⟩ = ⟨ g , D − 1 2 L D − 1 2 g ⟩ ⟨ g , g ⟩ = ⟨ f , L f ⟩ ⟨ D 1 2 f , D 1 2 f ⟩ = ∑ u ∼ v ( f ( u ) − f ( v ) ) 2 ∑ v f ( v ) 2 d v ≥ 0 , {\displaystyle \lambda \ =\ {\frac {\langle g,L^{\text{sym}}g\rangle }{\langle g,g\rangle }}\ =\ {\frac {\left\langle g,D^{-{\frac {1}{2}}}LD^{-{\frac {1}{2}}}g\right\rangle }{\langle g,g\rangle }}\ =\ {\frac {\langle f,Lf\rangle }{\left\langle D^{\frac {1}{2}}f,D^{\frac {1}{2}}f\right\rangle }}\ =\ {\frac {\sum _{u\sim v}(f(u)-f(v))^{2}}{\sum _{v}f(v)^{2}d_{v}}}\ \geq \ 0,} となる。ここでは内積 ⟨ f , g ⟩ = ∑ v f ( v ) g ( v ) {\textstyle \langle f,g\rangle =\sum _{v}f(v)g(v)} （全ての頂点vにわたる和）を用い、 ∑ u ∼ v {\textstyle \sum _{u\sim v}} は隣接頂点 {u,v} の全ての非順序対（英語版）にわたる和を示す。量 ∑ u , v ( f ( u ) − f ( v ) ) 2 {\textstyle \sum _{u,v}(f(u)-f(v))^{2}} はfの「ディリクレ和」と呼ばれるが、式 ⟨ g , L sym g ⟩ ⟨ g , g ⟩ {\textstyle {\frac {\left\langle g,L^{\text{sym}}g\right\rangle }{\langle g,g\rangle }}} はgのレイリー商と呼ばれる。 1をそれぞれの頂点上に値1を想定する関数とする。すると、 D 1 2 1 {\textstyle D^{\frac {1}{2}}1} は固有値0を持つ L sym {\textstyle L^{\text{sym}}} の固有関数である。 実際、正規化対称ラプラシアンの固有値は0 = μ0 ≤ … ≤ μn−1 ≤ 2を満たす。これらの固有値（正規化ラプラシアンのスペクトルと呼ばれる）は、一般グラフに対するその他のグラフ不変量とよく関連する。
※この「対称正規化ラプラシアン」の解説は、「ラプラシアン行列」の解説の一部です。
「対称正規化ラプラシアン」を含む「ラプラシアン行列」の記事については、「ラプラシアン行列」の概要を参照ください。
- 対称正規化ラプラシアンのページへのリンク
