【현대수학】 그래프 이론 (Graph Theory)

그래프 이론(graph theory)·네트워크 이론(network theory)

 

추천글 : 【현대수학】 현대수학 목차 

---

1. 기초 [본문]

2. 인과추론 [본문]

3. 기타 응용 [본문]

---

 

1. 기초 [목차]

⑴ 그래프의 구성 요소 

① V : 노드(정점, vertex)

② E : 엣지(간선, edge)

③ G : 그래프 

④ V(G) = {v₁, ···, v_n}

⑤ v_i ~ v_j : 엣지 e_ij가 v_i, v_j를 연결하는 경우 

⑵ 그래프 G의 차수 : 노드의 개수, 즉 |V(G)|

⑶ 그래프 G의 크기 : 엣지의 개수, 즉 |E(G)|

⑷ 노드 v_i의 차수(degree) : 노드 v_i에 연결된 엣지의 개수, 즉 deg(v_i)

① deg(v_i) = ∑_vi~vj 1

② δ(G)는 G의 노드의 차수 중 최솟값을, Δ(G)는 G의 노드의 차수 중 최댓값을 지칭

③ ∑ deg(v_i) = 2 | E(G) |

④ regular : 그래프 내 모든 노드의 차수가 동일한 경우

⑤ Eulerian graph : 그래프 내 모든 노드의 차수가 짝수인 경우 

⑸ 그래프의 종류

① 단순그래프(simple graph) : 두 노드 사이에 최대 한 엣지만 존재하며, 한 노드가 자기 자신과 연결되는 루프는 허용되지 않는 그래프

 

Figure. 1. 단순그래프

 

② 완전그래프(complete graph) : 그래프의 모든 노드쌍이 유일한 엣지로 연결돼 있는 그래프

 

Figure. 2. 완전그래프

 

○ strongly connected (= irreducible, communicable)

○ 그래프 내 임의의 노드 i에서 다른 임의의 노드 j로 도달할 수 있는 상태

○ 즉, 마르코프 체인 내 임의의 j에서 i로 reachable한지

○ 완전그래프를 구성하는 엣지의 수는 _NC₂ = N(N-1) / 2  

⑹ 서브그래프(subgraph) : V(H) ⊆ V(G)이고 E(H) ⊆ E(G)인 그래프 H 

① induced subgraph : G에서는 존재하지 않는 간선이 H에 새롭게 생기지 않는, 서브그래프 H 

② clique : 서브그래프가 완전그래프인 경우 

③ walk : v₀v₁, v₁v₂, ···, v_m-1v_m 엣지들로 연결된 v₀ → v₁ → ··· → v_m와 같은 경로

○ v₀를 initial vertex라고 하고, v_m을 final vertex라고 함 

○ walk를 구성하는 엣지의 개수를 length라고 함

④ path : 노드가 모두 고유한 walk

⑤ cycle : v₀ = v_m인 walk. 즉 모든 노드가 2개의 이웃을 가지는 clique 

⑥ forest : 사이클을 포함하지 않는 그래프 

⑦ tree : connected forest 

⑧ period : 특정 노드 i의 period는 노드 i에서 i로 향하는 모든 path의 최대공약수

○ 예 : 두 개의 노드 A, B가 있고 A=B와 같이 두 개의 엣지로 연결돼 있으면 각 노드의 period는 2 

⑨ aperiodic : 모든 노드의 period가 1인 것

○ irreducible일 때, 한 노드가 aperiodic이라면 다른 모든 노드도 aperiodic

○ 예 : 각 노드가 자기 자신으로 향하는 walk가 있으면 aperiodic

⑩ regular 

○ regular ⊂ irreduicible

○ 어떤 자연수 k에 대해, transition matrix M의 거듭제곱 M^k의 모든 원소가 양수(즉, 0이 아닌 값)인 경우 

⑺ 그래프의 종류 

① undirected graph : 그래프의 엣지가 방향성이 없는 경우 

② directed graph : 그래프의 엣지가 특정 방향성이 있는 경우 

③ k-partite : 노드의 집합을 k개의 그룹으로 나눌 수 있고, 같은 그룹에 속한 노드들이 서로 인접하지 않을 때 

⑻ 네트워크의 중심성(centrality)

① degree centrality : 사회적 커넥션이 많은 사람들을 보여줌 

② closeness centrality : 소셜 네트워크의 중심이 누구인지를 나타냄 

③ betweenness centrality : social circle에 연결된 사람들을 나타냄 

④ eigenvector centrality : 네트워크에서 영향력 있는 사람들을 나타냄

⑼ 인접행렬(adjancy matrix) : A로 표시 

① 정의 : 노드의 개수를 n이라 할 때 n × n 인접행렬은, A_i,j = 1 (if v_i ~ v_j), A_i,j = 0 (otherwise)로 정의

 

출처: 이미지 클릭

Figure. 3. 인접행렬의 예시

 

② 각 노드와 실수값을 연결하는 함수 f 

 

출처: 이미지 클릭

Figure. 4. 함수 f의 예시

 

③ 다음 관계식이 성립함 

 

 

④ symmetrically normalized adjacency matrix : Ã = D^-1/2AD^-1/2 (단, D_ii = d(v_i))

⑽ 근접행렬(사건행렬, incidence matrix) : ∇로 표시 

① undirected graph의 근접행렬 : B_i,j = 1 (if vertex v_i is incident with edge e_j), B_i,j = 0 (otherwise)로 정의

 

 

출처 : 이미지 클릭

Figure. 5. 근접행렬 예시

 

② directed graph의 근접행렬

 

 

③ 노드가 행, 엣지가 열인 경우(예 : Fig. 5)와 엣지가 행, 노드가 열인 경우(예 : Fig. 6)가 모두 사용되고 있음

⑾ 라플라스 행렬(Laplacian matrix)

① 개요

○ 정의 : L = ∇^T∇ = D - A (단, D_ii = d(v_i)) 

○ multiplicity : 연속적인 서브그래프의 개수 

 

출처: 이미지 클릭

Figure. 6. 라플라스 행렬 예시

 

○ 위의 경우 ∇는 다음과 같음 

 

Matrix([
    [1, -1,  0,  0],  # e1: v1 -> v2
    [1,  0, -1,  0],  # e2: v1 -> v3
    [0,  1, -1,  0],  # e3: v2 -> v3
    [0,  1,  0, -1]  # e4: v2 -> v4
])

 

② 라플라스 행렬의 변형

○ normalized graph Laplacian : L_n = D^-1/2LD^-1/2 = I - D^-1/2AD^-1/2. symmetric, semi-definite positive

○ Markov chain의 전이 행렬(transition matrix) : L^t = D^-1A 

○ random-walk graph Laplacian : L_r = D^-1L = I - L^t = D^-1/2L_nD^1/2

③ 특징 1. L은 고유치 0을 가지고 있음 : L1_n = 0

○ k개의 분리된 그래프가 있으면 0의 고유값이 k개가 존재함

○ 고유값이 0에 가까울수록 그래프가 더 잘 연결되어 있음을 나타냄

○ Fiedler 벡터 : λ₁ = 0 다음으로 두 번째로 작은 고유값에 대응하는 고유벡터. 그래프의 전체적인 구조를 나타냄

④ 특징 2. Laplacian as an operator

○ (Lf)(v_i) = ∑_vj~vi (f(v_i) - f(v_j)) : Fig. 4 참고

 

 

⑤ 특징 3. L은 대칭이고 양반정부호 행렬(positive semi-definite matrix)

○ 2차 형식 : f^TLf = ∑_{ei,j, i < j} (f(v_i) - f(v_j))² = (1/2) ∑_ei,j (f(v_i) - f(v_j))² ≥ 0

 

 

○ Fig. 4의 예시에서 f^TLf = 9.27 

○ 즉, L의 모든 고유치가 0보다 크거나 같은 실수

○ f 대신 행렬 p를 넣는 경우 tr(p^TLp)와 같이 표시함

⑥ 특징 4. Y = [y₁ y₂ ⋯ y_m] ∈ ℝ^k×m에 대하여 

○ tr(Y^TLY) = ∑_ei,j || y_i - y_j ||²

⑦ 특징 5. Rayleigh quotient

 

 

○ λ₂ = Fiedler 값(algebraic connectivity)은 값을 차이나게 하는데 필요한 에너지를 의미함 

○ 이 값이 크면 데이터들을 분리하는 게 어려워 전체적으로 잘 연결된 구조가 됨

○ 이 값이 작으면 데이터들을 분리하는 게 쉬워 약하게 연결된 구조, 별도의 클러스터로 군집화된 구조를 의미함

⑧ 응용 1. undirected weighted graph에서의 라플라시안 연산 

 

 

⑨ 응용 2. spectral clustering (ref)

○ 원래 문제 

○ 정의 : 그래프에서 최소 컷(min-cut)을 찾는 것. 클러스터 간 엣지 가중치는 최소화하면서, 클러스터 volume은 정규화된 분할

○ 군집 분할의 핵심은 서로 다른 군집 사이 연결(간선 가중치 합)은 작게 하고, 각 군집이 너무 작아지는 불균형은 막는 것

○ 단순히 군집 간 연결만 최소화(min-cut)하면 노드 몇 개만 떼어내는 자명한 분할이 나오기 쉬움. 그래서 cut을 군집의 크기(연결량)로 정규화한 normalized cut을 최소화

○ cut의 정의

 

 

○ volume의 정의

 

 

○ 2-cluster optimization problem 

 

 

○ multi-cluster optimization problem

 

 

○ spectral clustering은 다음과 같은 클러스터 레이블의 one-hot encoding X ∈ {0, 1}^N×K를 찾는 것과 동일함

 

 

○ 라플라시안 행렬을 이용한 풀이 

○ 문제 정의

 

 

○ y^TDy = 1 조건이 필요한 이유 : 이 조건이 없으면 자명한 해 y = 0가 존재하고, 임의의 y ≠ 0에 대해서 목적함수의 값을 작게 만드는 cy, 0 ≤ c < 1이 존재함 

○ y^TD1 = 0 조건이 필요한 이유 : 이 조건은 y ≠ 1과 필요충분조건 (orthogonality). 이 조건이 없으면 목적함수의 최솟값은 언제나 0이고 언제나 y = 1 (∵ 라그랑주 승수법)

 

 

○ 원래 spectral clustering 문제에서 one-hot constraint를 완화하고 X^TDX = I 조건을 추가하면 이 풀이와 동일해짐 

○ 단계 1. 주어진 n개의 데이터 포인트들 사이의 거리를 계산하여 n × n 크기의 인접 행렬 A를 만듦. 가우시안 커널을 많이 이용 

 

 

○ 단계 2. 인접 행렬을 기반으로 Laplacian 행렬을 계산 : L_n 혹은 L_r도 사용됨 

○ 단계 3. Laplacian 행렬의 가장 작은 k개의 고유값과 대응되는 고유 벡터 행렬 W = [ω₂, ···, ω_k] ∈ ℝ^n×k를 계산. λ₁ = 0에 대응되는 ω₁ = 1은 자명하므로 제외  

○ 단계 4. n개의 데이터는 k차원으로 자연스럽게 임베딩됨 : Y = W^T = [y₁, ⋯, y_n]의 각 열벡터

○ 단계 5. Y의 열벡터를 K-means clustering 등으로 클러스터링 수행 

⑩ 응용 3. 라플라스 행렬를 푸리에 변환 연산자로 사용할 수 있음 (예 : G-FuNK)

⑿ 차수 분포(degree distribution) : 전체 노드 중 차수가 k인 노드의 비율, 즉 P(k) = N_k / |V(G)|

⒀ 거리(distance) : 두 노드를 연결하는 가장 짧은 path의 길이. 그러한 path가 존재하지 않으면 거리는 ∞으로 정의

⒁ 클러스터링 계수(clustering coefficient) : 특정 노드의 차수를 k_i라고 하고, 그 노드와 연결된 주변 노드들끼리 연결된 엣지의 수를 e_i라 할 때

 

 

① 예를 들어, A가 B, C, D와 연결돼 있고, B-C, C-D 엣지가 추가로 있을 때, A에 대하여 e_i = 2, k_i = 3, C_i = 2 / 3

② k_i (k_i - 1) / 2 : 주변 노드들끼리 만들 수 있는 최대 엣지 개수 

③ C_i는 0에서 1 사이의 값을 가지며, 1에 가까울수록 해당 노드의 주변 노드들이 완전히 연결된 것을 의미함 

 

 

2. 인과추론 [목차]

⑴ 개요

① 인과추론에서는 DAG(directed acyclic graph)가 주로 사용됨 

○ 연구 질문 및 관련 개념 명확화

○ 가정을 명시적으로 식별

○ 편향 감소

○ 개별 효과 분리

○ 통계 분석을 위한 적절한 공변량 확인 

② 인과 구조를 나타내는 DAG를 데이터로부터 학습하는 일은 NP-hard

○ 따라서 DAG 공간(또는 Markov 동치류 공간)에서 greedy search로 근사

○ DAG 공간/동치류 공간은 매우 크기 때문에, 더 작은 순열(permutation) 공간에서 탐색하는 순열 기반 greedy search로 진행

○ 더 희소한(sparser) DAG를 만드는 방향으로 진행

⑵ Markov equivalence 

① DAG G의 Markov 특성 : parent node만이 child node의 분포를 결정하는 것 

② ℳ(G) : Markov 특성을 갖는 DAG G에서 비롯된 모든 확률 분포 

③ G₁과 G₂가 Markov equivalance라는 것 : ℳ(G₁) = ℳ(G₂)인 경우. G₁ ~ G₂로 표시

④ 필요충분조건 

○ skeleton : G₁과 G₂는 같은 구조를 가짐. 즉, 방향을 무시하고는 같은 edge 집합을 가짐

○ v-structure : G₁과 G₂는 같은 v-structure 집합을 가짐

○ (참고) v-structure : A → C ← B와 같은 구조에서 A, B는 연결되지 않은 것. 조건부 독립과 관련 (A not ⊥ B | C)

○ (참고) d-separation : A → (C, D, E) → B. information flow와 관련

⑤ MEC(Markov equivalence class) : 서로서로 Markov equivalence인 DAG들의 군 

○ 예 : X₂ = X₁ + ε ⇔ X₁ = X₂ - ε일 때, G₁: X₁ → X₂과 G₂: X₁ ← X₂는 구별할 수 없음

⑶ 인과모델(causal model)

① DAG G를 G = ([p], E)로 표시

② 노드 : [p] := {1, 2, ..., p}에서 각 노드 i는 i번째 확률 변수 X_i를 나타냄 

③ 간선 : 간선의 집합 E는 이들 확률변수 간의 인과관계를 나타냄

④ 분포 : X = (X₁, ..., X_p)이 구현된 샘플에 대한 확률밀도를 f로 표시 

⑷ 인과 마르코프 특성(causal Markov property)

① 정의 : f가 다음과 같이 인수분해되는 특성

 

 

② pa_G(i) : DAG G에서 노드 i의 부모 노드 집합

③ x_paG(i) : pa_G(i)에 대응되는 확률변수들의 값 

⑸ intervention

① I ⊆ [p]

○ intervention = perturbation (생물학에서 주로 사용)

○ intervention은 그래프 구조를 바꾸지 않고 노드의 값만 바꿈

○ perfect intervention : 완전 원인 제거 

○ imperfect intervention : 불완전 원인 제거

② I가 주어졌을 때 I-Markov 특성 (invariance) 

○ f^obs : perturbation이 없는 데이터의 확률밀도함수

○ f^I : perturbation을 가한 데이터의 확률밀도함수 

○ Markov 특성만으로 다음이 성립함 

 

 

○ (f^obs, f^I)가 Markov이고 임의의 j ∈ [p] - I에 대해 다음을 만족하는 경우 I-Markov라고 함 

 

 

③ I-MEC : MEC의 부분집합

⑹ 인과추론(causal inference)

① constraint-based method (예 : PC) 

○ 인과추론을 제약 충족 문제로 취급하여 인과 모형을 학습하고, 조건부 독립성 검정을 수행해 기저의 마르코프 동치류를 추정

② score-based method (예 : GES, GIES)

○ 각 마르코프 동치류에 점수를 부여하고, 페널티가 포함된 우도 점수를 탐욕적으로 최적화하여 DAG의 마르코프 동치류를 학습

○ 확률분포를 전제로 하므로 검정력(power)이 감소함 

③ 하이브리드 (예 : GSP, IGSP)

○ 조건부 독립성 검정을 기반으로 점수 함수를 구성

④ permutation 기반 causal structure learning 

○ 목표 1. intervention target을 찾기 위함 

○ 목표 2. causal graph 재구성

○ I-MEC 대신 I-essential (partially directed graph)을 고려 : 방향에 대해 identifiability가 없을 수 있기 때문

○ 가정 1. DAG(directed acyclic graph) 

○ 반례 : EGFR 리간드인 TGF-α, HB-EGF 등으 EGFR 신호전달 경로에 의해 영향을 받아 양성피드백 기전을 가지는 등 생물학적으로 이 가정마저 성립하지 않음

○ 가정 2. exogeneity : 시스템 변수는 intervention 변수의 부모 노드로 오지 않음

○ 가정 3. generic context : intervention 변수는 완전 연결(fully connected)

○ 가정 4. direct I-faithfulness (강한 가정) : 등호 조건과 intervention이 필요충분조건으로 연결

 

 

○ 가정 5. I-faithfulness assumption 

 

 

○ 가정 6. sparsest permutation principle : least edge가 실제 구조라는 추정. 오캄의 면도날과 유사함

 

약간 오타가 있음

Figure. 7. 상정한 인과 그래프 예시

 

○ JCI(joint causal inference) : x가 있을 때 어떤 인과추론 모델의 likelihood. f^joint(x, I)로 표시

 

 

○ 알려지지 않은 타겟 식별 가능성 정리

 

여기에서 C가 intervention target

 

○ IGSP(interventional greedy SP)

○ 입력 : f^obs, f¹, ···, f^k, I = {I¹, I², ···, I^k} (전혀 알려지지 않거나 부분적으로만 알려짐)

○ 출력 : π, I-MAP, I = {I¹, ···, I^k} (true target)

○ 목적함수

 

 

○ permutation은 intervention variable을 포함

 

 

3. 기타 응용 [목차]

⑴ 비둘기집의 원리 

⑵ 노드의 개수에 따른 고유한 그래프의 개수 : 거의 완벽하게 지수함수를 따름 

⑶ 다익스트라(Dijkstra) 및 Floyd 알고리즘 

⑷ 서브그래프의 개수를 세는 알고리즘 

⑸ 신념의 힘 

⑹ 사회적 네트워크 이론 혹은 six degress of separation

① 지구상의 임의의 두 사람을 골라도 최대 여섯 명만 건너면 아는 사이라는 것

② 증명 : 한 명이 평균 100명을 안다고 했을 때, 여섯 번을 건너면 100⁶ = 10억 명이 되어 비슷한 결론이 나옴 

⑺ Perron-Frobenius theorem

① 정리 1. transition matrix가 P인 finite Markov chain이 strongly connected이면 오직 1개의 정상상태 분포 q가 존재

○ 정상상태 분포는 Pq = q를 만족함

○ 예 : P = I (단위 행렬) ∈ ℝ^2×2이면 reducible 하기 때문에 정상상태 분포가 (x, 1-x) ∀x ∈ [0, 1]로 무수히 많음

 

 

② 정리 2. transition matrix가 P인 finite Markov chain이 strongly connected이고 aperiodic이면, 이를 Ergodic Markov chain이라고 하고 다음을 만족함

○ P_ij : 노드 j에서 노드 i로 전이될 확률. ∑_i P_ij = 1

○ 2-1. P^k의 i행 j열 원소 P_ij(k)는 k → ∞로 갈 때 q_i로 수렴 : 이때 i만 같으면 j와 무관하게 같은 값으로 수렴함을 주목 

○ 2-2. 초기상태 x₀에 무관하게 k번째 상태 x_k는 k → ∞로 갈 때 q로 수렴 

 

 

○ 예 : P = ((0, 1), (1, 0))이면 periodic (주기 = 2)이므로 π = (0.5, 0.5)라는 유일한 정상분포가 존재하지만 lim_k→∞ p^(k)이 2개로 구분됨 (예를 들어, p^(짝수) = (1, 0), p^(홀수) = (0, 1)이 될 수 있음)

 

 

⑻ 구글의 PageRank 알고리즘

① 단계 1. 웹페이지들을 그래프로 나타내고, 이를 Markov process transition matrix P로 표현 

② 단계 2. 텔레포트(teleportation) : sink 노드의 경우 다른 페이지로의 transition 확률을 1/n로 강제로 할당 : P → P'

③ 단계 3. P'' = (1 - α) P' + (α / n) 1 

○ 단, 1은 n × n에 1이 모두 채워진 형태

○ P'은 regular하다는 보장은 없지만, P''은 언제나 regular함이 보장됨

○ P''은 구글의 창업자 세르게이 브린과 래리 페이지가 정의한 Markov chain

④ 단계 4. P''x = x인 steady-state vector x를 탐색 

○ P''은 regular하므로 strongly connected이고, 이로 인해 steady-state가 유일하게 존재함 

○ 이때의 state-transition probability가 추천된 페이지의 중요도라고 할 수 있음

⑤ 사용자 맞춤 PageRank : 사용자 입력으로 텔레포트 분포 또는 그래프/후보집합을 바꿔서 사용자별 정상분포를 만듦

⑼ 4색 정리(four color theorem)

① 인접한 두 지역이 같은 색을 가지지 않도록 하기 위한 어떤 지도도 최대 4가지 색만으로 색칠할 수 있음

② 컴퓨터를 통해 모든 경우에서 4색 정리가 성립함을 확인함으로써 증명함

⑽ 한붓그리기 문제 혹은 쾨니히스베르크 다리 문제(Königsberg bridge problem)

① 어떤 그래프에서 각 노드를 한 번씩만 지나는 Eulerian path가 존재하려면 차수가 홀수인 노드가 0개이거나 2개여야 함

② 차수가 홀수인 노드가 2개이면 홀수 차수를 가진 두 노드 중 하나는 출발점, 다른 하나는 도착점이 됨

③ 쾨니히스베르크의 7개의 다리를 한 번씩만 모두 건너는 경로는 존재하지 않음

⑾ 램지 이론(Ramsey theory)

① 충분히 큰 그래프에는 반드시 특정한 구조(예 : 아는 사람들로 이루어진 완전 그래프, 모르는 사람들로 구성된 부분 그래프)가 존재함

② R(s, t) : s명의 모르는 사람들로 구성된 서브그래프 혹은 t명의 아는 사람들로 구성된 서브그래프가 반드시 존재하는 최소 노드 수

③ 정리 1. R(3, 3) = 6 : 임의의 6명 중에서는, 서로 친구인 3명이 있거나, 서로 친구가 아닌 3명이 존재. 경우의 수로 증명할 수 있음

④ 정리 2. R(3, 3, 3) = 17 

⑤ 정리 3. R(3, 3, 4) = 30

⑥ 정리 4. R(s, t)의 점화식 : R(s, t) ≤ R(s-1, t) + R(s, t-1) 

⑦ 정리 5. R(s, t)의 상한의 존재성 : R(s, t)의 점화식 및 수학적 귀납법으로 증명 (ref)

 

 

⑧ 정리 6. R_k(s₁, s₂, ···, s_k) ≤ R_k/2(R(s₁, s₂), R(s₃, s₄), ···, R(s_k-1, s_k))

⑿ 슐의 정리(Schur's theorem) 

① 임의의 k ≥ 2에 대하여, k-coloring 하에서 같은 색으로 칠해지고 x + y = z를 만족하는 (x, y, z)를 언제나 찾을 수 있는 {1, 2, ···, n}, n > 3이 존재한다는 정리. 램지 이론을 통해 증명

② 이를 페르마의 마지막 정리와 연결시켜, x^m + y^m = z^m (mod p)인 (x, y, z)의 존재성을 밝힘 

⒀ 에르되시-레니 무작위 그래프(Erdős–Rényi random graph)

① 무작위로 노드를 연결하는 단순한 규칙으로도 일정 임계점에서부터 매우 큰 그래프가 생성 

⒁ Steiner 트리 알고리즘

① 그래프 위에서 모든 단말을 연결하는 가장 비용이 적은 트리를 찾는 것

② NP-hard 

⒂ Goemans-Williamson (GW) algorithm 

① max-cut 문제, SDP(semidefinite programming), 근사 알고리즘

 

입력: 2024.10.01 19:44