29차시 · 정의와 표기

그래프와 그래프 신호

그래프 \(G=(V,E)\)에서 \(V\)는 꼭짓점 집합, \(E\)는 간선 집합이다. 이 차시는 방향·가중치·자기고리가 없는 유한 단순그래프를 다룬다.

간선 \(\{i,j\}\in E\)가 있으면 두 꼭짓점은 이웃이며 \(j\sim i\)로 쓴다. 이웃의 수 \(d_i\)를 차수라고 한다. 그래프 신호 \(x\in\mathbb R^{|V|}\)는 각 꼭짓점에 수 하나를 대응시킨 벡터이다.

\(P_4\)는 4개 꼭짓점을 일렬로 연결한 경로 그래프이다. \(C_4\)는 그 양 끝도 연결한 순환 그래프이다. 어떤 두 꼭짓점도 간선을 따라가는 경로로 이어질 때 연결 그래프라 한다. 같은 네 성분이라도 간선이 달라지면 이웃 관계가 달라진다.

29차시 · 정의와 표기

인접행렬·차수행렬·라플라시안

인접행렬 \(A\)는 이웃일 때 \(A_{ij}=1\), 아니면 0이다. 차수행렬은 \(D=\operatorname{diag}(d_1,\ldots,d_n)\)이고 라플라시안은 \(L=D-A\)로 정의한다.

즉 \(Lx\)의 한 성분은 자기 값과 이웃 값의 차이를 더한 값이다. 무방향 그래프에서는 \(A=A^T\)이므로 \(L\)도 대칭이다. \(\mathbf1=(1,\ldots,1)^T\)로 쓰며, \(\mathbf1^Tx\)는 신호 성분의 합이다.

29차시 · 계산과 논증

라플라시안 계산과 에너지 검산

\(P_4\)의 신호가 \(x=(1,2,0,1)^T\)이다. ① \(Lx\)의 네 성분을 구하라. ② \(x^TLx\)와 간선별 차이의 제곱합을 각각 계산하라. ③ \(Lx\)의 성분 합이 0인 이유를 설명하라.

29차시 · 정의와 표기

그래프 푸리에 모드와 확산

대칭행렬 \(L\)의 정규직교 고유벡터 \(q_i\)를 그래프 푸리에 모드라고 한다. 신호는 \(x=\sum_i c_iq_i\), \(c_i=q_i^Tx\)로 분해한다.

단위 길이로 맞춘 모드에서 고윳값은 이웃 간 차이의 제곱합이다. 작은 고윳값을 저주파, 큰 고윳값을 고주파라고 부르는 이유이다.

이산 확산은 \(x_{n+1}=(I-\eta L)x_n\)으로 값을 갱신하는 과정이다. \(\eta>0\)는 한 단계의 변화량을 정한다. 연속시간 확산 \(x'(t)=-Lx(t)\)과 구별한다.

29차시 · 설명과 유도

평균 보존과 이산 확산의 수렴 조건

\(\mathbf1^TL=0\)이므로 확산 뒤에도 전체 합과 평균이 같다. 모드 \(q_i\)의 계수는 한 단계마다 다음 배율을 받는다.

간선이 있는 연결 그래프에서 평균 성분을 제외한 모든 모드가 사라지려면 \(|1-\eta\lambda_i|<1\)이어야 한다. 이를 동시에 만족시키는 조건은

이 조건은 수렴의 조건이다. 매 단계 값을 이웃 값의 음이 아닌 가중평균으로 해석하려면 추가로 \(\eta\le1/d_{\max}\)를 확인한다.

29차시 · 계산과 논증

평균은 보존되는데 값이 발산할 수 있을까?

\(C_4\)에서 \(q=(1,-1,1,-1)^T\)는 \(Lq=4q\)를 만족한다. \(x_0=q\)에서 이산 확산을 시작한다.

① \(\eta=1/4,1/2,3/4\)일 때 \(x_n\)을 각각 구하라. ② 세 경우 모두 평균이 보존되는지, 모두 수렴하는지 설명하라. ③ 연속시간 확산과 비교하라.