라플라시안 행렬

그래프 이론의 수학적 분야에서, 그래프 라플라시안, 입장 행렬, Kirchhoff 행렬 또는 이산 라플라시안이라고도 불리는 라플라시안 행렬은 그래프를 행렬로 표현한 것이다. 피에르 시몬 라플라스(Pierre-Simon Laplace)의 이름을 따서 명명된 그래프 라플라스 행렬은 유한 차이 방법으로 얻은 음의 연속성 라플라스 라플라스 연산자에 근접한 그래프에서 음의 이산 라플라스 연산자의 행렬 형태로 볼 수 있다.

라플라크 행렬은 그래프의 많은 유용한 특성을 찾는 데 사용될 수 있다. 키르흐호프의 정리와 함께 주어진 그래프의 스패닝 트리 수를 계산하는 데 사용할 수 있다. 그래프의 가장 빠른 컷은 치거의 불평등에 의해 라플라크의 두 번째로 작은 고유값을 통해 근사하게 추정할 수 있다. 그것은 또한 다양한 기계 학습 어플리케이션에 유용할 수 있는 저차원의 임베딩 시공에도 사용될 수 있다.

단순 그래프 정의

라플라시안 행렬

$n{\displaystyle }$ ${\displaystyle n}$ $꼭지점$ v ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle \dots ,}$ ${\displaystyle {}_{}}$ ${\displaystyle n_{}}${\$displaystyle v_{1},\ldots, v_$${n$$}}$을(를) 포함한 간단한 그래프 $G{\displaystyle }$ ${\displaystyle G}$을$(를)$ 지정하면 해당 라플라시안 행렬 $L_{}$ ${\times }_{}$ n ${\$로 정의된다^[1]$.$

$L_{i,j:={\package}\case}\case(v_{i}})\\mbox{if}\i=j\-1&{\mbox{if}\i\neq j\{\nebox{and}\v_{i}}{\mbox{}{}}}}}}}}}에 인접해 있다.$

또는 행렬에 따라 동등하게

$L=D-A,}$

여기서 D는 도 행렬이고 A는 그래프의 인접 행렬이다. $G$ ${\textstyle G}$은(는) 단순한 그래프이므로$$ $A$ ${\textstyle A}$은(는) 1초 또는 0초만$$ 포함하고 대각선 요소는 모두 0초입니다.

여기에 라벨이 부착되지 않은 비방향 그래프와 그 라플라시안 행렬의 간단한 예가 있다.

라벨 그래프	도 행렬	인접 행렬	라플라시안 행렬
	${\textstyle \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)}$	${\textstyle \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)}$	${\textstyle \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)}$

인접 행렬과 라플라시안 행렬이 모두 대칭이며, 라플라시안 행렬의 행과 열 합이 모두 0이라는 비방향 그래프를 관찰한다.

지시된 그래프의 경우, 다음 예시와 같이 응용 프로그램에 따라 외설적 또는 외도를 사용할 수 있다.

인접 행렬	아웃도 행렬	아웃도어 라플라시안	인 도 행렬	인 디도 라플라시안
${\textstyle \left \puted\put{array}{rrrr}0&1\\0&0&1\\1&0\\end{array}\오른쪽)}$	${\textstyle \left({\puted{array}{rrrr}2&0&0\\0&0\\0&0&1\\end{array}\오른쪽)}$	${\textstyle \left({\puted{array}{rrrr}2&-1&-1\\0&-1\\\1&0&1\\end{array}\오른쪽)}$	${\textstyle \left \pretted\puted{array}{rrrr}1&0&0\\0&1&0\\0&0&2\\\end{array}\오른쪽)}$	${\textstyle \left({\puted{array}{rrrr}-1&-1&-1\\0&1\\\1&0&2\\end{array}\오른쪽)}$

지시된 그래프에서 인접 행렬과 라플라시안 행렬은 모두 비대칭이다. 그것의 라플라크 행렬에서, 외설적 또는 외설적 학위가 사용되었는지 여부에 따라 칼럼 합 또는 행 합은 0이다.

입사 행렬을 통한 대칭 라플라시안

v $\times$ $e$ $textstyle$v$\times$e$}$발생$$ 매트릭스 B(${정점}_{}$_ve v$$i {\$textstyle$v_${i$} ${및}_{}$ $v$ j$${\$textstyle v_${j$\}$ , i > j)는 다음과 같이 정의된다.

${\displaystyle B_{ve}=\왼쪽\{\\begin{array}1,&#{\text{{{}if }v=v_{i}\-1,&\text{{v=v_{j}\0,&#text{otherwise}.\end{array}\오른쪽.}$

이 정의의 가장자리는 기술적으로 지시되어 있더라도 그 방향은 임의적일 수 있으며, 여전히 다음과 같이 정의된 동일한 대칭 Laplacian $v$ $\times$ $v$ $textstyle$v$\times$ v \time v$}$ 매트릭스 L이 생성된다.

${\displaystyle L=BB^{\textsf{T}}$

여기서 $B{}^{}$ $T^{}$ ${\$ B$^{\textsf {T}$은(는) B의 전치 행렬이다.

비방향 그래프	발생 행렬	라플라시안 행렬
	${\textstyle \left({\cHB{array}{rrrr}1&1&1&1&0&0&0\\\0&0&1&1\\0&1&1\\end{array}\right}}}}$	${\textstyle \left \cHB\{array}{rrr}3&-1&-1&-1&1&0&0\\\-1&0&0&0\\\\1&0&1&1&1&2\\end{array}\rig}\right)}$

대체 제품 $B{\displaystyle {}^{}}$ ${\displaystyle T^{}}$ ${\displaystyle B^{}}$ ${\displaystyle B^{\textsf{T}B}$는 $일반적$으로 사용되는 원래 꼭지점 기반 라플라시안 매트릭스 L과 반대로 소위 e $\times$ $e$ $textstyle$e$\times e$} 에지 기반$$ 라플라시안을 정의한다.

지시된 그래프에 대한 대칭 라플라시안

지시된 그래프의 라플라크 행렬은 정의상 일반적으로 비대칭인 반면, 전통적인 스펙트럼 클러스터링은 주로 대칭 인접성과 라플라크 행렬이 있는 비방향 그래프를 위해 개발된다. 대칭이 필요한 기법을 적용하기 위한 사소한 접근법은 원래 지시된 그래프를 비방향 그래프로 바꾸고 후자를 위한 라플라크 행렬을 구축하는 것이다.

행렬 표기법에서, 방향하지 않은 그래프의 인접 행렬은 예를 들어 원래 지시된 그래프의 인접$$ 행렬 $A{\displaystyle }$ ${\displaystyle$ A$}$의 부울 합으로 정의될 수 있으며, 그 행렬은 ${\displaystyle A^{}}$ $T{\displaystyle {}^{}}$ ${\$$T{\displaystyle }$$\}\},$$여기$서 A {\$displaystyle$ A}의$$0과 1개의 항목이 다음 예와 같이 숫자가 아닌 논리적 값으로 처리된다$$.

인접 행렬	대칭 인접	대칭 래플라크 행렬
${\textstyle \left({\put{array}{ccc}0&1&1\0&0&1\\1&0\\\end{array}\오른쪽)}$	${\textstyle \left({\put{array}{ccc}0&1&1\\1&01\\1&0\\\end{array}\오른쪽)}$	${\textstyle \left({\cHB{array}{ccc}-2&-1&-1\\-1&2\\1&1&1&2\\end{array}\오른쪽)}$

라플라시안 행렬 정규화

무거운 노드라고도 불리는 큰 정도의 정점은 매트릭스 속성을 지배하는 라플라시안 매트릭스의 큰 대각선 진입이다. 정규화는 라플라크 행렬의 입력을 정점도로 나누어서 다른 정점의 입점과 더 동등하게 만드는 것을 목표로 한다. 0으로 나누어지는 것을 피하기 위해 0도로 분리된 정점은 정규화 과정에서 제외한다.

대칭적으로 정규화된 라플라시안

대칭적으로 정규화된 라플라시안 행렬은 다음과 같이 정의된다.^[1]

${\$$=D^{-{\frac {1}{2}}:}$$LD^{-{\frac{1}{2}}=I-D^{-{\frac{1}{2}}:}$$AD^{-{\frac{1}{2$

$L$ ${\text{sym}}^{}$ ${\$ L$^{\text{sym}}$의 요소는

${\displaystyle L_{i,j}^{\text{sym}}:={\cHB{case}1&{\mbox{}{}i=j{\mbox{{} 및 }}\\neq 0\\\-{\frac {1}{\sqrt{\ch(v_{i}})\cHB(v_{j})}}}}&{\mbox{{}}{{}}}{{{neq j{\mbox{ 및 }}{{v_{i}{\mbox{}}{}}}}에 인접해 있다.\end{case}}}$

대칭 정규화된 라플라시안 행렬은 인접 행렬이 대칭인 경우에만 대칭이다.

인접 행렬	도 행렬	정규화된 라플라시안
${\textstyle \left \puted\put{array}{rrrr}0&1&0\\1&0\\0&0\\end{array}\오른쪽)}$	${\textstyle \left \pretted\cHB{array}{rrrr}1&0&0\\0&0&0\\0&1\\\end{array}\오른쪽)}$	${\textstyle \left\ft{array}{rrrr}-1-{\sqrt{1/2}}&\\-{\sqrt{1/2}}&-{1/2}}-\0&-{\sqrt{1/2}}-\1}\end{array}}\rig}}오른쪽)}$

지시된 그래프의 비대칭 인접 행렬의 경우 정규화에 외향 및 외향 중 하나를 사용할 수 있다.

인접 행렬	아웃도 행렬	아웃도 표준화된 라플라시안	인 도 행렬	인 도 표준화된 라플라시안
${\textstyle \left \puted\put{array}{rrrr}0&1\\0&0&1\\1&0\\end{array}\오른쪽)}$	${\textstyle \left({\puted{array}{rrrr}2&0&0\\0&0\\0&0&1\\end{array}\오른쪽)}$	${\textstyle \left\ft{array}{rrrrr}-{\sqrt{1/2}}\{1/2}}\0&1-1\\\\\\sqrt{1/2}}&1&1\\nd{array}\오른쪽)}$	${\textstyle \left \pretted\puted{array}{rrrr}1&0&0\\0&1&0\\0&0&2\\\end{array}\오른쪽)}$	${\textstyle \left \preft\{array}{rrrr}-1&-{\sqrt{1/2}}\\0&-{\sqrt{1/2}}\-{\sqrt{1/2}&0&1\\\end{array}}\right}}}}}}}$

왼쪽(랜덤 워크) 및 오른쪽 정규화된 라플라시안

왼쪽(랜덤-워크) 정규화된 라플라시안 매트릭스는 다음과 같이 정의된다.

${\displaystyle L^{\text{rw}:=D^{-1}L=I-D^{-1}A}$

$L$ ${\text{rw}}^{}$ ${\$의 요소는 다음과 같다.

${\displaystyle L_{i,j}^{\text{rw}}:={\begin{case}1&{\mbox{{}}{}}}{}}\deg(v_{i})\neq 0\-{\frac(v_{i}){\deg}}}}&{\mbox{{}}}{{{neq j{\mbox{} 및 }}{{v_{i}{\mbox{}}{}}}}}}에 인접해 있다.\end{case}}}$

마찬가지로, 오른쪽 정규화된 라플라시안 행렬은 다음과 같이 정의된다.

${\displaystyle L}$ ${\displaystyle {}^{}}$- ${\displaystyle 1^{}}$= ${\displaystyle I}$- ${\displaystyle {}^{}}$ ${\displaystyle {\mathrm{D}}^{}}$- 1 ${\$

인접 행렬이 대칭이면 왼쪽 또는 오른쪽 정규화된 라플라시안 행렬이 대칭이 아니며, 모든 분리된 정점의 사소한 경우를 제외한다. 예를 들어,

인접 행렬	도 행렬	왼쪽 표준화된 라플라시안	오른쪽 정규화된 라플라시안
${\textstyle \left \puted\put{array}{rrrr}0&1&0\\1&0\\0&0\\end{array}\오른쪽)}$	${\textstyle \left \pretted\cHB{array}{rrrr}1&0&0\\0&0&0\\0&1\\\end{array}\오른쪽)}$	${\textstyle \left({\puted{array}{rrrr}-1&#1&#1&#1&#1&#1\\end{array}\right)}$	${\textstyle \left({\puted{array}{rrrr}1&-1/2&0\-1&1\\0&1/2&1\\end{array}\right)}$

또한 이 예는 왼쪽 정규화된 라플라시안 $L{\displaystyle {}^{}}$ ${\displaystyle {\text{rw}}^{}}$ ${\displaystyle :=}$ ${\displaystyle {}^{}}$- ${\displaystyle {}^{}}$ L${\displaystyle }$= ${\displaystyle I}$- ${\displaystyle {}^{}}$- ${\displaystyle {}^{}}$ ${\displaystyle {\mathrm{A}}^{}}$ ${\displaystyle$ L$^{\text{rw}}:$$=D^{-1}L=I-D^{-1}A}$는 $D{\displaystyle {}^{}}$- ${\displaystyle 1^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle$ D$^{-1}A}$이(가) 랜덤워크의 우측 확률적 매트릭스이므로 각 행이 0에 합치는데$$, 이는 대체 이름 무작위워크 정규화된 라플라시안을 설명한다. $덜{\displaystyle }$ 흔하게 사용되는 오른쪽 정규화된 라플라시안 ${\displaystyle {}^{}}$ D${\displaystyle {}^{}}$-${\displaystyle {}^{}{1}^{}}$ =${\displaystyle I}$ - ${\displaystyle {\mathrm{A}}^{}}$- D -$$1 {\$displaystyle$ LD$^{-1$}=$I-AD^{-1$}:{-${\displaystyle {}^{}}$$}$ A${\displaystyle {}^{}}$- ${\displaystyle 1^{}}$ ${\$이 왼쪽 확률형이기 때문에 각 열$$ 합계는 0이다.

지시된 그래프의 비대칭 인접 행렬의 경우 정규화를 위해 외향적 또는 외향적 행렬을 선택해야 한다.

인접 행렬	아웃도 행렬	Out-Degree 왼쪽 정규화	인 도 행렬	인 디도 우 정규화 라플라시안
${\textstyle \left \puted\put{array}{rrrr}0&1\\0&0&1\\1&0\\end{array}\오른쪽)}$	${\textstyle \left({\puted{array}{rrrr}2&0&0\\0&0\\0&0&1\\end{array}\오른쪽)}$	${\textstyle \left \puted\puted{array}{rrrrr)1&-1/2&-1/2\\0&1\\1&0&1\\\end{array}\right)}$	${\textstyle \left \pretted\puted{array}{rrrr}1&0&0\\0&1&0\\0&0&2\\\end{array}\오른쪽)}$	${\textstyle \left({\puted{array}{rrrr}-1&-1&-1/2\\0&1/2\\1&0&1\\end{array}\right)$

The left out-degree normalized Laplacian with row-sums all 0 relates to right stochastic ${\displaystyle D_{out}^{-1}A}$ , while the right in-degree normalized Laplacian with column-sums all 0 contains left stochastic ${\displaystyle AD_{in}^{-1}}$.

가중 에지가 있는 그래프 정의

가중 에지가 있는 응용 프로그램 그래프에서 공통적인 것은 엔트리의 값이 숫자이고 더 이상 0과 1로 제한되지 않는 인접 행렬에 의해 쉽게 정의된다. 스펙트럼 클러스터링과 그래프 기반 신호 처리에서, 그래프 정점이 데이터 점을 나타내는 경우, 에지 가중치를 계산할 수 있다. 예를 들어, 데이터 지점 쌍 사이의 거리에 반비례하여 모든 가중치가 음수가 되고 더 큰 값이 더 유사한 데이터 지점 쌍에 비공식적으로 대응된다. 데이터 지점 간의 상관 관계와 반상관성을 사용하면 자연히 양의 가중치와 음의 가중치를 모두 얻을 수 있다. 단순 그래프에 대한 대부분의 정의는 음이 아닌 표준 가중치까지 사소한 것으로 확장되는 반면, 음의 가중치는 특히 정상화에 더 많은 주의를 요한다.

라플라시안 행렬

라플라크 행렬은 다음과 같이 정의된다.

$L=D-A,}$

여기서 D는 도 행렬이고 A는 그래프의 인접 행렬이다.

지시된 그래프의 경우, 다음 예시와 같이 응용 프로그램에 따라 외설적 또는 외도를 사용할 수 있다.

인접 행렬	인 도 행렬	인 디도 라플라시안	아웃도 행렬	아웃도어 라플라시안
${\textstyle \left \pretted\{array}{rrrr}0&1&2\\3&05\\\6&7&0\\\end{array}\오른쪽)}$	${\textstyle \left({\puted{array}{rrrr}9&0&0\\0&0\\0&07\\end{array}\오른쪽)}$	${\textstyle \left \just\{array}{rrrr}9&-1&-2\\-3&8&-5\\-6&-7\\end{array}\오른쪽)}$	${\textstyle \left({\puted{array}{rrr}3&0&0\\0&0&0\\0&13\\end{array}\오른쪽)}$	${\textstyle \left \cHB\{array}{rrr}3&-1&-2\\-3&8&-5\\-6&-7&13\\end{array}\오른쪽)}$

인접 행렬의 주 대각선에 0이 아닌 항목으로 자신을 나타내는 그래프 자체 루프는 허용되지만 그래프 라플라시안 값에 영향을 미치지 않는다.

입사 행렬을 통한 대칭 라플라시안

가중 에지가 있는 그래프의 경우 가중치 발생 행렬 B를 정의하고 이를 사용하여${\displaystyle }L{\displaystyle }$ = ${\displaystyle {}^{}}$ ${\displaystyle T^{}}${\$displaystyle$ L$=BB^{\textsf{$T}}에 해당하는 대칭 Laplacian을 구성할 수 있다$.$ 여기서 설명하는 대체 클리너 접근법은 연결에서 가중치를 분리하는 것이다. 발생 행렬을 정규용으로 계속 사용 그래프를 그리고 가중치 값을 포함하는 행렬을 소개한다.

따라서, 무중력 $v$ $\times$ $e$ $textstyle$v$\time$e}발생$$매트릭스 B(정점_ve v × ${\$ 및 v $j_{}$ ${\$ , i > j)의 정의를 재사용한다.

${\displaystyle B_{ve}=\왼쪽\{\\begin{array}1,&#{\text{{{}if }v=v_{i}\-1,&\text{{v=v_{j}\0,&#text{otherwise}.\end{array}\오른쪽.}$

이제 에지 가중치를 포함하는 대각선 $e$ $\times$ $e$ $textstyle$e$\time e$} 행렬$$ W도 정의한다. B의 정의에서 가장자리가 기술적으로 지시되어 있더라도 그 방향은 임의적일 수 있으며, 여전히 다음과 같이 정의된 동일한 대칭 Laplacian $v$ $\times$ $v$ $textstyle$v$\times v$} 행렬 L이 생성된다.

$L=B 표시WB^{\textsf{T}}$

여기서 $B{}^{}$ $T^{}$ ${\$ B$^{\textsf {T}$은(는) B의 전치 행렬이다.

다음 예에서는 구성 방법을 예시하여 모든 에지 $e_{}$ ${\$에 가중치 값 $\mathrm{i}$가 할당되며$$, $여기$서$$i$$=$1$,$\mathrm{2,}$3,$$4. {\$textstyle i=1$,2,3,$4}$

비방향 그래프	발생 행렬	에지 웨이트	라플라시안 행렬
	${\textstyle \left({\cHB{array}{rrrr}1&1&1&1&0&0&0\\\0&0&1&1\\0&1&1\\end{array}\right}}}}$	${\textstyle \left({\puted{array}{rrrr}1&0&0&0&0\\0&0&0&0\\0&0&04\\\end{array}\right)}$	${\textstyle \left \cHB\{array}{rrr}6&-1&-2&-3\\-1&1&0&0&0\\\-2&0&6&4\\-3&0&4&#4&#\end{array}\rig}\right)}$

지시된 그래프에 대한 대칭 라플라시안

단순 그래프의 경우처럼 방향 가중 그래프의 라플라시안 행렬은 정의상 일반적으로 비대칭이다. 대칭은 라플라시안을 구성하기 전에 원래 지시된 그래프를 비방향 그래프로 먼저 변환하여 시행할 수 있다. 비방향 그래프의 인접 행렬은 예를 들어 원래 지시된 그래프의 인접$$ 행렬 $A{\displaystyle }$ ${\displaystyle A}$과 그 행렬이 ${\displaystyle A^{}}$ T ${\$$T}}$은(는) 다음 예와 같다$$.

인접 행렬	대칭 인접 행렬	대칭 래플라크 행렬
${\textstyle \left \puted\put{array}{rrrr}0&1\\0&0&1\\1&0\\end{array}\오른쪽)}$	${\textstyle \left \puted\puted{array}{rrrr}0&1&2\\1&0\\2&1&0\\end{array}\오른쪽)}$	${\textstyle \left({\puted{array}{rrrr}3&-1&-2\\-1&2&-1\\\-2&1&3\\end{array}\right)$

$A{\displaystyle }$ ${\displaystyle A}$의 0 항목과 1개의 항목이 단순한$$ 그래프, 값과 같이 논리적이지 않고 수치로 처리되어 결과의 차이를 설명하는 경우 - 단순 그래프의 경우 대칭화된 인접 행렬이 숫자 값이 아닌 논리합(예: 논리합)만을 갖는 단순해야 한다. 1 v 1 = 1인 반면 숫자 합은 1 + 1 = 2이다.

대칭 라플라시안 행렬은 다음 예와 같이 외설과 외도를 사용하여 두 라플라시안으로부터 계산할 수 있다.

인접 행렬	아웃도 행렬	아웃도어 라플라시안	인 도 행렬	인 디도 라플라시안
${\textstyle \left \puted\put{array}{rrrr}0&1\\0&0&1\\1&0\\end{array}\오른쪽)}$	${\textstyle \left({\puted{array}{rrrr}2&0&0\\0&0\\0&0&1\\end{array}\오른쪽)}$	${\textstyle \left({\puted{array}{rrrr}2&-1&-1\\0&-1\\\1&0&1\\end{array}\오른쪽)}$	${\textstyle \left \pretted\puted{array}{rrrr}1&0&0\\0&1&0\\0&0&2\\\end{array}\오른쪽)}$	${\textstyle \left({\puted{array}{rrrr}-1&-1&-1\\0&1\\\1&0&2\\end{array}\오른쪽)}$

도외 라플라시안과 도외 라플라시안의 합은 대칭 라플라시안 행렬과 같다.

라플라시안 행렬 정규화

표준화의 역할은 단순 그래프와 마찬가지로 라플라크 행렬의 대각선 입력을 모든 단위가 되도록 하고, 그에 따라 대각선 입력을 스케일 아웃하는 것이다. 인접 행렬의 주 대각선에 0이 아닌 그래프 자체 루프는 그래프 라플라시안 값에 영향을 미치지 않지만 정규화 인자의 계산을 위해 카운트가 필요할 수 있다.

대칭적으로 정규화된 라플라시안

대칭적으로 정규화된 라플라시안은 다음과 같이 정의된다.

${\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${}^{}$- ${\frac{1}{}}^{}$ ${2\frac{\mathrm{}}{}}^{}$ ${\$ D$^{-{\frac{1}{2}}:$ 대각선 입력이 D의 대각선 입력 제곱근의 왕복인 대각선 행렬일 뿐이다$$. 모든 에지 가중치가 음수가 아닌 경우 모든 도 값도 음수가 아니므로 모든 도 값은 고유한 양의 제곱근을 가진다. 0으로 나누어지는 것을 피하기 위해 다음 예와 같이 0도의 정점을 정규화 과정에서 제외한다.

인접 행렬	인 도 행렬	인 도 표준화된 라플라시안	아웃도 행렬	아웃도 표준화된 라플라시안
${\textstyle \left({\puted{array}{rrrr}0&1&0\\4&0\\0&0\\end{array}\오른쪽)}$	${\textstyle \left \puted\put{array}{rrrr}1&0&0\\0&0\\0&0\\end{array}\오른쪽)}$	${\textstyle \left \pretted\{array}{rrrr}-1/2&0\\2&0\\0&0\\end{array}\right}}}$	${\textstyle \left({\puted{array}{rrrr}4&0&0\\0&0\\0&0\\end{array}\오른쪽)}$	${\textstyle \left \pretted\{array}{rrrr}-1/2&0\\2&0\\0&0\\end{array}\right}}}$

대칭 정규화된 라플라시안은 인접 행렬 A가 대칭이고 D의 대각선 입력이 음이 아닌 경우에만 대칭 행렬이며, 이 경우 대칭 정규화된 라플라시안이라는 용어를 사용할 수 있다.

대칭 정규화된 라플라시안 행렬도 다음과 같이 쓸 수 있다.

${\displaystyle L^{\text{sym}:=D^{-{\frac {1}{2}}:}LD^{-{\frac{1}{2}}=D^{-{\frac {1}{2}}BWB^{\textsf{T}D^{-{\frac {1}{2}}=SS^{T}}}}$

무중력 $v$ $\times$ e $textstyle$v$\time e$}발생 매트릭스 B 및 에지 가중치를 포함하는 대각선 $e$ $\times$ $e$ $textstyle$ e $\times e$$$$}$매트릭스$$ W를 사용하고 새$$ $v$ $\times$ $e$ $textstyle$v$\time$e} 가중발생 $매트릭스$ S$$= ${D\mathrm{}}^{}$ -${}^{}$/ ${2\mathrm{}}^{}$ B $1^{}$을 정의${\$$BW^{{1}/{2}}}$ whose rows are indexed by the vertices and whose columns are indexed by the edges of G such that each column corresponding to an edge e = {u, v} has an entry ${\textstyle {\frac {1}{\sqrt {d_{u}}}}}$ in the row corresponding to u, an entry ${\textstyle -{\frac {1}{\sqrt {d_{v}}}}}$ in the 행은 v에 해당하며 다른 곳에 0개의 항목이 있다.

무작위 걷기 정규화 라플라시안

무작위 걷기 정규화 라플라시안은 다음과 같이 정의된다.

${\displaystyle L^{\text{rw}:=D^{-1}L}$

여기서 D는 도 행렬이다. 도 행렬 D는 대각선이기 때문에 역 $D{}^{}$- $1^{}$ ${\$는 단순히 대각선 행렬로 정의되며$$, D의 해당 대각선 항목의 왕복인 대각선 항목이 있다. 고립된 꼭지점(도가 0인 정점)의 경우 공통적으로 해당 요소 L${}_{}^{}i{}_{}^{}$ , $i_{}^{}$ ${\text{rw}}_{}^{}$ ${\$을(를) 0으로 설정하는$$ 것이 일반적이다. $L$ ${\text{rw}}^{}$ ${\$의 매트릭스 요소는 다음과 같다.

${\displaystyle L_{i,j}^{\text{rw}}:={\begin{case}1&{\mbox{if}\i=j\{\mbox{and}\\\deg(v_{i})\neq 0\-{\\frac{\deg(v_{i})}}}}}}}}}&{\mbox{if}\i\neq j\{\neq j\{and}\v_{i}{\mbox{}{}}{}}}}}}에 인접해 있다.\end{case}}}$

무작위 걷기 정규화된 라플라시안의 이름은 이 $매트릭스$가 L ${\text{rw}}^{}$ ${}^{}I$ - $P${\$textstyle$ L$^{\rw}=I-P}$라는 사실에서 따온 것이다$.$ $여기$서$$P =${}^{}$ - ${}^{}$ A$${\$textstyle P=D^{-1A}$는 단순히 음이 아닌 가중치를 가정하여 그래프 상의 랜덤 워커의 전환 매트릭스일 뿐이다$$. 예를 들어 $e{}_{}$ $i_{}$ ${\$가 i번째 표준 기준 벡터를 나타내도록 한다$$. Then ${\textstyle x=e_{i}P}$ is a probability vector representing the distribution of a random walker's locations after taking a single step from vertex ${\textstyle i}$; i.e., ${\textstyle x_{j}=\mathbb {P} \left(v_{i}\to v_{j}\right)}$. More generally, if the vector $x$${\textstyle x}$은(는) 그래프의 꼭지점에 있는 임의의 보행자 위치에 대한 확률 분포로, $그러면{}^{}$ x${}^{}=$ = $x$ $P^{}$ t$${\$textstyle$ x$'=xP^{t}}$는 t$${\$textstyle$ t$}단계$ 이후$$ 보행자의 확률 분포다.

음체중량

음의 가중치는 몇 가지 도전 과제를 나타낸다.

• 음의 가중치가 있으면 자연스럽게 비절연 정점에 대한 행 및/또는 열 합이 0이 될 수 있다. 대각선 입력이 분리된 꼭지점처럼 0인 반면, 양수 가중치의 큰 행 합과 음수 가중치의 같은 음수 행 합이 0인 정점은 무거운 노드로 간주될 수 있다.
• 음의 가중치는 또한 음의 행 및/또는 열 합계를 줄 수 있으므로, 비정규화된 라플라시안 행렬의 해당 대각선 입력이 음이 되고 대칭 정규화에 필요한 양의 제곱근은 존재하지 않게 된다.
• 정규화를 위해 행 및/또는 열섬의 절대값을 취하도록 주장할 수 있으며, 따라서 가능한 값 -1을 정규화된 라플라시안 행렬의 주 대각선의 합법적인 단위 항목으로 취급한다.

특성.

고유값 $\lambda {}_{}$ ${0\mathrm{}}_{}$ ${}_{}$ ${1\mathrm{}}_{}$ $\le$ ⋯ ⋯ n n n $n_{}$ n${}_{}$- $1_{}$ ${\$1}\$lq \cdots \lambda \{n-1$

• L은 대칭이다.
• L은 양의 smidefinite($\mathrm{모든}$ $i$ ${\textstyle$ $\lambda _{i}\geq$ $0})$이다.$$ 이는 발생 행렬 섹션(아래)에서 확인된다. 이것은 라플라시안이 대칭적이고 대각선적으로 우세하다는 사실에서도 알 수 있다.
• L은 M-매트릭스(대각선 외부 입력은 양성이지만 고유값의 실제 부분은 음성이 아님)이다.
• L의 모든 행 합과 열 합은 0이다. 실제로 이 합계에서 꼭지점의 정도는 각 이웃에 대한 "-1"로 요약된다.
• In consequence, ${\textstyle \lambda _{0}=0}$, because the vector ${\textstyle \mathbf {v} _{0}=(1,1,\dots ,1)}$ satisfies ${\textstyle L\mathbf {v} _{0}=\mathbf {0} .}$ This also implies that the Laplacian matrix is singular.
• 그래프에서 연결된 성분의 수는 라플라시안 nullspace와 0 고유값의 대수적 다중의 치수다.
• L의 가장 작은 0이 아닌 고유값을 스펙트럼 갭이라고 한다.
• L의 두 번째로 작은 고유값(또는 0일 수 있음)은 G의 대수적 연결성(또는 피들러 값)이며 그래프의 가장 빠른 컷에 가깝다.
• 라플라시안(Laplacian)은 함수 $f$: $V\mathbb{}$→ R ${\$$V\to \mathb {R}$$},$ $여기$서 V ${\textstyle V}$은(는) G의 꼭지점 집합이고 $n$= $V$ $textstyle n=$ V $}$입니다$.$
• G가 k-규칙일 때 정규화된 라플라시안은 $L\mathcal{}$ = $1\frac{\mathrm{}}{}k$ L$$= I$$- $1$ $k$ $\frac{A}{}$ ${\textstyle {\mathcal{L}={\tfrac{1}{k}L=I-{\tfrac{1}{k}A}$이다$.$ 여기서 A는 인접 행렬이고 나는 정체성 행렬이다.
• 다중 연결된 구성요소가 있는 그래프의 경우, L은 블록 대각 행렬이며, 여기서 각 블록은 정점 순서를 변경한 후(즉, L은 블록 대각 행렬과 유사하게 순열됨) 각 구성요소에 대한 각 Laplacian 행렬이다.
• Laplacian 행렬 L의 추적은 $\mathrm{2m}${\$textstyle$ 2m$}$과 동일하며$,$ 여기서 m {\$textstyle$ m$}$은(는) 해당 그래프의 가장자리 수입니다.
• 이제 단위 표준 고유 벡터 $v{\mathbf{}}_{}$ ${}_{}$ ${\\$ 및$$ 해당하는 고유값 $\lambda {}_{}$ $i_{}$ ${\$을(를) $포함$한 L$${\$textstyle$L$\}$의 eigende 구성을 고려하십시오$.$

${\displaystyle {\begin{aligned}\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{aigned}}$

$\lambda {}_{}$ $i_{}$ ${\$는 그 $자체$로 ${}_{}$ M $v$ {\$textstyle$M\mathbf {$v} _{$i}{i}}}의 내생물로 쓸 수 있으므로$$ $shows$ i ${}_{}$ i$$≥ $0$ {\$textyle$ $\lambda _{i}\geq$0}}}}}}}의 고유값이 모두 음성이라는$$ 것을 알 수 있다$.$

• 정규화된 대칭 라플라시안의 모든 고유값은 0 = μ₀ μ … μ μ_n−1 μ μ μ 2를 만족한다. 이러한 고유값(정규화된 라플라시안의 스펙트럼으로 알려져 있음)은 일반 그래프의 다른 그래프 불변제와 잘 관련된다.^[1]

* 확인할 수 있다 

${\$$D^{\frac{1}{2$

i.e., ${\textstyle L^{\text{rw}}}$ is similar to the normalized Laplacian ${\textstyle L^{\text{sym}}}$. For this reason, even if ${\textstyle L^{\text{rw}}}$ is in general not symmetric, it has real eigenvalues — exactly the same as the eigenvalues of the normalized symmetric Laplacian $L^{\text{sym}}$${\textstyle$ L$^{\text{sym$

연속 라플라스틱에 근접한 이산 라플라스 연산자로 해석

그래프 라플라시안 행렬은 유한 차이 방법으로 얻은 음의 연속성 라플라시안 라플라스 연산자에 근접한 그래프에서 음의 이산 라플라스 연산자의 행렬 형태로 더 자세히 볼 수 있다. (이연산 포아송 방정식 참조)^[2] 이 해석에서, 모든 그래프 꼭지점은 격자점으로 취급된다; 정점의 국소 연결은 이 격자점에서 유한 차이 근사 스텐실을 결정하며, 격자 크기는 항상 모든 에지에 대해 하나이며, 균일한 Neumann 경계 콘디티의 경우에 해당하는 격자점에 제약이 없다.즉, 자유 경계선 상에. 그러한 해석은 예를 들어, 정점과 가장자리가 무한히 많은 그래프의 경우 라플라크 행렬을 일반화하여 무한한 크기의 라플라크 행렬로 이어질 수 있다.

라플라시안 매트릭스의 일반화 및 확장

일반화 라플라시안

일반화된 Laplacian $Q{\displaystyle }$ ${\displaystyle Q}$은(^[3]는) 다음과 같이 정의된다.

${\displaystyle {\displaysty}Q_{i,j}<0&{\mbox{{}{}}{{neq j{\mbox{과}}{{v_{ni}{\mbox{}{}}}{\mbox{}}{}}}}}는 }v_{j}\\에 인접해 있다.Q_{i},j}=0&{\mbox{{}i\neq j{\mbox{{\mbox{{}{{v_{{i}}{\mbox{any number}}&{\mbox{notherwise}}}}}에 인접하지 않다.\end{case}}}$

일반 라플라시안은 일반화된 라플라시언이라는 것을 주목하라.

변형 라플라시안

변형된 라플라시안(Laplacian)은 일반적으로 다음과 같이 정의된다.

${\displaystyle \Delta(s)=I-sA+s^{2}(D-I)}$

여기서 I는 ID 매트릭스, A는 인접 매트릭스, D는 도 매트릭스, s는 (복잡한 값을 갖는) 숫자다. ^[4]
표준 라플라시안은 $\Delta \mathrm{}$( $1$) ${\textstyle \Delta(1)}$과 $\Delta \mathrm{}$($$- $1$)$$= D$$+ $A$ ${\textstyle \Delta (-1)=D+$에 $\mathrm{불과하다}$.$A}$는 표식이 없는 라플라시안이다.

시그널리스 라플라시안

부호 없는 라플라시안은 다음과 같이 정의된다.

$[\displaystyle Q=D+)A}$

여기서 D ${\displaystyle D}$은 도 행렬이고$$A {\$displaystyle A}$은 인접 행렬이다.^[5] 서명된 Laplacian $L{\displaystyle }$ ${\displaystyle L}$과 같이$,$ 부호 없는 Laplacian $Q{\displaystyle }$ ${\displaysty Q}$도 양성으로 반확정성이 있다.

${\displaystyle Q=RR^{\textsf{T}}$

여기서 $R$ ${\textstyle R}$은(는) 발생 행렬이다. ${\displaystyle Q}$ ${\displaystyle Q}$은(는) 분리된 정점 이외의 초당적 연결 구성요소를 가진 경우에만 0 고유 벡터를 가진다$$. 이것은 다음과 같이 보여질 수 있다.

${\displaystyle \mathbf {x} ^{\textsf {T}Q\mathbf {x} ^{\textsf {T}RR^{T}\textsf {x}\mathbf {t}\textbf {x} \mathbf {0}.$

그래프에 초당적으로 연결된 구성 요소가 있는 경우에만$$ x${\displaystyle }x{\displaystyle \mathbf{}}$ ${\displaystyle 0\mathbf{}}$ ${\$가) 있는 솔루션이 있다.

지시 다중 글씨가 있음

라플라시안 매트릭스의 아날로그는 지시된 다중 글자에 대해 정의할 수 있다.^[6] 이 경우 라플라크 행렬 L은 다음과 같이 정의된다.

$L=D-A,}$

여기서 D는 D가_i,i 정점 i의 아웃도와 동일한 대각 행렬이고 A는 i에서 j까지의 에지 수와 동일한 A를_i,j 갖는 행렬(루프 포함)이다.

참고 항목

• 강성행렬
• 저항 거리
• 전환율 매트릭스
• 유한 가중 그래프에 대한 미적분
• 그래프 푸리에 변환

참조

• T. 수나다, "구체적인 기하학적 분석", 순수 수학에서의 심포비아의 진행 (ed. by P) 엑너, J. P. 키팅, P. 쿠치먼트, T. 수나다, A. Telyaev), 77(2008), 51–86.
• B. Bollobás, Modern Graph Theory, Springer-Verlag (1998, corrected ed. 2013), ISBN 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).