피들러 벡터

편집 역사 토론
수치해석 시뮬레이션 마지막 수정: 2026-08-01 04:53:41

1. 개요[편집]

피들러 벡터
Fiedler vector
정의그래프 라플라시안의 두 번째로 작은 고유값에 대응하는 고유벡터
짝 고유값λ₂ = 대수적 연결도(algebraic connectivity)
제안Miroslav Fiedler (1973)
주요 용도그래프 이분, 메시 분할, 행렬 재배열, 합의 속도
계산란초스, LOBPCG, 다단계 가속

피들러 벡터(Fiedler vector)는 그래프 라플라시안 행렬의 두 번째로 작은 고유값에 대응하는 고유벡터이며, 그 고유값 λ2\lambda_2를 그래프의 대수적 연결도(algebraic connectivity)라 부른다. 이름은 1973년 이 양의 성질을 정리한 체코 수학자 미로슬라프 피들러에서 왔다.1

한 문장으로 말하면 그래프를 “가장 자연스럽게” 두 덩어리로 자르는 방향을 알려주는 실수 벡터다. 노드마다 실수 하나가 붙는데, 그 값의 부호나 중앙값을 기준으로 자르면 잘라내는 간선 수가 작으면서 양쪽 크기도 얼추 맞는 분할이 나온다. 이 문서는 λ2\lambda_2와 그 고유벡터 자체의 성질·계산·비군집 응용(메시 분할, 행렬 재배열, 합의 속도)에 집중한다. 이 벡터를 kk개 군집으로 확장해 여러 고유벡터를 좌표로 삼고 정규화 절단(NCut)을 완화해 k-평균 군집화로 마무리하는 군집화 절차 전반은 스펙트럴 군집화가, 실제 격자를 만드는 이야기는 메시 생성이, 분할된 조각을 프로세서에 태우는 이야기는 병렬 컴퓨팅이 각각 담당한다.

2. 그래프 라플라시안[편집]

노드 nn개 무향 그래프의 인접행렬을 AA, 차수 대각행렬을 D=diag(d1,…,dn)D = \mathrm{diag}(d_1,\dots,d_n)이라 할 때 그래프 라플라시안은

L=D−AL = D - A

이다. 이 행렬의 모든 성질은 사실상 다음 이차형식 하나에서 나온다.

x⊤Lx=∑(i,j)∈Ewij (xi−xj)2\mathbf{x}^\top L \mathbf{x} = \sum_{(i,j) \in E} w_{ij}\,(x_i - x_j)^2

우변이 제곱합이므로 LL은 대칭 준정부호(PSD)다. 따라서 고유값은 전부 실수이고 0=λ1≤λ2≤⋯≤λn0 = \lambda_1 \le \lambda_2 \le \cdots \le \lambda_n 로 정렬된다. 상수벡터를 넣으면 모든 항이 0이므로

L1=0L\mathbf{1} = \mathbf{0}

즉 가장 작은 고유값은 항상 0이고 그 고유벡터는 상수벡터다. 이 자명한 모드가 있다는 것이 이 행렬을 다룰 때 계속 따라다니는 특징이며, 계산할 때는 매번 이 방향을 걸러내야 한다.

더 중요한 사실은 0 고유값의 중복도가 그래프의 연결 성분 개수와 정확히 같다는 것이다. 성분이 둘이면 각 성분 위에서만 1인 지시벡터 두 개가 모두 LL의 영공간에 들어간다. 이로부터 곧바로 따라오는 것이 다음 명제다.

λ2>0  ⟺  그래프가 연결되어 있다\lambda_2 > 0 \iff \text{그래프가 연결되어 있다}

연결성이라는 조합적 성질이 고유값 하나의 양수성으로 번역된다는 점 때문에 λ2\lambda_2가 “대수적 연결도”라는 이름을 얻었다.

3. 대수적 연결도가 재는 것[편집]

λ2\lambda_2는 단순히 0인지 아닌지만 말하지 않는다. 크기 자체가 얼마나 잘 연결되어 있는가의 정량적 척도다. 쿠랑-피셔 정리를 쓰면

λ2=min⁡x⊥1, x≠0x⊤Lxx⊤x\lambda_2 = \min_{\mathbf{x} \perp \mathbf{1},\ \mathbf{x} \neq \mathbf{0}} \frac{\mathbf{x}^\top L \mathbf{x}}{\mathbf{x}^\top \mathbf{x}}

가 된다. 상수 모드를 제외한 레일리 몫의 최솟값이며, 이를 달성하는 x\mathbf{x}가 바로 피들러 벡터다. 분자는 “이웃끼리 값이 다르면 벌점”, 분모는 “너무 작아지지 마라”이므로, 이 최소화는 평균이 0이라는 제약 아래 이웃끼리 최대한 비슷한 값을 배치하는 문제다. 그래프가 두 덩어리로 갈라져 있고 그 사이 간선이 몇 개뿐이라면, 한쪽에 +a+a 다른 쪽에 −b-b를 주는 배치가 벌점을 거의 물지 않는다. 그래서 최적해는 “덩어리 구조”를 그대로 드러낸다.

알려진 부등식 몇 가지가 감을 잡는 데 도움이 된다. 완전그래프가 아닌 GG에 대해

λ2≤κv(G)≤κe(G)\lambda_2 \le \kappa_v(G) \le \kappa_e(G)

로 정점 연결도·간선 연결도의 하계 역할을 하고, 경로 그래프처럼 길쭉한 그래프는 λ2∼1/n2\lambda_2 \sim 1/n^2 로 0에 급격히 붙는 반면 완전그래프 KnK_n은 λ2=n\lambda_2 = n 으로 최대다. 즉 길고 얇은 구조는 대수적 연결도가 작고, 촘촘한 구조는 크다. 유한요소 메시로 치면 가늘고 긴 관 형상은 λ2\lambda_2가 바닥이고, 3차원 덩어리 형상은 상대적으로 크다.

4. 스펙트럴 이분과 치거 부등식[편집]

그래프를 두 조각 SS, Sˉ\bar S로 나누는 문제를 생각하자. 노드마다 ±1\pm 1 지시값을 주면 잘린 간선 수는 14x⊤Lx\frac{1}{4}\mathbf{x}^\top L \mathbf{x} 이므로, 균형 잡힌 최소 절단은

min⁡x∈{−1,+1}n, x⊤1=0x⊤Lx\min_{\mathbf{x} \in \{-1,+1\}^n,\ \mathbf{x}^\top\mathbf{1}=0} \mathbf{x}^\top L \mathbf{x}

로 쓸 수 있다. 이 문제는 NP-난해다. 여기서 x\mathbf{x}가 ±1\pm 1이어야 한다는 정수 제약만 풀어주고 실수를 허용하면 그것이 바로 앞 절의 레일리 몫 최소화, 즉 피들러 벡터다. 스펙트럴 이분(spectral bisection)의 전부는 이 완화해를 다시 이산화하는 것이다.

  • 부호 절단 — xi>0x_i > 0 이면 SS, 아니면 Sˉ\bar S. 자연스럽지만 양쪽 크기가 심하게 기울 수 있다.
  • 중앙값 절단 — xix_i를 정렬해 위쪽 절반과 아래쪽 절반으로 자른다. 정확히 균등한 이분이 보장되므로 부하 균형이 중요한 병렬 분할에서는 이쪽이 기본값이다.
  • 최적 문턱값 훑기 — 정렬한 뒤 모든 절단 위치를 훑으며 실제 목적함수(컨덕턴스 등)가 최소인 곳을 고른다. 정렬 비용만 추가되므로 사실상 공짜다.

이 완화가 그냥 “그럴듯한 휴리스틱”이 아니라는 것을 보증하는 것이 치거 부등식이다. 아래 절의 정규화 라플라시안 고유값 λ2\lambda_2와 컨덕턴스 hGh_G에 대해

λ22≤hG≤2λ2\frac{\lambda_2}{2} \le h_G \le \sqrt{2\lambda_2}

가 성립한다. 왼쪽 부등식은 λ2\lambda_2가 절단 품질의 하계를 준다는 뜻이고(어떤 절단도 λ2/2\lambda_2/2보다 좋을 수 없다), 오른쪽 부등식은 문턱값 훑기로 얻은 절단이 최적값의 제곱근 규모 안에 든다는 품질 보증이다. 조합 최적화 문제의 연속 완화가 이런 양방향 보증을 갖는 경우는 흔치 않다.2

5. 정규화 변형[편집]

차수가 들쭉날쭉한 그래프에서는 LL을 그대로 쓰면 차수가 큰 노드가 이차형식을 지배해버린다. 그래서 두 가지 정규화가 표준이다.

Lsym=D−1/2LD−1/2=I−D−1/2AD−1/2,Lrw=D−1L=I−D−1AL_{\rm sym} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} A D^{-1/2}, \qquad L_{\rm rw} = D^{-1} L = I - D^{-1}A

LsymL_{\rm sym}은 대칭이라 수치적으로 다루기 편하고, LrwL_{\rm rw}는 무작위 보행의 전이행렬 D−1AD^{-1}A에서 바로 나와 확률적 해석이 명확하다. 둘은 고유값이 완전히 같고 고유벡터가 urw=D−1/2usym\mathbf{u}_{\rm rw} = D^{-1/2}\mathbf{u}_{\rm sym} 로 대응한다. 정규화 스펙트럼은 [0,2][0, 2] 구간에 갇히며, 치거 부등식과 무작위 보행의 혼합 시간 ∼1/λ2\sim 1/\lambda_2 같은 결과가 전부 이쪽 버전에서 성립한다. 간선 절단 수 자체를 줄이는 게 목적이면 정규화하지 않은 LL, 부피 대비 절단 비율(컨덕턴스)을 줄이는 게 목적이면 정규화 버전을 쓰는 것이 대략의 기준이다.

6. 실제 계산[편집]

행렬 전체를 대각화할 필요는 전혀 없다. 필요한 것은 최소 고유값 근처의 벡터 하나이고, 게다가 가장 작은 것(λ1=0\lambda_1 = 0, 상수벡터)은 답을 이미 알고 있다.

  • 란초스 알고리즘 — 대칭 희소행렬의 크릴로프 부분공간법. 매 반복이 행렬-벡터 곱 하나라 병렬 컴퓨팅에도 잘 맞는다. 상수벡터 성분을 매 단계 빼주는 디플레이션이 필수인데, 반올림 오차로 그 방향이 다시 살아나면 수렴이 엉뚱한 곳으로 간다.
  • LOBPCG — 전처리를 얹을 수 있는 국소 최적 블록 전처리 공액경사법. 라플라시안에는 다중격자법이나 불완전 촐레스키 전처리기가 잘 듣는다. 스펙트럼 하단이 촘촘해 란초스가 고전하는 대형 메시에서 특히 유리하다.
  • 다단계 가속 — 그래프를 거칠게 뭉쳐(coarsening) 작은 문제에서 피들러 벡터를 구한 뒤 원래 그래프로 보간해 초기 추정값으로 쓴다. 반복 횟수를 한 자릿수로 떨어뜨리는 실무 표준 기법.

주의할 점은 λ2\lambda_2와 λ3\lambda_3가 가까울 때다. 이때 고유공간이 사실상 축퇴되어 있어 피들러 벡터가 수치적으로 불안정해진다. 대칭성이 높은 격자(정육면체, 정사각형 메시)에서 흔히 벌어지며, 이 경우 어느 방향으로 잘라도 품질이 비슷하다는 뜻이므로 실용적으로는 큰 문제가 아니다. 다만 “같은 메시를 두 번 분할했는데 결과가 다르다”는 재현성 문제가 여기서 나온다.

7. 응용[편집]

7.1. 유한요소 메시 분할[편집]

유한요소법이나 유한체적 해석을 여러 프로세서에 나눠 돌리려면 메시를 균등한 조각으로 쪼개되 조각 사이 인접면(=통신량)을 최소화해야 한다. 요소를 노드로, 면 공유 관계를 간선으로 놓으면 정확히 균형 그래프 이분 문제가 되고, 이를 재귀적으로 적용하는 것이 재귀 스펙트럴 이분(RSB)이다. 1990년대 초 초대형 구조해석 병렬화의 표준이었다.3

오늘날 실무의 기본값은 METIS 계열의 다단계 기법이다. 그래프를 뭉치고 → 작은 그래프에서 분할하고 → 되풀면서 커니건-린/피두시아-마테이스 국소 개선을 얹는 방식으로, 시간복잡도가 사실상 간선 수에 선형이라 고유값 계산이 필요한 스펙트럴 방법보다 훨씬 빠르다. 절단 품질도 대체로 대등하거나 낫다. 그래서 오늘날 피들러 벡터의 위치는 다단계 기법의 초기 분할 단계 또는 품질 비교용 기준선, 그리고 절단 하계를 주는 이론적 도구 쪽으로 이동했다.

7.2. 행렬 재배열[편집]

희소 대칭 행렬의 0이 아닌 성분을 대각 근처로 몰아넣으면 LU 분해나 촐레스키 분해의 채움(fill-in)이 줄고 캐시 효율이 오른다. 피들러 벡터 값 순으로 행·열을 정렬하는 스펙트럴 재배열은 ∑(i,j)∈E(πi−πj)2\sum_{(i,j)\in E}(\pi_i - \pi_j)^2 를 완화 최소화하는 것과 같아, 대역폭·엔벨로프 축소에 바로 쓰인다. 고전적인 역 커스힐-맥키(RCM) 재배열이 훨씬 싸서 널리 쓰이지만, 구조가 복잡한 그래프에서는 스펙트럴 재배열이 더 좋은 순서를 내는 경우가 있다.

7.3. 합의와 동기화[편집]

nn개 노드가 이웃끼리만 값을 주고받으며 평균에 수렴하는 합의 동역학은

x˙=−Lx\dot{\mathbf{x}} = -L\mathbf{x}

로 쓰인다. 해를 고유벡터로 전개하면 상수 모드(=평균)만 남고 나머지 모드는 e−λkte^{-\lambda_k t} 로 죽는다. 따라서 불일치가 사라지는 속도는 정확히 λ2\lambda_2가 지배한다. 무선 센서 네트워크의 분산 평균, 다중 로봇 대형 제어, 결합 진동자의 동기화 안정성이 모두 이 결론에 얹혀 있고, “링크를 어디에 추가해야 합의가 빨라지는가”는 곧 λ2\lambda_2 최대화 문제(볼록 최적화로 풀린다)가 된다. 네트워크 강건성 지표로 λ2\lambda_2를 쓰는 관행도 여기서 나왔다.4

8. 관련 문서[편집]

9. Footnotes[편집]

  1. Fiedler, M. (1973). Algebraic connectivity of graphs. Czechoslovak Mathematical Journal. 정작 “피들러 벡터”라는 이름은 1990년 포덴·사이먼·류가 메시 분할 논문에서 붙인 것이다. 본인 이름이 붙은 벡터를 17년 뒤 남이 명명해 주는 것도 나름 훈훈한 전개. ↩

  2. 치거 부등식의 원본은 리만 다양체 위 라플라스-벨트라미 연산자에 대한 결과(Cheeger, 1970)이고, 그래프 판본은 그 이산 대응물이다. 미분기하에서 넘어온 정리가 병렬 격자 분할기의 품질 보증서로 쓰이고 있는 셈이다. ↩

  3. 그 전에는 사람이 CAD 화면을 보며 손으로 영역을 나눴다. 분할 품질이 담당자의 미적 감각에 달려 있었고, 프로세서 수가 바뀌면 처음부터 다시 그려야 했다. 요즘 기준으로는 야근의 물리적 실체. ↩

  4. 그래서 네트워크 논문에서 λ2\lambda_2가 클수록 좋다는 서술이 반복되는데, 링크를 늘리면 당연히 커지므로 비용 제약 없이 이 값만 보는 것은 의미가 없다. “예산 mm개의 간선으로 λ2\lambda_2를 최대화하라”까지 가야 진짜 설계 문제다. ↩