Graph - Laplacian Matrix의 Fiedler Value

Fiedler Value  : 두 번째로 작은 고유값 \( \lambda_1 \)
Fiedler Vector : 이 고유값에 대응하는 고유벡터 \( \mathbf{v}_1 \)

 

Fiedler Value와 그래프의 클러스터링

Fiedler value는 그래프의 클러스터링 구조를 나타내는 중요한 지표로 Fiedler value가 작을수록 그래프는 더 잘 클러스터링된 구조를 가지고 있음을 의미한다.

1. 스펙트럼 그래프 이론
   그래프의 라플라시안 행렬 \( L \)은 그래프의 구조를 수학적으로 나타낸다. 라플라시안 행렬의 고유값과 고유벡터는 그래프의 여러 특성을 반영한다. 특히, 두 번째 고유값 \( \lambda_1 \) (Fiedler value)은 그래프의 클러스터링 가능성을 나타낸다.
2. 그래프 분리
   Fiedler value \( \lambda_1 \)가 작을수록, 그래프를 두 개의 서브그래프로 나누는 데 필요한 '잘라야 하는' 엣지의 수가 적음을 의미한다. 이는 그래프가 자연스럽게 두 개의 클러스터로 나눠질 수 있음을 나타낸다.
   따라서 Fiedler value가 작을수록 그래프 내에서 자연스럽게 두 개의 밀접하게 연결된 클러스터가 존재함을 시사합니다.
   또한 작은 Fiedler value는 그래프가 두 개의 클러스터로 나뉘어질 때 각 클러스터 내의 노드들이 서로 강하게 연결되어 있음을 의미한다. 이는 클러스터 내의 연결이 강하고, 클러스터 간의 연결이 상대적으로 약하다는 것을 나타낸다.
3. 스펙트럴 갭
   첫 번째 고유값 \( \lambda_0 \)은 항상 0이며, 이 고유값에 대응하는 고유벡터는 모든 요소가 동일한 값을 가진다. 두 번째 고유값 \( \lambda_1 \)과 첫 번째 고유값 \( \lambda_0 \) 사이의 차이(스펙트럴 갭)가 클수록 그래프는 더 명확한 클러스터링 구조를 가진다.

예시
예를 들어, 6개의 노드를 가진 그래프의 라플라시안 행렬 \( L \)이 다음과 같다고 가정하자:
\[ L = \begin{bmatrix}
2 & -1 & -1 & 0 & 0 & 0 \\
-1 & 3 & -1 & -1 & 0 & 0 \\
-1 & -1 & 3 & -1 & 0 & 0 \\
0 & -1 & -1 & 3 & -1 & 0 \\
0 & 0 & 0 & -1 & 2 & -1 \\
0 & 0 & 0 & 0 & -1 & 1
\end{bmatrix} \]

이 행렬의 두 번째 고유값 \( \lambda_1 \)은 0.585이며, 해당 고유벡터 \( \mathbf{v}_1 \)은 다음과 같다:
\[ \mathbf{v}_1 = \begin{bmatrix}
0.289 \\
0.5 \\
0.5 \\
0.289 \\
-0.5 \\
-0.5
\end{bmatrix} \]

이 고유벡터를 이용하여 그래프를 두 개의 클러스터로 나눌 수 있다. 고유벡터의 양수 값과 음수 값을 기준으로 클러스터를 나누면, 첫 번째 클러스터는 노드 1, 2, 3, 4로 구성되고, 두 번째 클러스터는 노드 5, 6으로 구성된다

관련글 Spectrual Clustering