Graph-tool 논문4

Sylen·2025년 1월 4일

아래 튜토리얼/설명은 Tiago P. Peixoto의 논문 "Nonparametric Bayesian inference of the microcanonical stochastic block model"(arXiv:1610.02703v4 (2018)) 내용을 한글로 정성껏 풀이한 것입니다.
문서의 주요 개념인 "마이크로캐논(microcanonical) 확률적 블록 모델(SBM)"과 "비모수적(Nonparametric) 베이esian 추론"을 중심으로, 왜 이 모델이 필요하고 어떻게 구성·추론하는지, 그리고 전통적인 '캐논(canonical)' 모델과 어떻게 다른지를 수식·원리를 곁들여 상세하게 설명해 보겠습니다.

1. 도입: 네트워크 구조 분석과 SBM

1.1 네트워크 구조 분석의 배경

  • 대규모 소셜, 생물학, 기술, 교통 네트워크 등은 단순 관측만으로 숨겨진 모듈 구조(커뮤니티, 블록)를 파악하기 어렵다.
  • 전통적으로는 “모듈성(modularity) 최대화” 등의 휴리스틱 기법이 많이 제안되었으나, (a) 잡음(noise)과 구조를 명확히 구분 못하거나, (b) 큰 규모에서 소규모 그룹을 놓치거나, (c) 다양한 해가 동시에 존재하는 문제가 있었다.

1.2 확률적 블록 모델(SBM)의 아이디어

  • SBM(Stochastic Block Model)은 노드를 여러 그룹(블록)에 할당하고, 그룹 간 연결 확률·기댓값을 바탕으로 네트워크를 생성하는 모델.
    • 노드 (i)가 그룹 (b_i)에 속해 있을 때, 그룹 (r)와 (s) 간의 간선 발생 확률(또는 기대 간선 수)을 매개변수로 설정.
    • 이 모델에 데이터를 “fit”함으로써, 노드별 어떤 그룹에 속하는지 추론 → 커뮤니티 구조를 베이지안적·확률적으로 찾을 수 있음.
  • SBM은 전통적으로 “간단한(canonical) 확률 분포”를 사용(예: 포아송, 베르누이). 그러나 여기서는 “마이크로캐논(microcanonical) 버전”을 강조.

1.3 마이크로캐논(Microcanonical) vs. 캐논(Canonical)

  • 캐논(canonical) 모델: 연결(간선 수)이 ‘평균(expected)’에 의해 조절. 예) 포아송 파라미터나 확률값 등으로 인해, 실제 네트워크가 가진 수많은 세부 구조(정확한 차수, 정확한 블록 간 에지수 등)는 평균적으로만 맞출 뿐, 오차 허용.
  • 마이크로캐논(microcanonical) 모델: 네트워크가 가져야 할 “정확한” 제약(정점별 차수, 블록 간 에지 수 등)을 딱 고정(hard constraint). 즉, 해당 제약을 절대 위반하지 않는 범위에서만 네트워크를 생성하는 모델.
    • 이는 (정점 차수·블록 간 에지수 등의) 결합 분포를 “단 하나도” 어긋나지 않도록 구성하므로, 특정 네트워크 구조(예: 실제 네트워크에서 관측된 “정확한” 차수나 블록별 에지 수)를 그대로 존중하는 무작위 그래프 생성이 가능.

1.4 비모수적(Nonparametric) 베이지안 추론

  • B(블록 수)나 각 블록의 크기 등을 사전에 고정하지 않고, 데이터를 통해 자동 결정(추론)하고자 함.
  • 이를 위해 “사전확률(prior) → 사후확률(posterior)” 관점에서 모델 파라미터(블록 할당, 에지 분포 등)를 추론하되, 모델 복잡도에 대한 과적합(overfitting)을 피하도록 주의(Occam’s razor).
  • 마이크로캐논 모델에서의 장점: “하드 constraint” 때문에, 마진라이클리후드(marginal likelihood) 계산이 더 간단(또는 정확)해짐.

2. 마이크로캐논 “Degree-Corrected” SBM: 수식과 원리

논문에서 제안된 모델은 Degree-Corrected 버전입니다. 즉, 각 노드는 서로 다른 차수를 가져도 좋도록 “노드별 degree”를 고정한 상태로 블록 구조를 반영.

  1. 모델 파라미터

    • ( b = {b_i} ): 노드 (i)가 속한 블록(그룹) 인덱스. (b_i \in [1, \dots, B]).
    • ( k = {k_i} ): 각 노드의 “정확한” 차수(무방향에서). (유향이면 in-degree, out-degree 각각)
    • ( e = { e_{rs} }): 블록 (r)와 (s) 사이의 정확한 에지 개수(단, (r=s)이면 2배).

  2. 네트워크 생성 과정(아이디어)

    • 노드 (i)에 대해, 차수 (k_i)만큼 “하프-엣지(stub)” 부여.
    • 그런 뒤, “블록 (r)와 (s)” 사이에 정확히 (e_{rs})개의 하프-엣지 쌍이 연결되도록 무작위 매칭(구성).
    • 이로써, 한 노드가 가지고 있는 하프-엣지는 꼭 (ki)개를 연결하게 되고, 블록 간 에지 수도 정확히 (e{rs})를 만족.

  3. 확률 수식

    • 각 그래프 (A)가 주어졌을 때, 그 그래프가 ((b,k,e)) 파라미터를 가진 모델에서 나올 확률:
      [
      P(A \mid b,k,e) \;=\; \frac{\Xi(A)}{\Omega(e)}.
      ]
      • (\Xi(A)): 그래프 (A)가 나타낼 수 있는 하프-엣지 쌍의 내부 순열 개수
        (\quad \Xi(A) = \prod{i} k_i! \,/\, \bigl(\prod{i<j} A{ij}! \prod{i} A_{ii}!!\bigr))
        (노드별로 (k_i)! 가지 방법 - 간선 중복·자기 루프 고려)
      • (\Omega(e)): 블록 간 에지 개수 (e)를 만족하도록 하프-엣지를 매칭할 수 있는 총 경우의 수
        (\quad \Omega(e) = \prod{r} e_r! \,/\, \bigl(\prod{r<s} e{rs}! \prod{r} e{rr}!!\bigr))
        (여기서 ( e_r = \sum_s e        {rs} ))

  4. 멀티에지, 자기루프

    • 이 설정은 다중 간선과 자기루프도 가능하게 하지만, 희소 그래프( (E \sim O(N)) )라면 중복 간선·자기 루프 발생 확률은 (1/N) 비율로 작아져 대부분 무시 가능.

  5. Non-degree-corrected SBM은 위에서 노드별 차수가 비슷하다고 가정한 “특수 케이스”.

    • 그 경우 블록 내에서 노드 차수 분포가 근사적으로 포아송이 되어버려, 이질적인(ne) 차수를 잘 모델링 못함.

3. 비모수적 베이지안 관점: 전체 사후확률

이 모델을 데이터(관측된 네트워크) (A)에 적용해, 노드들의 블록 할당 (b) 등을 추론하려면?

  1. 전체 공동분포
    [
    P(A,k,e,b) \;=\; P(A \mid k,e,b)\,P(k \mid e,b)\,P(e \mid b)\,P(b).
    ]

    • 여기서 (P(A \mid k,e,b))는 위 (2.3) 식이고, 나머지는 “사전분포(prior)”로 설정.

  2. 사후분포: (P(b \mid A))
    [
    P(b \mid A)
    \;=\;
    \frac{ P(A,b) }{ P(A) }
    \;=\;
    \frac{ \sum{k,e} P(A,k,e,b) }{ \sum_b \sum{k,e} P(A,k,e,b) }.
    ]

    • 마이크로캐논 특성상, (A)가 정해지면 (k,e)가 정확히 (\hat{k}(A), \hat{e}(A,b))로 결정됨(하드 constraint).
    • 결과적으로 마진라이클리후드 계산 시, 적분(or 합)이 간소화됨.

  3. MDL(최소기술길이) 해석

    • (-\log_2 P(A,k,e,b) = S + L) 형태로, 데이터 기술 길이 + 파라미터 기술 길이로 분해.
    • 이를 최소화하는 (b)를 찾는 것은 “사후확률을 최대화”하는 것과 동치.
    • 또한, 모델이 너무 복잡해지면(블록 수 (B) 커지면) 파라미터 부분이 커져서 벌칙(penalty)이 부과 → 과적합 방지.

  4. Sampling(표본추출) vs Optimization(최적화)

    • 사후분포를 전부 샘플링(MCMC)하면 다양한 해를 모두 반영, 편향은 줄어드나 분산은 커짐(너무 많은 후보).
    • 최대화(1개 해) 접근은 명확하지만, 편향이 존재할 수 있음.
    • 실제론 목표(새로운 데이터 예측 vs. 현재 데이터 구조화)에 따라 선택적.

4. 사전분포(priors) 설정: 노드 그룹, 차수, 블록간 에지

논문에서는 “단순한(무정보) 균등분포”를 한 단계 더 깊은(계층적, hyperprior)으로 교체해 성능을 개선하는 과정을 제시.

4.1 노드의 그룹 할당에 대한 prior

  • 노드 수 (N), 그룹 수 (B) (불명).
  • 만약 “완전 무작위” (P(b)\propto B^{-N}) 같은 걸 쓰면, 모든 그룹 크기가 비슷하다는 문제.
  • 대신, 노드별 그룹 할당은 group size n={n_r}가 정해지면:
    [
    P(b \mid n)
    \;=\;
    \frac{\prod_r n_r!}{N!}.
    ]
  • 그리고 group size 분포 (P(n \mid B))도 균일 분포로 두되, “빈 그룹(0명)”은 배제(이게 중요).
  • 이렇게 하면 nonparametric이 되면서도, 그룹 크기에 대한 불필요한 가정 완화.

4.2 차수( degree ) 분포에 대한 prior

  • 마찬가지로, NDC-SBM(비차수 보정)은 각 그룹 내에서 차수가 포아송스럽게 몰리는 단점.
  • 그래서 arbitrary degree 반영 위해, “uniform”한 차수 분포(“모든 ((k1,\dots,k{nr})) 동일 확률”)를 먼저 가정한 뒤(이는 1차 prior) → 거기에 추가 hyperprior(“q(m,n)”)를 붙여서, 훨씬 유연한 분포를 형성.
  • 결과적으로, 실제 네트워크의 이질적 차수 분포에 가깝게 학습 가능.

4.3 블록 간 에지 분포 prior

  • 블록 (r)와 (s) 사이의 에지 수 (e_{rs})가 어떻게 분포하는지도 prior 필요.
  • 단순 균등분포(“모든 ({e_{rs}}) 동일”)를 쓰면, resolution limit(최대 (\sqrt{N}) 그룹) 문제가 발생 → 많은 소규모 그룹을 포착 못 함.
  • Nested(계층) SBM으로 상위 레벨에서도 SBM 형태의 다중그래프를 생성, 이를 반복.
    • 상위 레벨로 갈수록 노드(그룹) 수는 작아지나 간선 밀도는 커진다.
    • 마이크로캐논 uniform NDC-SBM을 상위 priors로 쌓아 올려서, 더 많은 그룹 분해가 가능해짐.

5. 캐논(Canonical) SBM과의 관계

  • 전통적 “캐논 SBM”은 블록 간 연결이 “평균적으로” (\lambda_{rs}\theta_i\theta_j) (포아송) 등으로 정해지고, 차수·블록 간 에지수가 기대값만 고정.
  • 마이크로캐논 모델과 캐논 모델은 “차수·에지수가 충분히 클 때” 근사적으로 동일(ensemble equivalence), 하지만 작은 네트워크나 sparse 상황에선 차이가 큼.
  • 또한, 베이지안으로 접근 시, 캐논 모델의 (\theta, \lambda) 적분(마진라이클리후드)을 특정 방식(파라미터화)에 따라 하면 마이크로캐논과 같은 식이 나오기도 함 → 본질적으로 같을 수도.
  • 결국, 어떤 매개변수화를 택하느냐(예: (\hat\theta_r = n_r) vs (\hat\theta_r=1))가 달라서, priors 해석이 달라짐.

6. 최대 그룹 수 문제(Resolution Limit)와 계층 priors의 개선

  • 비정보 prior(균등 등)을 쓰면, 모형이 “너무 많은 그룹”을 나누려 할 때, 큰 패널티가 생겨 (\sqrt{N}) 정도까지만 식별 가능 → 작은 그룹 다 놓침.
  • 그러나 계층 priors( nested SBM )를 적용하면, (\frac{N}{\ln N})까지 그룹 식별 가능 범위가 넓어져서, 더욱 세밀한 모듈 구조를 잡아냄.

7. 실제 추론 알고리즘: MCMC

7.1 전반적 아이디어

  • 사후분포 (P({b_l} \mid A))를 MCMC로 샘플링. ( “({b_l})”는 여러 레벨의 블록 파티션 )
  • 하위 레벨(원본 그래프)의 노드 그룹 이동 → 상위 레벨도 일관성 유지하며 변화 → 메트로폴리스-헤이스팅(MH)으로 수용/거부.
  • 이 과정에서 하위 레벨이 가장 많은 노드(원본 그래프), 상위 레벨로 갈수록 그룹 수 감소(그룹의 그룹).

7.2 핵심: 이동 제안(move proposals)과 수용률

  • 노드 (i)가 현재 그룹 (r)에서 (s)로 옮길 확률을 어떻게 제안?
  • 무작정 균등제안 시 비효율(거의 거부).
  • 논문에서는 노드 이웃 혹은 블록 연결정보 기반으로 “smart proposal”을 사용 → 수렴 빠름.

7.3 초기화

  • “각 노드를 자기만의 그룹에 둔 상태”에서부터, 단계적으로 그룹 병합 + 노드 재배치 병행(“Agglomerative” 기법).
  • 국소최적에 갇히는 문제 완화.

7.4 샘플링 vs. 최대화

  • 샘플링 모드: (\beta=1)에서 MH로.
  • 최대화 모드: (\beta\to\infty)로, 가장 큰 사후확률(혹은 가장 낮은 MDL) 찾는 탐욕 알고리즘처럼 작동.

8. 모델 비교와 실제 데이터 실험 결과

  • 논문에서는 “NDCSBM(비차수보정) vs DC-SBM(차수보정)”을 실제 데이터에 적용 비교.

    • 일관적 결과: DC-SBM(특히 hyperprior를 사용) 모델이 대부분 더 낫게 적합.
    • 다만, 특정 네트워크(차수분포가 좁은 경우)에선 NDC-SBM이 더 나을 수도.

  • 예: Political blogs(유향), Zachary’s karate club 등에서, 단순 NDC-SBM은 주로 “노드 차수”에 따라 그룹화하려 하고, DC-SBM은 실제 “정치 성향” 구분(커뮤니티)을 보다 정확히 포착.

  • 해석: 차수 이질성이 큰 네트워크에서, degree-correction이 없는 모델은 “차수 클러스터링”을 커뮤니티라고 오인하기 쉬움 → DC-SBM이 진짜 블록 구조를 잘 반영.

9. 요약 및 의의

  1. Microcanonical(미시정역) DC-SBM

    • 네트워크의 “노드별 정확 차수”와 “블록 간 정확 에지수”를 하드로 고정.
    • 베이지안 관점에서, 이로 인해 마진라이클리후드 계산이 단순화되고, 보다 깊은 계층적 priors를 도입하기 쉽다.

  2. Nonparametric

    • 블록 수 (B)를 사전 지정하지 않고, 데이터에 맞추어 적절히 결정(Occam’s razor 원리).
    • 그룹 크기, 차수 분포, 블록 간 에지 분포에 대해 계층적(하이퍼) priors 설정 → 더 유연.

  3. 효율적 MCMC

    • 전통적 기법(O(EB), O(EB^2) 등)보다, 여기선 (\mathcal{O}(E))로 스케일 → 대규모 네트워크에서도 많은 그룹 식별 가능.

  4. 캐논 vs. 마이크로캐논 등가성

    • 특정 파라미터화·prior 아래서는 동일 분포를 만들 수 있음 → 둘 중 선택은 주관적(모델링 취향).
    • 다만 microcanonical이 “정확 제약”을 강제하므로, 해석상 장점이 있음.

  5. 실증 예시

    • 다양한 실제 네트워크에서, 차수보정 DC-SBM + 계층 hyperprior가 대체로 더 좋은 설명력, 더 작은 MDL 값.

10. 결론

마이크로캐논 SBM을 사용하면,

  • 하드 제약(정확 차수, 정확 블록 에지수)을 가정하여 네트워크를 모델링,
  • 베이지안으로 접근함으로써, 블록(커뮤니티) 구조와 모델 복잡도에 관한 자연스러운 탐색(추론)이 가능,
  • 계층 hyperprior로 확장하면, 큰 네트워크에서도 정밀한 구조(작은 그룹 포함)를 놓치지 않음.

논문에서 제시된 기법은 기존의 SBMs가 갖는 한계(특히 “단순균등 priors”의 under/over-fitting 등)와 큰 그룹·작은 그룹 식별 문제를 베이지안 계층화로 해결한 점이 핵심이다. 또한, 전통적인 캐논 모델과의 수학적/이론적 등가성을 일정 부분 확보하여, 모델링 편의에 따라 양자를 자유롭게 택할 수 있게 했다.

결과적으로, 이 방법론은 대규모 네트워크에서 “유의미한 모듈 구조”를 자동 찾고, 모형 선택(모델 비교)까지 이뤄질 수 있도록 하는 강력한 비모수적 베이지안 접근을 제시한다. 도시·교통·사회 등 복잡계 네트워크 분석에 널리 응용될 가능성이 높다.

아래 튜토리얼은 Karrer & Newman(2010)의 논문 "Stochastic blockmodels and community structure in networks" (arXiv:1008.3926v1) 내용을 한글로 풀이·정리한 것입니다. 왜 기존 블록 모델에 노드별 차수(heterogeneous degrees)를 고려(=Degree-Corrected)해야 하는지, 그리고 그것이 커뮤니티 탐색(community detection)에 어떤 의미가 있는지에 대해 최대한 자세하고 친절하게 설명해보겠습니다.

1. 문제 제기와 배경

1.1. 확률적 블록 모델(SBM)과 커뮤니티 탐색

  • 네트워크를 분석할 때, “노드를 여러 그룹으로 분할하고, 그룹 간 연결 특성”에 따라 네트워크를 생성·설명하려는 아이디어가 Stochastic Block Model(이하 SBM).
  • 예:
    • 노드 (i)의 그룹이 (gi)이고, 그룹이 (K)개라면, 그룹 (r)와 (s) 사이의 연결(간선) “발생 확률”이나 “기댓값”을 (\psi{rs}) 또는 (\omega_{rs})로 둔다.
    • 이를 통해 네트워크(간선 행렬)를 생성하는 “확률적” 모델.
  • 전통적 SBM은 “가장 단순”하게 각 그룹 간 동일한 간선 확률((\psi_{rs}))만 다르고, 노드별 차수는 그룹 내에서 비슷하다고 가정. 따라서 실제 네트워크에서 보이는 ‘차수 분포의 이질성(heterogeneous degrees)’을 잘 반영하지 못해 문제가 생긴다.
    • 예: 어떤 노드는 차수가 매우 크고, 다른 노드는 매우 작아도, “같은 그룹이면 평균 정도의 차수로만 취급”되어 실제 데이터와 큰 괴리가 생긴다.

1.2. 본 논문(“Degree-Corrected” 블록 모델)의 의의

  • “Degree-Corrected Stochastic Block Model”(이하 DC-SBM)은 전통적 SBM에 “노드별 차수”를 명시적으로 반영하는 방식.
  • 이렇게 하면 “노드가 이미 높은 차수를 가졌기 때문에 연결이 많다”는 구조적 특징을 모델에서 직접 반영 가능 → 보다 현실적인 적합 + 커뮤니티 구조를 제대로 탐색할 수 있음.

2. 전통적(Non-degree-corrected) 블록 모델 재검토

2.1. 모델 정의 (무향, 멀티에지 가능, 자기루프 가능으로 확장)

  • 노드 (n)개, 그룹 수 (K). 그룹 배정 함수 (g_i) ((i)번 노드가 어느 그룹?).
  • 그룹 (r)와 (s) 사이의 “기댓값”을 (\omega{rs})로 두고, 실제 간선 수 (A{ij})는 포아송 분포로 모형화(멀티에지 허용).
  • 무작위 그래프 (G)가 생성될 확률:
    [
    P(G \mid \omega, g)
    \;=\;
    \prod{i<j}
    \frac{(\omega    {gi g_j})^{A{ij}}}{A{ij}!} \exp(-\omega{gi g_j})
    \;\times\;
    \prod_i
    \frac{(\tfrac12\,\omega    {gi g_i})^{A{ii}/2}}{(A{ii}/2)!}\exp\bigl(-\tfrac12 \,\omega{g_i g_i}\bigr).
    ]
  • 이 모델에서, 그룹 내 노드 수가 (\,nr), 그리고 그룹 (r)-(s) 간 총 에지수가 (m{rs})((r=s)일 땐 2배 계산)라 하면, 최대우도추정 시
    [
    \hat{\omega}{rs} \;=\; \frac{m{rs}}{n_r\,n_s}.
    ]
  • 그 결과, (불필요한 상수 제외) 모델의 로그우도(또는 목적함수)를
    [
    L(G \mid g)
    =
    \sum{r,s} m{rs} \, \ln!\Bigl(\frac{m_{rs}}{n_r n_s}\Bigr).
    ]
    로 표현 가능.

2.2. 왜 차수를 무시하면 문제가 생기나?

  • 이 목적함수는 “모든 그룹 노드가 대체로 같은 차수를 갖는다”는 전제를 은연중에 깔고 있음.
  • 실제로, 이질적인 차수가 있는 네트워크(예: 어떤 노드는 차수가 매우 큼)가 주어지면, 이 모델은 그걸 “고차수 노드끼리 묶고, 저차수 노드끼리 묶는” 식으로 해결하려 하며, 정작 우리가 찾고 싶은 “커뮤니티 구조(같은 성향·역할)”가 뒤섞일 우려가 있음.
    • 즉, 차수가 큰 노드를 같은 그룹으로 묶는 것이 모델 관점에서 더 우도(확률)를 높이기 때문.

예시:

  • Karate 클럽(Zachary’s karate club) 네트워크에서, 전통적 블록 모델은 노드를 “고차수 vs. 저차수”로 나누는 결과를 내버림 → 실제 분열된 두 파벌과는 다른 분할.
  • Political blog 네트워크에서도 “차수 큰 그룹 / 작은 그룹”으로 갈려버리는 경향.

3. Degree-Corrected SBM

3.1. 모델 정의: 노드별 차수 파라미터 (\theta_i)

  • 아이디어: “노드 (i)가 차수 (\thetai)에 해당하는 ‘비례도’를 가지게 하고, 그룹 (g_i)가 (\omega{g_i g_j})를 통해 연결이 결정되되, (\theta_i\theta_j)만큼의 가중이 곱해지도록.”
  • 수식으로:
    [
    P(G \mid \theta, \omega, g)
    \;=\;
    \prod{i<j}
    \frac{(\theta_i \,\theta_j\,\omega    {gi g_j})^{A{ij}}}{A{ij}!}
    \exp(-\theta_i\,\theta_j\,\omega    {g_i g_j})
    \;\times\;
    \cdots
    ]
  • 정규화: (\sum_{i \in r} \theta_i = 1) (각 그룹 (r)에 속한 (\theta_i) 합이 1)로 설정하면, 그룹별 총차수 등 모형이 적절히 분산.

3.2. 최대우도추정 결과

  • (\hat{\theta}i = \frac{k_i}{\kappa{gi}}), 여기서 (k_i)는 노드 (i)의 (실제) 차수, (\kappa_r = \sum{i \in r} k_i).
  • (\hat{\omega}{rs} = m{rs}). ( (m_{rs})는 그룹 간 에지수 )
  • 이렇게 하면, 실제로 그룹 (r)-(s)간 에지 기대치 (\omega_{rs})를 맞추면서도, 노드 (i) 차수가 (\theta_i\theta_j)로 잘 반영됨.

3.3. 로그우도(목적함수) 식

  • (불필요한 상수 제외)
    [
    L{\mathrm{DC}}(G \mid g)
    \;=\;
    \sum    {r,s} m{rs}\,\ln \Bigl(\frac{m{rs}}{\kappa_r\,\kappa_s}\Bigr).
    ]
  • (\kappa_r)는 “블록 (r) 내 모든 노드 차수 합.”
  • 전통적 모델과의 차이는 (n_r) 대신 (\kappa_r)가 들어간다는 점. 차수가 다양한 경우 이 차이가 굉장히 큼.

3.4. 의미

  • 이제 “노드가 고차수”라는 점은 이미 (\theta_i)에서 반영 → 모델이 “고차수끼리만 그룹짓기” 식으로 오판하지 않음.
  • 따라서 실제 커뮤니티 구조(관심 있는 모듈성)를 제대로 추론 가능해짐.

4. 구현 및 알고리즘

4.1. 간단한 로컬 탐색 / 휴리스틱

  • 위에서 유도된 목적함수(로그우도)를 최대화하면, 그룹 할당 (g) 최적해를 찾는다.
  • Kernighan–Lin 스타일의 휴리스틱:
    1. 임의(또는 다른 방법)로 (K)개 그룹에 배정.
    2. “단 한 번씩만 노드를 옮기는” 과정으로, 각 노드가 이동 시 얻는 로그우도 증가(또는 감소 최소)를 순차적으로 적용.
    3. 모든 노드가 한 차례 이동하면, 그 중 최대 점수 상태를 골라 다음 iteration 시작.
    4. 더 이상 개선이 없으면 정지.
  • 로컬 최적에 빠질 수 있어 여러 랜덤 시드를 시도.

4.2. 시간 복잡도

  • 노드가 그룹 바꿀 때, 식 (25)를 쓰면 (\mathcal{O}(K + k_i)) 혹은 (\mathcal{O}(K(K + \langle k \rangle)))로 계산 가능 → 큰 그래프에서도 구현 가능.

5. 실제 데이터 적용 사례

5.1. Karate club 네트워크

  • 노드 34개. 두 파벌로 분열(실제).
  • 전통적(NDC) SBM: “고차수 vs 저차수” 그룹으로 나눔(실제 파벌 분할과 어긋남).
  • Degree-corrected(DC) SBM: 거의 정확히 두 파벌을 재현(고차수 노드가 다른 블록에 섞여 있어도 괜찮).

5.2. Political blog 네트워크

  • 노드 1222개, "liberal vs conservative"라는 현실 분류 있음.
  • NDC-SBM은 또다시 “고차수 vs 저차수”로 분할.
  • DC-SBM은 정치 성향에 가까운 분류를 찾아냄. 실제 레이블과 Normalized Mutual Information(NMI)=0.72로 꽤 높은 일치도.

6. 인공(합성) 네트워크 실험과 성능 비교

6.1. 합성 그래프 생성

  • DC-SBM에서, (\omega{rs}^{} = \lambda \omega{rs}^{(\mathrm{planted})} + (1-\lambda) \omega_{rs}^{(\mathrm{random})}) 같은 식으로 “커뮤니티 + 무작위” 가중.
  • (\lambda=0)이면 완전 무작위(차수만 유지), (\lambda=1)이면 이상적인 커뮤니티, 그 중간값으로 커뮤니티 명확도 조절.

6.2. 실험 결과

  • 전통적 모델 vs DC-SBM 각각 초기화를 (a)플랜트된 그룹으로, (b)랜덤으로 한 뒤, 최종 할당을 측정 → 실제 플랜트 구조와의 NMI 비교.
  • (\lambda)가 작으면(커뮤니티 구조 희미), 모두 성능 낮지만, 어느 정도 (\lambda) 이상이 되면 DC-SBM이 훨씬 빠르게 “진짜 구조”를 인식.
  • 전통적 모델은 (\lambda)가 꽤 커져야만 간신히 잡아내며, 때로는 끝까지 고차수-저차수 그룹에만 치중.

7. 결론 & 시사점

  1. Degree-corrected 아이디어:

    • 기존 SBM에 노드별 차수를 반영 → 큰 차수 노드끼리 뭉치는 “가짜” 커뮤니티 현상을 방지.
    • 따라서 실측 네트워크에서 더 정확하고 의미 있는 커뮤니티를 찾을 수 있음.

  2. 장점:

    • 실제 네트워크 차수 분포가 폭넓은 경우(이질성이 클 때) 효과 탁월.
    • 합성 벤치마크 생성에도 활용 가능(정밀한 차수 분포를 부여한 블록 구조).

  3. 한계:

    • 너무 많은 매개변수(( \theta_i)가 노드마다 존재).
    • 특정 차수(0도달 등)가 모델링되기 어려울 수 있음.
    • 그룹 수 (K)도 미리 알아야 한다는 점. (물론 MDL이나 다른 기법으로 해결 시도 가능)

  4. 의의:

    • 차수를 고려하는 확장으로도, 모델 복잡도가 ‘조금’ 증가하는 것에 비해 실험 성능은 “상당한” 개선 → 커뮤니티 탐색에서 사실상 “디폴트 옵션”으로 고려해야 할 만큼 중요.
    • 이후 다른 블록 모델(Overlap, Mixed membership)에도 동일 아이디어 적용 가능.

“노드 간 연결이 실제로는 차수에 큰 영향을 받는다는 점을 무시하면, 커뮤니티 구조 발견이 심각하게 왜곡될 수 있다.”
“Degree-Corrected SBM”은 이 문제를 효과적으로 해결해준다.

참고

  • Karrer & Newman (2010). Stochastic blockmodels and community structure in networks. arXiv:1008.3926
  • 본문에서는 수학적 유도 외에도, 여러 실제·합성 네트워크에서 “전통적 vs 차수보정 SBM”을 비교 실험. 차수보정이 대부분 우수.

아래 내용은 Peixoto (2020) 논문 "Latent Poisson models for networks with heterogeneous density"(arXiv:2002.07803v4)를 기반으로, 네트워크에서 ‘전역적으로 희소(globally sparse)’이지만 ‘국지적으로는 밀집(locally dense)’할 수 있는 구조를 설명할 수 있는 잠재(multigraph) 포아송 모델(latent Poisson model)을 소개하고, 이를 어떻게 단순 그래프(simple graph) 분석에 적용할 수 있는지를 한글로 자세히 설명합니다. 특히 수식·개념·원리에 초점을 맞춰, 왜 이러한 모델이 필요한지, 그리고 "erased(에러이즈드) Poisson 모델"을 어떻게 도출·추론하며, 커뮤니티 탐지(community detection)에 어떻게 활용되는지를 정성껏 풀어내겠습니다.

1. 서론: 전역 희소성과 국지 밀도의 공존

1.1 전역적으로 희소(sparse)하지만, 국지적으로 매우 밀집한 현상

  • 희소 네트워크란?
    • 전체 노드 수 (N)에 비해 간선의 수 (E)가 매우 적어, 평균 차수 (\langle k\rangle)이 크지 않은 상태. 예: 대부분 사람이 전세계 수십억 중 극히 일부에게만 연결(소셜 네트워크).
    • 그러나, 지역적으로는 어떤 노드는 굉장히 많은 노드와 연결될 수 있음(“허브” 현상), 혹은 작은 집단 내부는 매우 조밀하게 연결되어 있을 수 있음(“커뮤니티”).

1.2 기존 접근의 어려움

  • 차수가 매우 큰 노드 존재 → 전통적인 “단순 그래프 단위”의 일반적인 모델(예: 전형적 SBM 등)은, 단순히 “네트워크 전반적으로 희소함”만으로는 이질적(heterogeneous) 밀도를 잘 처리하기 어렵다.
    • 예: 노드 일부가 전체 절반과 연결(“locally dense”)이지만, 전체적으로는 희소 → 전통 모델이 이를 설명하려면 구조적 왜곡, 혹은 잘못된 결론(예: “차수가 큰 노드는 별도 그룹” 등)이 나올 수 있음.

2. “최대 엔트로피(maximum-entropy) 모델”과 포아송(Poisson) 모델

2.1 최대 엔트로피 원리: 간선 수(차수 분포)에 대한 제약

  • 노드별 기대 차수 (\hat{k}i)가 주어졌을 때, 이를 만족하는 가장 “무작위성(엔트로피)”이 큰 네트워크 집합을 고려:
    [
    \text{maximize} \quad S = -\sum    {A}P(A)\ln P(A)
    ]
    subject to (\sum{A}P(A)\sum_j A{ji} = \hat{k}_i) 등등.

  • 이때의 해답: 각 (i,j) 간선이 독립적이며, (\theta_i\theta_j) 꼴로 연결 확률(또는 기댓값)이 표현되는 분포.

    • 단순 그래프의 경우:
      [
      P(A_{ij}=1)\;=\;\frac{\theta_i\theta_j}{1+\theta_i\theta_j}.
      ]
    • 멀티그래프(다중 간선 허용)의 경우:
      [
      P(A_{ij}=m)\;=\;(1-\theta_i\theta_j)\,(\theta_i\theta_j)^m.
      ]
    • 노드별 기대 차수 (\hat{k}_i)를 만족하기 위해 (\theta_i)를 적절히 풀어야 함.

2.2 “구별 가능한(distinguishable) 멀티에지”를 고려하면 포아송 모델 등장

  • 만약 간선 하나하나에 “타입”이 있다고 하고, 타입 수 (M)을 (\to\infty)로 두면, 결국 “각 (i\to j)에 대한 다중 연결”이 포아송 분포로 수렴:
    [
    P(A_{ij} = m) \;=\; \frac{(\theta_i\theta_j)^m}{m!} e^{-\theta_i\theta_j}.
    ]
  • 이를 ‘포아송 모델’이라 부름.
  • 만약 자기 루프(self-loop) 포함하면, 노드 (i)의 대각성분 (A_{ii})는 짝수 형태.
  • 포아송 모델은 차수가 무한히 클 수도 있지만, (희소 가정) (\theta_i \approx k_i/\sqrt{2E}) 등으로 제한하면 실제 큰 스케일에서 잘 작동.

2.3 단순 그래프로 “지워진(erased) 포아송 모델”

  • Poisson 모델은 근본적으로 “노드 쌍 간 여러 간선(멀티엣지)”을 허용.
  • 실제 단순 그래프(0 또는 1개 간선)인 경우에는, 멀티엣지가 “1개 이상이면 1개로 치고, 0이면 0으로 치는” 식으로 erase한다:
    [
    G{ij}
    =
    \begin{cases}
    1 & \text{if }A    {ij}>0\
    0 & \text{otherwise}
    \end{cases}.
    ]
  • 이로 인해, (\theta_i\theta_j)가 큰 쌍은 포아송 분포 상 ‘간선 다중개’가 많았을 텐데, 전부 1로 뭉텅이 카운트 → 이 과정이 “내재적(de facto)으로 디서소티브(disassortative)한 상관”을 유도하기도 함.

3. Erased Poisson 모델의 성질

3.1 기대값 (\langle G_{ij}\rangle = 1 - e^{-\theta_i\theta_j})

  • 간선 존재 확률이 (1 - e^{-\theta_i\theta_j}). (\theta_i\theta_j)가 클수록 거의 1에 가까워져, 노드 간 연결이 “포화”되는 경향.
  • 이는 전통적 최대엔트로피(단순 그래프) 모델에서 (\theta_i\theta_j / (1 + \theta_i\theta_j))와 유사하지만, 실제 곡선 모양이 조금 다름(그림 1~2).

3.2 “노드 간 차수 상관”이 어떻게 생기는지

  • 전통적 단순그래프 모델(“Bernoulli SBM”)은 큰 (\theta\theta)에서 “포화”가 발생 → 디서소티브한 경향.
  • Erased Poisson도 마찬가지로 큰 (\theta\theta)에선 간선 존재 확률이 1에 가까워 “포화” → 디서소티브 경향.

3.3 Bayesian 관점에서의 "재구성(reconstruction)"

  • “단순 그래프”가 관측되었을 때, 그 이면의 “멀티그래프(포아송)”가 존재했다고 가정(“잠재 멀티그래프”) → (\theta)와 멀티그래프 (A)를 추정.
  • 이 과정:
    1. (P(A,\theta|G)) 식으로 Posterior 정리.
    2. 특정 (\theta)에 대해, 실제 (A)는 “단순 그래프 (G)에서 지워졌을(erase) 가능성이 있는 멀티엣지 분포” (\propto P(A| \theta)P(G|A))로 추론.
    3. EM 알고리즘으로 (\theta)를 구해나감 → E-step(기댓값 (\langle A\rangle) 계산), M-step((\theta) 업데이트).
  • 최종적으로는 “포아송 멀티그래프”(({A_{ij}}))를 복원 → 거기서 차수 상관이 없는지(혹은 적은지) 여부 확인.
    • 만약 복원된 멀티그래프가 별 상관이 없다면, “관측된 단순 그래프 상의 상관은 소거 과정(erase) 때문”이라는 결론.

4. 에러이즈드 포아송 모델로 살펴본 네트워크 특성

4.1 “(차수가 큰) 노드끼리 연결”이 단순히 “erase” 때문일 수도

  • 예: 혼합 정도가 broad한, 스케일프리 등에선 전통적 모델로는 “디서소티브”가 관측되지만, 에러이즈드 포아송 모델로 “본래 멀티그래프”를 재구성하면 상관성이 사라짐(실험).

4.2 여러 실제 네트워크 분석

  • 인터넷 AS 레벨, 생물학적 네트워크(메타볼릭), 소셜 네트워크(사용자 취향) 등 → 재구성 멀티그래프를 살펴보면, 일부는 “실제로 디서소티브가 아닌데, 차수 때문에 그런 것처럼 보였구나”를 확인.
  • 반대로, 실제로 유의미한 디서소티비티라면, 재구성 이후에도 남음.

5. 커뮤니티 탐색에의 적용

5.1 기존 Poisson DC-SBM vs Erased Poisson DC-SBM

  • Poisson DC-SBM(멀티그래프 전제)은 “노드 쌍 사이에 여러 간선”도 자연스럽게 나타남 → 전역 희소라도 특정 부분이 매우 치밀하면, 예: 한 쌍에서 (\lambda \approx 1) 이상일 수 있음.
  • 문제: 만약 실제 그래프가 단순 간선 형태이면, (\lambda > 1)인 경우 멀티엣지가 아주 빈번해질 수 있어, “포아송 모델”로는 잘 설명하기 힘듦.
  • “에러이즈드 포아송 SBМ”은 단순 그래프(중복 간선x)를 직접 다룸 → 로컬 밀도(‘한두 노드/클릭이 사실상 대부분과 연결’) 또한 “단순히 한 간선이 여러 번 중복되는” 것으로 만들 필요 없이, 1개의 간선의 “존재 확률이 거의 1”로 모델링 가능.

5.2 예시: 작은 클릭들이 많은 링 구조(network of cliques on a ring)

  • Poisson DC-SBM은 작은 완전 연결 집단(클릭) 내부의 (\lambda)를 매우 높이려면, “그에 따라 멀티엣지가 다수 생기는” 부작용 → 잘못된 예측.
  • Erased 포아송은 “딱 1개의 에지가 거의 확실히 존재(확률 근1)” 같은 케이스를 자연스럽게 표현 → 작은·조밀 커뮤니티도 잘 식별.

5.3 구체 사례

  • Karate club 같은 전통적 예시:
    • Poisson DC-SBM은 오히려 하나의 그룹 또는 몇 개 그룹(차수가 큰/작으로 분류…)만 찾을 수 있음
    • Erased Poisson DC-SBM은 더 풍부한(4개 그룹 등) 구조 추론(= 실제 국지적 조밀도 반영).

6. 결론

  1. 에러이즈드 포아송 모델(erased Poisson model):
    • “노드 쌍 간 다중 간선을 포아송로 생성 → 단순 그래프로 소거(erase)”, 라는 절차를 직접 확률모델화.
    • 전역 희소+국지 밀집(고차수 일부 노드, 작은 클릭) 등 다양한 “이질적 밀도(heterogeneous densities)”를 포아송분포 기반으로 간결히 포착.
  2. 단순 그래프에서 “디서소티브(음의 상관) vs 단순히 차수 때문에 유발된 것인가?” 구분 가능:
    • 잠재 멀티그래프(reconstructed multigraph)를 복원해서 그 상관을 조사 → 실제 내재된 상관인지, 단순한 “소거(erase) 현상”인지를 식별.
  3. 커뮤니티 탐색:
    • Poisson DC-SBM을 단순 그래프에 바로 적용하면 “멀티엣지” 발생빈도가 과소/과대 추정 → 국지적 조밀함을 놓칠 수 있음.
    • Erased 버전은 간선 존재확률이 (1-e^{-\theta_i\theta_j})로 “최대1”에 근접 가능 → 국소 밀집 구조를 더 명확히 감지 → 소형·치밀 커뮤니티도 잘 탐지.
  4. 향후 과제:
    • 링크 예측 등 다양한 “에러있는 측정”이나 “초이질성 네트워크”에서, Erased 포아송 모델이 얼마나 좋은지 추가 연구.
    • 복합 모형(혼합멤버십, 계층 SBM 등)에 Erased Poisson 아이디어 결합 가능.

정리 요약

본 논문은:

  • "포아송 멀티그래프" 모델이 차수 이질성(high-degree 노드)과 국지적 조밀도를 잘 설명하지만, 단순 그래프와 직접적 불일치(다중간선 허용↔불허).
  • 이를 해결하기 위해, "에러이즈드(Erasred) 포아송 모델"을 정의: 실제 단순 그래프는, 밑단(latent)에서는 포아송 멀티그래프로 생성되었으나, 다중간선은 1개로, 자기루프는 제거된 것으로 본다.
  • 이 모델을 통해 "관측 단순 그래프" → "잠재(multigraph) 구조"를 재구성(Bayesian/EM)할 수 있고, 이를 통해 차수 요인 vs 실질적 네트워크 구조를 구분 가능해진다.
  • 커뮤니티 탐색, 디서소티브 상관 해석 등에 응용 시, 기존 Poisson/DC-SBM이 가진 한계를 보완, 작은 클릭/조밀 구조도 잘 포착 가능.

따라서, “네트워크가 전역적으로는 간선 수가 적지만, 특정 부분만 매우 연결이 촘촘한” 복잡한 상황을 다룰 때, 에러이즈드 포아송 모델은 단순 포아송/최대엔트로피 모델 대비 더 유연하고 직관적인 해석을 가능케 한다는 것이 핵심 결론입니다.

profile
Sylen
AI가 재밌는 걸
이전 포스트

Graph-tool 8

다음 포스트

Graph-tool 9

0개의 댓글