Ch.8 §8.2 Graphs and Networks — 접속행렬 \(A\), 키르히호프 법칙, 그리고 그래프 라플라시안 \(A^\top C A\)

전기 회로에서 그래프 라플라시안과 스펙트럴 그래프 이론까지: §8.1의 골격이 그래프 위에서 다시 등장하는 이야기

Strang Ch.8 §8.2를 단독으로 상세히 다룬다. 방향 그래프의 접속행렬(incidence matrix) \(A\) 가 어떻게 키르히호프의 두 법칙(KVL, KCL)을 자동으로 만들어 내는지, 그리고 컨덕턴스 대각행렬 \(C\) 와 함께 그래프 라플라시안 \(L = A^\top C A\) 를 구성하는 과정을 §8.1의 \(K = A^\top C A\) 와 같은 골격으로 전개한다. 4-노드 완전 그래프에 전류원을 넣은 손계산 예제, 영공간/좌영공간의 물리적 해석, 오일러 공식, 그리고 스펙트럴 그래프 이론·랜덤워크·GNN·PageRank로 이어지는 현대적 응용도 함께 정리한다.

Math
Linear Algebra
저자

Kwangmin Kim

공개

2026년 04월 12일

1 개요

한 줄 요약

방향 그래프의 접속행렬(incidence matrix) \(A\) 와 컨덕턴스 대각행렬 \(C\) 가 만나면, 회로의 평형 방정식은 정확히 \(L\,x = f,\;\; L = A^\top C A\) 가 된다. 이 행렬 \(L\) 이 곧 그래프 라플라시안 이고, 그 영공간은 “그래프의 연결 성분 개수만큼의 자유도”, 좌영공간은 “독립 루프의 개수만큼의 보존류”, 그리고 양정치성은 “나무(tree)일 때만” 회복된다. §8.1의 스프링-질량 골격이 그래프 위에서 단어만 바뀐 채 그대로 등장한다.

§8.1에서 우리는 스프링-질량 모델을 통해 강성행렬 \(K = A^\top C A\) 가 어떻게 등장하는지 보았다 (Ch.8 §8.1 — Matrices in Engineering 참조). 이번 절은 같은 골격이 전기 회로 와 네트워크 에서 한 글자도 안 바꾸고 다시 등장한다는 사실을 보여 준다. 차이는 단어뿐이다.

§8.1 (역학) §8.2 (전기)
변위 \(u\) 전위(potential) \(x\)
신장 \(e = A u\) 전위차 \(A x\)
스프링 상수 \(C\) 컨덕턴스 \(C = 1/(\text{저항})\)
내부힘 \(y = C e\) 전류 \(y = -C A x\) (Ohm 법칙)
외부힘 \(f = A^\top y\) 외부 전류원 \(A^\top y = f\) (KCL)
강성행렬 \(K = A^\top C A\) 그래프 라플라시안 \(L = A^\top C A\)

이 표 한 장을 머릿속에 박아 두면, 이 절에서 새로 배워야 할 것은 “\(A\) 가 무엇이냐” 하나뿐이다. 행렬 \(A\) 의 기본 사실(접속행렬, 영공간, 행공간, 좌영공간)은 MIT 18.06 Lecture 12 — 그래프, 네트워크, 근접 행렬 에서 강의노트 스타일로 정리했으므로, 이 절은 그 위에 §8.1과의 연결고리, 스펙트럴 그래프 해석, 그리고 현대 데이터 사이언스 응용 을 더 깊게 쌓는다.

2 방향 그래프와 접속행렬

그래프 \(G = (V, E)\) 는 \(n\) 개의 노드(정점) \(V = \{1, \dots, n\}\) 와 \(m\) 개의 에지(변) \(E = \{e_1, \dots, e_m\}\) 로 구성된다. 방향 그래프 는 각 에지에 화살표(임의로 정한 양의 방향)가 붙은 그래프다. 방향 자체는 임의지만, 한 번 정하면 일관되게 유지한다.

이 정보를 행렬 한 장에 담는 방식이 접속행렬(incidence matrix) 이다.

\[ A \in \mathbb{R}^{m \times n}, \qquad A_{ki} = \begin{cases} -1 & \text{에지 } k \text{ 가 노드 } i \text{ 에서 출발} \\ +1 & \text{에지 } k \text{ 가 노드 } i \text{ 에 도착} \\ 0 & \text{그 외} \end{cases}. \]

행 = 에지, 열 = 노드. 한 행에는 정확히 \(-1\) 한 개와 \(+1\) 한 개가 있고 나머지는 모두 0이다.

Strang의 기본 예제 — \(n = 4\) 노드, \(m = 6\) 에지인 완전 그래프 \(K_4\). 에지 번호와 화살표는 다음과 같다.

에지 출발 → 도착
1 \(1 \to 2\)
2 \(1 \to 3\)
3 \(2 \to 3\)
4 \(1 \to 4\)
5 \(2 \to 4\)
6 \(3 \to 4\)

이를 위 규칙에 대입하면

\[ A = \begin{bmatrix} -1 & 1 & 0 & 0 \\ -1 & 0 & 1 & 0 \\ 0 & -1 & 1 & 0 \\ -1 & 0 & 0 & 1 \\ 0 & -1 & 0 & 1 \\ 0 & 0 & -1 & 1 \end{bmatrix}. \]

이 행렬 한 장이 그래프의 모든 위상정보 를 담고 있다. 그림이 없어도 행을 보고 에지를, 열을 보고 노드를 복원할 수 있다.

한 가지 중요한 성질

\(A\) 의 모든 행은 합이 0이다. 따라서 모든 1로 이루어진 벡터 \(\mathbf{1} = (1, 1, 1, 1)^\top\) 에 대해 \(A\mathbf{1} = \mathbf{0}\) 이고, 이는 곧 상수 벡터가 항상 \(A\) 의 영공간에 들어 있다 는 뜻이다. 물리적으로 “모든 노드의 전위를 같은 양만큼 올리면 어느 에지에서도 전위차가 변하지 않는다” 는 사실에 대응한다. 미적분에서 부정적분이 \(+ C\) 만큼 임의의 상수를 가지는 것과 정확히 같은 자유도다.

3 첫 번째 단계 \(e = A x\): 전위차

스프링 모델에서 \(e = A u\) 가 변위로부터 신장을 만들었듯, 회로에서 \(A x\) 는 노드의 전위(potential) \(x\) 로부터 각 에지에서의 전위차(potential difference) 를 만든다.

\[ A x = \begin{bmatrix} x_2 - x_1 \\ x_3 - x_1 \\ x_3 - x_2 \\ x_4 - x_1 \\ x_4 - x_2 \\ x_4 - x_3 \end{bmatrix}. \]

각 성분은 “도착 노드의 전위 − 출발 노드의 전위” 를 그대로 적은 것이다. 이 단계는 순수한 기하학 이고, 어떤 재료적 가정도 들어 있지 않다.

직관: \(A\) 는 “이산 미분(discrete derivative)”

연속 함수에서 도함수 \(du/dx\) 가 “이웃한 두 점의 차이” 를 측정하듯, \(A x\) 도 “이웃한 두 노드의 차이” 를 측정한다. 그래서 \(A\) 를 그래프의 이산 미분 연산자 로 부르기도 한다. 그러면 §8.1 끝에서 본 연속 극한 \(A \to d/dx\) 의 의미가 더 분명해진다.

4 두 번째 단계 \(y = -C A x\): Ohm 법칙

회로의 한 에지에 흐르는 전류 \(y_k\) 는 두 가지에 비례한다.

  • 그 에지의 양 끝점 사이 전위차 \(x_i - x_j\)
  • 그 에지의 컨덕턴스 \(c_k\) (즉, \(1 / R_k\), 저항의 역수)

이것이 바로 옴의 법칙

\[ y_k = c_k\,(x_i - x_j). \]

회로 이론의 관습은 “전류는 높은 전위에서 낮은 전위로 흐른다” 이므로 부호가 \(-A x\) 가 된다. 즉

\[ \boxed{\;y = -C A x, \qquad C = \operatorname{diag}(c_1, \dots, c_m).\;} \]

§8.1의 \(y = C e\) 와 비교하면 부호 하나 차이뿐이다 (역학에서는 양의 신장이 양의 인장력을 만들지만, 회로에서는 양의 전위차가 반대 방향 전류를 만들기 때문). 이 부호는 골격을 깨지 않는다 — 어차피 다음 단계에서 \(A^\top\) 와 한 번 더 만나면서 결과는 양정치 형태로 돌아온다.

모든 분야의 구성식은 같은 자리에 있다

같은 두 번째 단계 \(y = (\text{재료})(\text{변위 차이})\) 가 분야마다 이름만 달리해서 등장한다.

분야 구성식 이름 형태
역학 Hooke 법칙 응력 = 탄성률 × 변형률
전기 Ohm 법칙 전류 = 컨덕턴스 × 전위차
열전달 Fourier 법칙 열류 = 열전도도 × 온도구배
유체 Darcy 법칙 유량 = 투과율 × 압력구배
통계 정규방정식의 가중치 가중 잔차 = 가중치 × 잔차

세 단계 골격에서 두 번째 단계만 분야마다 다르고, 첫 번째와 세 번째는 분야와 무관하게 항상 \(A\) 와 \(A^\top\) 다. 이것이 “응용수학의 모든 평형 문제는 \(A^\top C A\) 다” 라는 Strang의 표현의 정확한 의미다.

5 세 번째 단계 \(A^\top y = f\): 키르히호프 전류 법칙 (KCL)

각 노드에서 들어오는 전류와 나가는 전류가 정확히 균형을 이루어야 한다. 외부 전류원이 노드 \(i\) 에 \(f_i\) 만큼을 주입한다고 하자. 그러면

\[ \sum_{\text{노드 }i\text{ 에 들어오는 에지}} y_k - \sum_{\text{노드 }i\text{ 에서 나가는 에지}} y_k = f_i. \]

이 균형 조건을 모든 노드에 대해 묶으면 행렬형으로

\[ \boxed{\;A^\top y = f.\;} \]

이것이 키르히호프의 전류 법칙(Kirchhoff’s Current Law, KCL) 이다. 그리고 결정적으로 — 이 행렬은 1단계의 \(A\) 의 전치 와 정확히 같다. 우리가 일부러 그렇게 만든 것이 아니라, 노드 \(i\) 에서 보면 “들어오는 = \(+1\), 나가는 = \(-1\)” 의 부호가 자연스럽게 행과 열을 뒤집기 때문이다.

가상일의 원리로 다시 보기

임의의 가상 전위 변화 \(\delta x\) 에 대해, 외부 전류원이 한 일은 \(\delta x^\top f\) 이고, 내부 전류가 한 일은 \(\delta(Ax)^\top y = \delta x^\top (A^\top y)\) 이다. 두 일이 같아야 평형이 성립하므로 \(f = A^\top y\) 가 강제된다. 즉 \(A\) 와 \(A^\top\) 가 항상 함께 등장하는 이유는 §8.1에서와 동일하게 에너지 균형 이다.

6 합치기: 그래프 라플라시안 \(L = A^\top C A\)

세 단계를 결합하면

\[ f = A^\top y = A^\top(-CAx) = -A^\top C A\, x. \]

부호를 양변에 거꾸로 두면

\[ \boxed{\;L\, x = f, \qquad L = A^\top C A.\;} \]

이 행렬 \(L\) 이 바로 (가중) 그래프 라플라시안(weighted graph Laplacian) 이다. 컨덕턴스가 모두 1이면 \(L = A^\top A\) 가 표준 그래프 라플라시안이 된다.

한 줄로 검증할 수 있는 성질

  1. 대칭 — \(L^\top = (A^\top C A)^\top = A^\top C^\top A = A^\top C A = L\). (cf. §8.1)
  2. 양반정치 — 임의의 \(x\) 에 대해 \(x^\top L x = (Ax)^\top C (Ax) = \sum_k c_k (Ax)_k^2 \ge 0\).
  3. 에너지 해석 — \(\frac{1}{2} x^\top L x\) 는 회로 전체에서 소산되는 열에너지(power dissipation) \(\frac{1}{2} \sum_k c_k (\text{전위차})_k^2\) 다.

세 성질 모두 §8.1과 한 줄도 다르지 않다. 단어만 “에너지 → 열손실”, “양정치 → 양반정치”로 살짝 바뀌었을 뿐이다.

그런데 왜 §8.1과 달리 양반정치인가 — 바로 다음 절에서 답한다.

7 영공간과 양정치성: 그래프의 위상이 결정한다

§8.1에서 \(K\) 가 양정치가 되려면 \(A\) 가 독립 열을 가져야 했다. 회로 \(A\) 의 경우는 어떤가?

답: 그래프가 연결되어 있으면, \(A\) 의 영공간은 정확히 1차원이고 상수 벡터 \(\mathbf{1}\) 이 들어 있다.

증명 스케치 — \(A x = 0\) 이면 모든 에지에서 전위차가 0, 즉 인접한 두 노드의 전위가 같다. 그래프가 연결되어 있으면 모든 노드가 어떤 경로로든 이어져 있으므로 전체 노드의 전위가 같은 값 \(c\) 가 되어야 한다. 따라서 \(x = c\mathbf{1}\).

이것이 의미하는 것:

\[ \dim N(A) = (\text{연결 성분의 개수}), \qquad \operatorname{rank}(A) = n - (\text{연결 성분 개수}). \]

연결 그래프의 경우 \(\operatorname{rank}(A) = n - 1\) 이고, \(L = A^\top C A\) 도 같은 영공간 \(\operatorname{span}\{\mathbf{1}\}\) 을 가져 양반정치이지만 양정치는 아니다.

물리적 의미: 접지(grounding)

\(L x = f\) 는 그대로는 풀리지 않는다. 영공간이 비어 있지 않기 때문에 \(L\) 은 가역이 아니고, 또 \(f\) 가 영공간과 직교해야 — 즉 \(\mathbf{1}^\top f = \sum f_i = 0\) 이어야 — 해가 존재한다. 후자의 의미는 분명하다: 외부에서 주입하는 전류의 총합은 0이어야 한다. 그렇지 않으면 회로에서 전하가 무한히 쌓여 평형이 존재하지 않는다.

전자의 자유도(영공간)는 한 노드를 접지(ground) 함으로써 제거한다. 즉 \(x_n = 0\) 으로 고정하고 \(L\) 의 마지막 행과 열을 제거하면, 남은 \((n-1) \times (n-1)\) 부분행렬은 가역이고 양정치다. 회로 시뮬레이터가 항상 한 노드를 접지로 잡는 이유다.

8 좌영공간 \(N(A^\top)\) 와 키르히호프 전압 법칙 (KVL)

이제 행과 열을 바꿔서 \(A^\top y = 0\) 의 해를 찾는다. 이는 외부 소스 없이 (\(f = 0\)) 회로 안에서만 흐를 수 있는 전류 패턴을 묻는 것이다.

물리적 직관: 루프 전류(loop current) 다. 그래프 안의 닫힌 루프를 따라 단위 전류를 한 바퀴 흘리면, 모든 노드에서 들어오는 양과 나가는 양이 정확히 같다 (한 번 들어왔으니 한 번 나가야 다시 출발점으로 돌아온다). 따라서 그 루프 전류 벡터는 \(A^\top y = 0\) 의 해다.

좌영공간의 차원 — 평면 그래프에 대해 오일러의 공식

\[ n - m + (\text{독립 루프 수}) = (\text{연결 성분 수}). \]

연결 그래프(연결 성분 1개)에서

\[ \dim N(A^\top) = m - r = m - (n - 1) = m - n + 1. \]

이것이 곧 독립 루프의 개수 다. Strang의 예제 (\(K_4\), \(n=4\), \(m=6\))에서는 \(m - n + 1 = 3\) 이다. 실제로 그림에서 작은 삼각형 루프 3개가 독립이고, 큰 삼각형 루프는 그 합이다.

키르히호프 전압 법칙 (KVL) 의 행렬판

“닫힌 루프를 따라 전위차의 합은 0이다” 는 KVL은, 그래프 언어로 말하면 \(A x\) 의 성분을 임의의 닫힌 루프를 따라 더하면 0이 된다 는 것이다. 이것은 정의에서 자동으로 따라온다 — 루프에서 한 바퀴 돌면 시작 노드로 돌아오므로 전위 차이의 누적이 0이다. 즉 \(C(A)\) (열공간)는 정확히 “루프 적분이 0인 벡터들의 부분공간” 이고, 이것이 \(N(A^\top)\) 와 직교하는 이유다.

요약하면

  • KVL ↔︎ 열공간 \(C(A)\) (모든 루프 적분이 0)
  • KCL ↔︎ 좌영공간 \(N(A^\top)\) (모든 루프 전류가 가능한 해)
  • 두 부분공간이 서로 직교하는 것이 곧 선형대수의 기본정리 의 회로 버전이다.

9 손계산 예제: \(K_4\) + 단위 전류원

이제 위 골격으로 구체적인 회로를 푼다. 모든 컨덕턴스가 1, 외부 전류원 \(S\) 가 노드 1로 들어와서 노드 4로 빠져나간다고 하자. 즉

\[ f = (S, 0, 0, -S). \]

(노드별로 들어오는 전류가 양, 나가는 것이 음. 합이 0이므로 평형이 가능하다.)

1단계: \(L = A^\top A\) 계산

위에서 적은 \(A\) 를 그대로 곱하면

\[ L = A^\top A = \begin{bmatrix} 3 & -1 & -1 & -1 \\ -1 & 3 & -1 & -1 \\ -1 & -1 & 3 & -1 \\ -1 & -1 & -1 & 3 \end{bmatrix}. \]

대각 성분 3 = 각 노드의 차수(degree, 연결된 에지 수). 비대각 \(-1\) = 두 노드가 연결되어 있다는 표시. 이것이 그래프 라플라시안의 표준 표현 이다 — 차수 행렬 \(D\) 빼기 인접 행렬 \(A_{\text{adj}}\).

\[ L = D - A_{\text{adj}}. \]

(여기서의 \(A_{\text{adj}}\) 는 인접행렬이라 incidence matrix \(A\) 와 다른 행렬이지만, 책의 표기 관습이라 같은 글자를 쓴다.)

2단계: 접지하고 가역화

노드 4를 접지 (\(x_4 = 0\))하면 4번째 행과 열을 제거한다.

\[ L_{\text{red}} = \begin{bmatrix} 3 & -1 & -1 \\ -1 & 3 & -1 \\ -1 & -1 & 3 \end{bmatrix}, \qquad f_{\text{red}} = \begin{bmatrix} S \\ 0 \\ 0 \end{bmatrix}. \]

3단계: 풀기

대칭과 직관으로 \(x_2 = x_3\) 임을 짐작할 수 있다 (노드 2와 3은 노드 1과 4 사이에서 정확히 같은 위치). 가정해서 풀면

\[ 3 x_1 - 2 x_2 = S, \qquad -x_1 + 2 x_2 = 0. \]

두 번째 식에서 \(x_1 = 2 x_2\) 를 첫 식에 대입하면 \(6 x_2 - 2 x_2 = S\), 즉 \(x_2 = S/4\), \(x_1 = S/2\).

\[ \boxed{\;x = (S/2,\; S/4,\; S/4,\; 0).\;} \]

4단계: Ohm 법칙으로 전류 복원

\(y = -C A x = -A x\) 이므로

\[ y = -\begin{bmatrix} x_2 - x_1 \\ x_3 - x_1 \\ x_3 - x_2 \\ x_4 - x_1 \\ x_4 - x_2 \\ x_4 - x_3 \end{bmatrix} = \begin{bmatrix} S/4 \\ S/4 \\ 0 \\ S/2 \\ S/4 \\ S/4 \end{bmatrix}. \]

해석 — 들어온 전류 \(S\) 의 정확히 절반은 가장 짧은 길(에지 4: 노드 1 → 4)로 직진한다. 나머지 절반은 두 갈래로 똑같이 갈라져 (에지 1 → 5: \(1\to2\to4\), 에지 2 → 6: \(1\to3\to4\)) 각각 \(S/4\) 씩 흐른다. 노드 2와 3 사이를 잇는 에지 3에는 전류가 흐르지 않는다 — 두 노드의 전위가 같으므로 흐를 이유가 없다. 대칭이 결과를 대칭으로 만든 것이다.

자연이 최소화하는 양

앞서 \(\frac{1}{2} x^\top L x\) 가 회로의 열손실 \(\frac{1}{2}\sum c_k(\Delta x)_k^2\) 라고 했다. 자연(전류의 분포)은 이 에너지를 최소화 하는 쪽으로 전류를 흘린다. 즉 \(L x = f\) 의 해는 동시에 다음 변분 문제의 해다.

\[ \min_x \;\tfrac{1}{2} x^\top L x - x^\top f. \]

이는 §8.1의 강성행렬에서도 같았고, 다음 절(Ch.8 §8.6)에서 볼 가중 최소제곱(BLUE)의 변분 형태와도 같다. 응용수학의 모든 평형은 이차형식의 최소화 문제와 등가 다.

10 트리, 루프, 오일러 공식

오일러의 공식을 다시 쓰면

\[ n - m + (\text{독립 루프 수}) = 1 \qquad (\text{연결된 평면 그래프}). \]

이 공식의 선형대수 버전은 \(r = n - 1\), \(\dim N(A^\top) = m - r = m - n + 1\) 이고, 두 식을 더하면 정확히 1이 나온다.

두 극단:

그래프 종류 에지 수 루프 수 비고
트리(tree) \(m = n - 1\) \(0\) 행이 모두 독립, \(A\) 는 키 큰 직사각
완전 그래프(complete) \(m = n(n-1)/2\) \(\binom{n-1}{2}\) 행이 가장 많이 종속

따라서 가장 단순한 형태로 환원하는 가우스 소거는 정확히 그래프를 신장 트리(spanning tree)로 줄이는 작업 과 같다. 소거가 만들어 내는 0행은 곧 “이 에지는 루프에 의해 종속된다” 는 사실의 행렬 버전이다.

회로 이론과 그래프 이론의 만남
  • 신장 트리 = 가우스 소거가 멈추는 곳 = \(A\) 의 행공간 기저
  • 루프(loop) = 신장 트리에 추가되는 모든 에지마다 정확히 하나씩 만들어진다 = \(A^\top\) 의 영공간 기저
  • 따라서 회로의 “독립 KCL 방정식 수” 는 \(n - 1\) (= 트리 에지 수), “독립 KVL 방정식 수” 는 \(m - n + 1\) (= 루프 수). 이 둘을 더하면 \(m\) 이 되어, 미지 전류 \(m\) 개를 정확히 풀 수 있다.

11 코드: NumPy 로 \(K_4\) 풀기

import numpy as np

# 4-노드 완전 그래프 K4 의 접속행렬 (6 by 4)
A = np.array([
    [-1,  1,  0,  0],   # edge 1: 1 -> 2
    [-1,  0,  1,  0],   # edge 2: 1 -> 3
    [ 0, -1,  1,  0],   # edge 3: 2 -> 3
    [-1,  0,  0,  1],   # edge 4: 1 -> 4
    [ 0, -1,  0,  1],   # edge 5: 2 -> 4
    [ 0,  0, -1,  1],   # edge 6: 3 -> 4
])

# 컨덕턴스 모두 1
C = np.eye(6)

# 그래프 라플라시안
L = A.T @ C @ A
print("L =\n", L)
# [[ 3 -1 -1 -1]
#  [-1  3 -1 -1]
#  [-1 -1  3 -1]
#  [-1 -1 -1  3]]

# 접지: 노드 4 제거
L_red = L[:3, :3]
S = 1.0
f_red = np.array([S, 0.0, 0.0])

x_red = np.linalg.solve(L_red, f_red)
x = np.append(x_red, 0.0)
print("전위 x =", x)         # [0.5  0.25 0.25 0.  ]

# Ohm 법칙으로 전류 복원
y = -C @ A @ x
print("전류 y =", y)
# [0.25 0.25 0.   0.5  0.25 0.25]

# 영공간 검증
eigvals = np.linalg.eigvalsh(L)
print("L 고유값 =", np.round(eigvals, 6))
# [0. 4. 4. 4]   ← 0 이 정확히 한 번 = 연결 성분 1개

# 전체 열손실 = (1/2) x^T L x
power = 0.5 * x @ L @ x
print("열손실 =", power)     # 0.25 = (1/2)·S·x_1 = 입력 일률의 절반

이 한 번의 실행으로 손계산 결과가 그대로 검증된다. 특히 마지막 줄의 고유값 패턴 \(\{0, 4, 4, 4\}\) 는 우연이 아니다 — 다음 절의 주제다.

12 그래프 라플라시안의 스펙트럼 한 발짝

라플라시안 \(L\) 은 대칭 양반정치이므로 모든 고유값이 음이 아니다. 가장 작은 고유값은 항상

\[ \lambda_1 = 0, \qquad \text{고유벡터} = \mathbf{1}. \]

이 0 고유값의 중복도(multiplicity) 가 연결 성분의 개수 와 같다는 사실은 그래프 이론의 기본 정리 중 하나다. 즉

\[ (\text{연결 성분 수}) = \dim N(L) = (\lambda = 0 \text{ 의 중복도}). \]

두 번째로 작은 고유값 \(\lambda_2\) 는 Fiedler 값 또는 algebraic connectivity 라 불리고, 그래프가 얼마나 “잘 연결되어 있는지” 를 측정한다. 이 값과 그에 대응하는 고유벡터(Fiedler 벡터)가 스펙트럴 클러스터링 의 핵심 도구다 — 노드들을 Fiedler 벡터 성분의 부호에 따라 두 그룹으로 나누면 그래프 컷이 거의 최소가 된다.

스펙트럼 정보 그래프 의미 응용
\(\lambda_1 = 0\) 의 중복도 연결 성분 개수 그래프 분할 / 컨네티드 컴포넌트 검출
\(\lambda_2\) (Fiedler 값) 연결 강도(algebraic connectivity) 스펙트럴 클러스터링
\(\lambda_2\) 의 고유벡터 최소 컷 방향 이미지 분할, 커뮤니티 탐지
\(\sum \lambda_i\) \(\operatorname{tr}(L) = 2m\) (가중 X) 에지 총량
\(\det(L_{\text{red}})\) 신장 트리 개수 (Matrix-Tree Theorem) 회로 분석, 무작위 그래프 통계

위 코드의 \(K_4\) 에서 고유값이 \(\{0, 4, 4, 4\}\) 인 이유는 \(K_n\) 의 라플라시안 고유값이 \(\{0, n, n, \dots, n\}\) 이기 때문이다. 그리고 Matrix-Tree 정리로부터 \(K_n\) 의 신장 트리 수는 \(\det(L_{\text{red}}) = n^{n-2}\) — Cayley의 공식이 한 줄로 따라 나온다 (\(K_4\) 의 경우 \(4^2 = 16\)).

13 데이터 사이언스와의 연결

같은 \(L = A^\top C A\) 가 현대 ML 에서 여러 이름으로 등장한다.

분야 행렬 용도
스펙트럴 클러스터링 정규화 라플라시안 \(L = I - D^{-1/2} A_{\text{adj}} D^{-1/2}\) 노드를 군집화
그래프 신경망(GNN) \(L\) 또는 \(A_{\text{adj}}\) 메시지 패싱의 1차 근사
Tikhonov 정규화 \(\lambda L\) 그래프 위의 매끄러운 함수 학습 (Laplacian regularization)
반지도 학습 \(L\) 라벨 전파(label propagation) — \(L x = f\) 와 같은 골격
PageRank \((I - \alpha P)\) 랜덤워크의 정상 분포 (\(P\) 는 \(D^{-1} A_{\text{adj}}\), 다음 절 §8.3 마르코프 행렬과 직결)
회로 시뮬레이터(SPICE) \(A^\top G A\) \(G\) 는 컨덕턴스 행렬, 정확히 같은 골격

특히 반지도 학습의 라벨 전파 는 직관이 회로와 거의 같다. 일부 노드에 라벨 (\(f_i \neq 0\), “전류원”) 을 주고, 나머지 노드의 라벨 (\(x_i\), “전위”) 을 \(L x = f\) 의 해로 결정한다. 라벨이 없는 노드의 전위는 주변 라벨 노드들의 가중 평균으로 자동 결정된다. 회로에서 전류가 가장 효율적인 경로로 흐르듯, 라벨도 그래프 위에서 가장 매끄러운 방식으로 퍼진다.

마찬가지로 PageRank 는 (\(I - \alpha P^\top\)) 형태의 선형 시스템을 푸는 것이고, \(P = D^{-1} A_{\text{adj}}\) 가 마르코프 전이 행렬이다. 다음 절 §8.3 (Markov Matrices) 에서 이어진다.

14 정리

이 절의 모든 내용은 다음 한 다이어그램으로 요약된다.

\[ \underbrace{x}_{\text{전위}} \;\xrightarrow{\;A\;}\; \underbrace{Ax}_{\text{전위차}} \;\xrightarrow{\;-C\;}\; \underbrace{y}_{\text{전류}} \;\xrightarrow{\;A^\top\;}\; \underbrace{f}_{\text{외부 전류원}} \]

단계 식 회로의 이름 일반 골격
1 \(Ax\) 전위차 (이산 미분) 운동학
2 \(y = -C A x\) Ohm 법칙 구성식
3 \(A^\top y = f\) 키르히호프 전류 법칙 평형
합 \(L x = f,\; L = A^\top C A\) 그래프 라플라시안 강성행렬과 같은 골격

핵심 사실 다섯

  1. \(L\) 은 항상 대칭 양반정치 — 그래프와 컨덕턴스 정의에서 자동으로 따라온다.
  2. 영공간은 연결 성분 개수 — 연결 그래프에서는 \(\mathbf{1}\) 한 방향뿐.
  3. 양정치성은 한 노드를 접지하면 회복 — \(L_{\text{red}}\) 가 가역이 되고 \(L_{\text{red}} x = f\) 가 유일해를 가진다.
  4. 좌영공간 = 루프 전류 — \(\dim = m - n + 1\), 오일러 공식의 행렬판.
  5. §8.1의 골격과 단어만 다르고 수학은 동일 — 강성행렬과 그래프 라플라시안은 같은 한 가족이다.

15 관련 주제

Subscribe

Enjoy this blog? Get notified of new posts by email: