Graph-tool 8

Sylen·2025년 1월 4일

아래 내용은 Price Network 모델 관련 참고 문헌들 가운데, 특히 이종 밀도(heterogeneous density)를 다루는 Latent Poisson 모델, 그리고 Microcanonical Stochastic Block Model(이하 SBM) 등과 관련된 핵심 원리·수식·개념을 중점으로, 한글로 상세히 설명하는 자료입니다. 수식과 원리를 위주로 설명하되, 네트워크 분석 전반의 응용 사례 이해에 도움이 되도록 정리했습니다.

0. 개요

네트워크 데이터에서 중요한 특징 중 하나는 전역적으로 희소(sparse)해 보이면서도, 국지적으로는 밀도(density)가 이질적이라는 점입니다. 예컨대, 어떤 노드는 전체 네트워크 중 큰 부분과 연결되어 “고차수(high-degree)”를 갖는가 하면, 대부분의 다른 노드는 소수의 노드와만 연결되는 경우가 흔합니다.

이때, 기존에 알려진 전통적인 확률적 블록 모델(Stochastic Block Model, SBM)들은 대체로 정확한(정수) 차수를 강제하거나, 정규화된 확률만을 다루며, 노드별로 큰 차수 편차나 지역적 밀집(커뮤니티) 구조를 온전히 반영하기 쉽지 않았습니다.

Peixoto, Newman 등의 관련 문헌은 이러한 문제점을 개선하기 위해, Poisson 분포를 활용한 랜덤 멀티그래프(multigraph) 기반 모델 또는 Microcanonical(미시정준) 모델을 다루면서,
1. 네트워크 생성 시 멀티엣지(동일 노드 쌍에 여러 간선)와 셀프 루프(자기 루프)를 허용해 수학적으로 간단한 꼴을 유지하거나,
2. 미시정준(Microcanonical) 방식으로 노드 차수·블록 간 간선 수를 정확하게 고정(= “hard constraint”)해서 모델을 구성할 수 있게 했습니다.

이하에서는 [Latent Poisson 모델: 멀티그래프를 얼핏 허용하지만, 최종적으로 심플(simple) 그래프를 만드는 과정]과, [Microcanonical SBM: 블록 구조를 엄격 고정해주는 방법]을 중점적으로 살펴봅니다.

1. Latent Poisson 모델과 이종 밀도(Heterogeneous Density)

1.1 Poisson 모델 배경

고전적 SBM은 블록 간 연결 확률(또는 기대값)을 정해놓고, 해당 확률에 따라 에지(edge)를 “0/1”로 표본추출함. 그런데,
- (a) 노드별 차수가 크게 다른 경우(= 이종도)
- (b) 어떤 노드는 네트워크 큰 부분과 많이 연결되어 사실상 멀티엣지에 가까운 상황
- (c) 지역적으로 극도로 밀집된 커뮤니티
- (\dots)
  이런 상황을 잘 설명하려면, 단순 이항 혹은 일정 확률만으로는 부족할 수 있음.
Poisson 모델은 두 노드 (i,j)가 연결될 때, 연결 간선 개수 (A_{ij})가 실제 포아송((\lambda)) 분포를 따른다고 가정. 즉, 동일 노드 쌍에서도 다중 간선을 허용.
- 식으로 쓰면, 노드 (i)와 노드 (j) 사이에 (m)개의 간선이 생길 확률 (P(A_{ij}=m))는
  
  [
  P(A{ij}=m) \;=\; \frac{(\lambda{ij})^m \; e^{-\lambda_{ij}}}{m!}.
  ]
이렇게 멀티엣지 모델을 쓰면, 차수가 큰 노드는 (\lambda_i)를 크게 설정해줄 수 있고, 따라서 노드별 이질적 차수 분포를 자연스럽게 반영 가능.
하지만 실제 현실 네트워크는 (대부분) simple graph(동일 노드 쌍에 최대 1개 간선)인 경우가 많다. 멀티엣지를 완전히 허용하는 Poisson만으로는 괴리가 있을 수 있음.

1.2 Erased Poisson(“지워진” Poisson) 모델

Erased Poisson(“지워진 포아송”) 모델 아이디어:
1. 먼저 백그라운드에서는 멀티그래프(포아송 분포)로 간선을 생성
2. 만약 노드 쌍 ((i,j))에 간선이 1개 이상 생겼으면 simple graph 상에서는 “단일 간선이 존재한다고(=1)” 표기, 2개 이상이어도 결과적으로는 1로 처리(“erase” = 다중 간선 정보는 지움)
3. 자기 루프도 마찬가지로 제거.
이렇게 하면, (\lambda{ij})가 큰 노드 쌍은 “simple graph 상에서 간선이 존재할 확률”이 (\;1 - e^{-\lambda{ij}}\; )이 됨.
- (\lambda{ij})가 매우 크면 (1 - e^{-\lambda{ij}} \approx 1), 즉 거의 100% 연결로 본다.
- 반면 (\lambda_{ij})가 작으면 0에 가까운 확률.
- 수학적으로는 “multiedge가 distinguishable(서로 구별 가능)”하다고 가정한 것과 맞물려, 간단한 꼴의 확률식을 얻을 수 있음.

1.3 Latent Poisson vs. Maximum-Entropy Simple Graph

동일한 차수 기대값을 강제하는 최대엔트로피(ME) simple graph 모델과 비교할 때, Erased Poisson은 고차수 노드끼리 연결될 확률이 포화되는 형태가 다소 다르게 나타남.
Erased Poisson은 “이론적으로 Poisson 기반 멀티그래프 + 에지 제거” 과정을 통해 명시적 디그리-디그리 상관(degree-degree correlation)을 만들어낼 수 있다는 점이 중요한 특징.
특히, 차수가 큰 노드가 많으면, 단순 Poisson 모델(멀티그래프 그대로)로는 “다중간선 발생”을 과도하게 예측할 수도 있는데, Erased Poisson은 1개의 간선으로 포화되어서 보다 실제 simple graph 형태를 잘 반영할 수 있음.

2. Microcanonical(미시정준) SBM 개념

2.1 전통적인 SBM의 “평균값” 강제 vs. 미시정준(정확값) 강제

Poisson형 SBM: 그룹 (r)–(s) 사이 간선 개수의 기대값(평균)만 (\lambda_{rs})로 맞추고, 실제로는 포아송 확률에 따라 변동.
Microcanonical SBM: 그룹 (r)–(s) 사이 간선 수가 정확히 (\;e_{rs}\;)로 고정. (혹은 노드 (i)의 차수가 정확히 (k_i))
- 즉, (\sum{r,s} e{rs} = 2E) 가 됨.
- 노드별 차수도 (k_i)가 정확히 설정됨 ⇒ 이 경우 배정 가능한 간선 구성(half-edge matchings)을 전수하는 combinatorial 방식을 사용.
이처럼 (a) 그룹 간 간선 수, (b) 노드별 차수가 “확률적으로가 아니라” 딱딱 고정되도록 하면, 이론적으로 “구체적 생성방법”은 configuration model(짜깁기 방식) 식으로 바뀜.
대신, 모델 내부 수식이 “self-loop나 멀티엣지 허용” 가능하게 전개되면, 계산이 간단해짐.

2.2 Microcanonical DC-SBM(Degree-Corrected Stochastic Block Model)

Degree-Corrected라는 말은 “노드별 차수 (k_i)를 원하는 대로(혹은 데이터로부터) 설정 가능”하다는 의미.
이때, 그룹별 연결((e_{rs}) = 그룹 (r)–(s) 간 간선 수)도 정확히 맞추어야 함.
그 확률은, 구조적으로 구성(half-edge pairing) 가능한 경우의 수 (\Omega(e))와 실제 간선 배치(그래프)마다 대응되는 경우의 수 (\Xi(A))를 비율로 하여 구함:

[
P(A \mid k, e, b)
\;=\;
\frac{\Xi(A)}{\Omega(e)}.
]
“모든 인접 행렬 (A) 중에서, (a) 노드별 차수가 (ki) 맞고, (b) 그룹 간 (\sum{ij} A{ij}\delta{bi,r}\delta{bj,s}) = (e{rs}) 충족하는” 경우만 허용. 나머지 경우는 확률 0.
이러한 엄격제약(microcanonical) 하에서, 차수 분포·블록 구조가 원하는 대로 반영 가능해지고, 수학적으로도 모델의 로그우도 등을 계산할 때 비교적 간단한 형태가 됨.

2.3 Microcanonical vs. Canonical SBM

Peixoto, Newman 등은 미시정준 SBM과 전통(포아송) SBM이, ‘대규모 네트워크에서 큰 차수값이 충분히 많을 경우’(Stirling 근사 등)에는 어느 정도 근사적으로 같은 분포를 유도하지만,
작은 스케일이나 예외적 데이터에는 두 모델이 다르게 동작할 수 있음을 보여줌.

3. 핵심 수식 요약

아래는 Latent Poisson(Erased Poisson) 모델과 Microcanonical DC-SBM 관련하여 자주 등장하는 대표적 수식들입니다.

Erased Poisson Simple Graph
- 백그라운드 멀티그래프에서 노드 (i),(j) 간 포아송 분포(평균 (\lambda_{ij}))로 간선을 생성한 후, “간선이 1개 이상이면 simple graph에서 1, 없으면 0, 자기 루프는 제외”:
  
  [
  P(G{ij}=1 \mid \lambda{ij}) = 1 - e^{-\lambda{ij}},
  \quad
  P(G{ij}=0 \mid \lambda{ij}) = e^{-\lambda{ij}}.
  ]
- 차수를 정확히 맞추려면, ({\lambda_{ij}})를 알맞게 풀어야 하는데, EM 알고리즘 등으로 수치해결 가능.
Microcanonical DC-SBM에서의 네트워크 생성 확률
- 노드 분할(블록 할당) (b), 그룹 간 간선수 (e_{rs}), 노드별 차수 (k_i)가 정해졌다고 할 때,
  
  [
  P(A \mid k,e,b) \;=\; \frac{\Xi(A)}{\Omega(e)},
  ]
  
  [
  \Xi(A) \;=\; \prod{i} k_i! \,\Big/\,\biggl(!!\prod{i<j} A{ij}!\biggr)\,\bigl(!!\prod_i A{ii}!!\bigr),
  \quad
  \Omega(e) \;=\; \prod{r} e{r}! \,\Big/\,\biggl(!!\prod{r<s} e{rs}!\biggr)\,\bigl(!!\prodr e{rr}!!\bigr).
  ]
- 여기서 (ki = \sum_j A{ij}), (e{rs} = \sum{ij} A{ij}\,\delta{bi,r}\delta{b_j,s}).
Microcanonical (Non-Degree-Corrected) SBM
- 노드별 차수를 그룹 내부에서 동일한 평균값으로 처리(= 전통적 SBM). 이때는 (\Omega(e)) 및 (\Xi(A))에 대한 해석이 조금 단순해지지만, 이질적인 차수 분포를 제대로 설명하기 어렵다.
Degree-Corrected vs. Non-Degree-Corrected
- (비교) 로그가능도에 대해, 차수를 반영하는 항(“(\sum k_i\log k_i)” 등)이 추가되어, 고차수 노드에 대한 모델 적합도가 훨씬 개선.

4. 이질적 밀도(Heterogeneous Density)에서의 장점

Broad degree distribution: 대규모 네트워크에서 차수가 극단적으로 큰 노드가 일부 존재해도, Latent Poisson이나 Microcanonical DC-SBM은 그런 노드들을 실제로 모델링 가능.
Locally dense subgraphs: Erased Poisson은 (\lambda_{ij})를 충분히 크게 두면, 두 노드가 거의 항상 연결(=1)되는 식으로 지역적 밀집을 정확히 표현 가능.
커뮤니티 탐지: “전통적인 SBM”은 고차수 노드를 하나의 블록으로 몰아넣는 식으로 틀릴 수도 있으나, “차수 보정(DC)”된 미시정준/포아송 모델은 이를 방지하며, 실제 커뮤니티 구조를 찾아낼 확률이 높아짐.

5. 요약

Poisson/Erased Poisson 방식은 멀티엣지를 허용하는 모델이지만, 최종 simple graph로의 “간선 중복 제거”를 통해, 이질적 차수나 국지 밀도를 쉽게 반영할 수 있음.
Microcanonical SBM은 또 다른 관점에서, 블록 간 간선 수, 노드 차수를 “정확히(하드하게)” 맞추는 모델로, 전반적 엔트로피 계산이나 MDL(최소기술길이) 분석이 깔끔해지고, 파라미터 추정도 균형감 있게 이루어짐.
두 접근 모두 이종적인 밀도 분포, 광범위한 차수분포를 네트워크 생성 과정에서 자연스럽게 포착할 수 있어, 고전적인 SBM 혹은 단순 무작위 그래프 모델 대비, 실제 데이터에 대한 적합도가 더 좋아진다는 장점이 있습니다.
Peixoto, Newman 등은 다양한 시뮬레이션 실험과 실제 empirical 네트워크에 대해 이를 시연했고, 커뮤니티 구조(예: 정치 블로그, 카라테클럽, Dolphin 사회적 네트워크, 등)에서 성능 향상을 관찰했습니다.

결론적으로, Poisson 기반 혹은 Microcanonical(미시정준) SBM은 정교한 네트워크 분석(특히, 차수분포가 넓고 국지 밀도가 큰 케이스)에서 우수한 설명력을 가진다는 점을 보여줍니다. Urban/교통 네트워크나 대규모 소셜 네트워크처럼 몇몇 노드나 지역이 매우 밀집되어 있을 때, 기존 단순 모델보다 적합하다는 연구결과가 제시되고 있습니다.

네트워크 모델링, 커뮤니티 탐지, 고차수 노드 분석, 확률 모델링 등 다양한 분야에서 이 개념들을 접목할 수 있을 것입니다.

참고 문헌

T. Peixoto, “Latent Poisson models for networks with heterogeneous density,” [arXiv:2002.07803 / Phys. Rev. E 102 (2020)]

T. Peixoto, “Nonparametric Bayesian inference of the microcanonical stochastic block model,” [arXiv:1610.02703 / Phys. Rev. E 95 (2017)]

B. Karrer, M.E.J. Newman, “Stochastic blockmodels and community structure in networks,” [Phys. Rev. E 83 (2011) 016107]

기타 인용: [arXiv:1008.3926v1], [arXiv:1610.02703v4] 등.

아래 내용은 graph-tool 라이브러리에서 제공하는 generate_sbm 함수를 중심으로, 네트워크(그래프) 모델 중 하나인 확률적 블록 모델(Stochastic Block Model, SBM)을 생성할 때 필요한 매개변수와 내부 동작 과정을 자세히 해설하고, 파이썬 예제 코드를 통해 실제로 어떻게 활용할 수 있는지를 단계적으로 설명합니다. 특히, (1) ‘포아송형 SBM’과 (2) ‘미시정준(Microcanonical) SBM’의 차이점을 살펴보고, (3) 초보자도 따라 하기 쉽게 주석을 풍부하게 포함한 튜토리얼 예시 코드를 준비하였습니다.

1. 개요: SBM(Stochastic Block Model)이란?

SBM은 네트워크의 정점(노드)들을 몇 개의 그룹(블록)으로 나누고, 그룹 간, 그리고 그룹 내부 간선 생성에 대한 확률(또는 평균 개수)을 달리 설정하여 네트워크를 생성하는 모델입니다.

예: 그룹 A와 B 사이 간선은 평균적으로 얼마, 그룹 B 내부 간선은 얼마… 식으로 모델링.
이렇게 함으로써, 네트워크가 분명한 “커뮤니티” 구조(혹은 그룹 구조)를 가지도록 생성할 수 있습니다.

graph_tool.generation.generate_sbm() 함수는 이러한 SBM 기반의 무작위 그래프(랜덤 네트워크)를 만들어주는 편리한 도구입니다. 특이하게도, 차수(노드별 연결 개수)가 정확히 고정되는 "미시정준(Microcanonical)" 모델과, 포아송 평균으로 설정되는 일반적 모델 모두를 지원합니다.

2. 함수 시그니처와 매개변수

graph_tool.generation.generate_sbm(
    b, 
    probs, 
    out_degs=None, 
    in_degs=None, 
    directed=False, 
    micro_ers=False, 
    micro_degs=False
)

각 인자의 의미는 다음과 같습니다:

b: 정수형 iterable 혹은 NumPy 배열
- 그래프의 각 정점이 어느 그룹(블록)에 속하는지를 명시. 즉, [0, 2, 1, 1, 0, ...] 식으로 노드 i의 그룹 번호가 담긴 리스트/배열.
- 예: b[i] = r 이면, i번 노드는 r번째 그룹에 속함.
probs: 2차원 NumPy ndarray 혹은 scipy.sparse.spmatrix
- 그룹 간 연결 “경향”(propensity)(평균 간선 개수)를 나타내는 행렬.
- probs[r, s] : 그룹 r와 s 사이에 존재하는 “평균 간선 수” (포아송 모델 기준). 혹은 미시정준 옵션일 때는 실제 간선 수를 정해주는 역할이 됨.
- 무방향 그래프(directed=False)의 경우, r == s인 대각 원소는 해당 그룹 내부 간선(자기 블록 내)을 평균 2배로 취급함에 유의(공식 문서 참고).
out_degs: (옵션) 각 노드의 out-degree(=나가는 차수)에 대한 “선호도(propensity)” 배열
- 비어 있으면 모든 노드가 동일 선호도를 가짐.
- 제공 시, 실제 간선이 어느 노드로부터 나가는지를 결정할 때 비례 사용.
- 미시정준(micro_degs)이 False라면, 이 값들은 “기댓값”만 맞추는 식(포아송)으로 작동. True라면, 실제로 정확히 고정된 out-degree가 됨.
in_degs: (옵션) 각 노드의 in-degree(=들어오는 차수)에 대한 “선호도(propensity)” 배열 (유향 그래프일 때)
- out_degs와 유사한 역할. 비어 있으면 모든 노드는 동일 in-degree 선호를 가짐.
directed: (기본값 False)
- True일 경우 유향 그래프(Directed graph) 생성, False이면 무향 그래프.
micro_ers: (기본값 False)
- True로 설정하면, “미시정준” 버전으로 에지 개수를 정확히 맞춤. 즉, probs[r, s]가 “그룹 r–s 간 실제 간선 수”가 됨(무방향일 경우 대각은 2배 해석).
- False면, probs[r, s]는 “평균 혹은 포아송 분포의 파라미터” 역할만 함.
micro_degs: (기본값 False)
- True일 경우, 노드 차수를 정확히 맞춤(“미시정준” 차수). 이 때는 자동으로 micro_ers=True도 포함되는 효과가 있음.
- False면, 노드 차수는 포아송적으로만 맞추고 실제로는 변동될 수 있음.

반환값

g: graph_tool.Graph 객체 (생성된 그래프)

3. 기본 동작 원리

블록 할당(b): 먼저 모든 노드 i가 그룹 b[i]에 속해 있음이 주어짐.
그룹 간 간선 개수(probs):
- 미시정준 모드(micro_ers=True)일 때:
  - probs[r, s] = 그룹 r, s 사이 “정확한 간선(혹은 중복 간선) 개수”.
    - 무방향의 경우, 대각(r == s) 원소 probs[r, r]는 “두 배”로 해석되어 그룹 r 내부에서 정확히 probs[r, r]/2개의 간선을 만듦.
- 포아송 모드(micro_ers=False)일 때:
  - probs[r, s] = 해당 그룹 쌍(r, s) 간선 개수의 평균(λ 파라미터). 실제 간선 수는 Poisson 분포로 샘플링.
노드 차수(out_degs, in_degs):
- 미시정준(micro_degs=True)이라면, 해당 노드의 out-degree, in-degree를 정확히 고정.
- 포아송일 때(micro_degs=False), 차수가 평균(기댓값) 정도로만 맞춰지고 실제 생성 시는 변동 가능.
간선 샘플링: 주어진 모든 제약(그룹 간 간선 수, 차수 등)을 충족하는 방향(혹은 무방향)으로 무작위 매칭을 수행하여 최종 그래프 g를 생성.

4. 단계별 예시 코드: Poisson한 SBM vs. Microcanonical SBM

초보자도 따라 하기 쉽게, Python 코드 예시를 작성해 보겠습니다.
아래 환경 전제:

Python 3.x
graph-tool 라이브러리 설치 (리눅스/맥에서 conda 혹은 해당 패키지로 설치)
numpy 설치

4.1 필요한 라이브러리 임포트

import numpy as np
import graph_tool as gt
from graph_tool.generation import generate_sbm

4.2 그룹 할당 벡터 `b` 만들기

예를 들어, 노드가 10개이고, 이를 그룹 0,1,2 중 하나로 무작위 배정:

N = 10  # 노드 수
B = 3   # 블록(그룹) 수

# 노드별 그룹 할당 (0 <= b[i] < B)
b = np.random.randint(low=0, high=B, size=N)
print("b:", b)  # 예: [1 0 2 1 1 2 0 1 2 0]

4.3 그룹 간 연결 확률(혹은 개수) 행렬 `probs` 준비

1) 포아송 모드 (micro_ers=False)

예: 그룹 r–s 간 평균 간선 수(=Poisson 파라미터)를 무작위로 생성

# 임의의 파라미터로 Poisson 파라미터 생성
probs_poisson = np.random.rand(B, B) * 5.0  # 0~5 사이
# 무방향 그래프를 가정한다면, probs를 대칭화
for r in range(B):
    for s in range(r+1, B):
        probs_poisson[s, r] = probs_poisson[r, s]

print("Poisson-based probs:\n", probs_poisson)

2) 미시정준(Microcanonical) 모드 (micro_ers=True)

probs[r, s] = r–s 간 실제 간선 수(정확히), 무방향이면 대각 대등 고려

probs_micro = np.random.randint(low=0, high=5, size=(B,B)).astype(float)

# 무방향을 가정하니 대칭화
for r in range(B):
    for s in range(r+1, B):
        probs_micro[s, r] = probs_micro[r, s]

print("Exact microcanonical edges:\n", probs_micro)

4.4 (선택) 노드별 차수(`out_degs`, `in_degs`) 지정

일단 간단히, 차수를 지정하지 않는 경우(None).
차수를 포아송 기반으로만 하거나, 혹은 미시정준일 때는 차수를 정확히 맞추려면, 아래처럼 배열 준비:

out_degs = np.random.randint(low=1, high=4, size=N)  # 노드별 out-degree
# in_degs가 필요하다면(유향 그래프 가정) 비슷하게 생성

4.5 그래프 생성 호출하기

포아송 SBM (미시정준 아님):

g_poisson = generate_sbm(
    b          = b,
    probs      = probs_poisson,
    out_degs   = None,      # or out_degs=out_degs, in_degs=...
    directed   = False,     # 무방향
    micro_ers  = False,     # 포아송(평균) 모드
    micro_degs = False
)

미시정준 SBM (간선 수도 정확히, 차수도 정확히):

g_micro = generate_sbm(
    b          = b,
    probs      = probs_micro,
    out_degs   = None,     # 차수 지정 없으면, 노드별 연결 개수 균일
    directed   = False,
    micro_ers  = True,     # 그룹 간 간선 수 엄격 고정
    micro_degs = False     # 차수까지 엄격 고정하려면 True (단, out_degs 필요)
)

4.6 결과 확인

print("포아송 SBM 그래프:")
print(" - 노드 수:", g_poisson.num_vertices())
print(" - 간선 수:", g_poisson.num_edges())

print("미시정준 SBM 그래프:")
print(" - 노드 수:", g_micro.num_vertices())
print(" - 간선 수:", g_micro.num_edges())

실제로 시각화를 해보고 싶다면 graph_tool.draw 모듈의 graph_draw 함수로 위치좌표를 레이아웃하고 확인할 수 있습니다:

from graph_tool.draw import graph_draw, sfdp_layout
pos = sfdp_layout(g_poisson)
graph_draw(g_poisson, pos=pos, output="poisson_sbm.png")

5. 튜토리얼 전체 코드 예시 (주석 풍부하게)

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

"""
graph-tool의 generate_sbm 함수를 사용하여
1) Poisson (평균 기반) SBM
2) Microcanonical (미시정준) SBM
두 가지 그래프를 생성해보는 예시 코드입니다.
"""

import numpy as np
import graph_tool as gt
from graph_tool.draw import graph_draw, sfdp_layout
from graph_tool.generation import generate_sbm

def main():
    # 1. 노드 수, 그룹 수 지정
    N = 12   # 노드 12개
    B = 3    # 그룹(블록) 3개
    
    # 2. 노드별 그룹 할당 벡터 b: [0, 2, 1, ...] 등
    b = np.random.randint(low=0, high=B, size=N)
    
    # 3. 그룹 간 연결 파라미터 (Poisson 모드)
    probs_poisson = np.random.rand(B, B) * 2.0
    # 무방향 가정 -> 대칭화
    for r in range(B):
        for s in range(r+1, B):
            probs_poisson[s, r] = probs_poisson[r, s]
    
    # 4. 그룹 간 정확한 간선 수 (Microcanonical)
    probs_micro = np.random.randint(low=0, high=3, size=(B,B)).astype(float)
    # 무방향 -> 대칭화
    for r in range(B):
        for s in range(r+1, B):
            probs_micro[s, r] = probs_micro[r, s]
    
    # 5. 그래프 생성: Poisson
    g_poisson = generate_sbm(
        b=b,
        probs=probs_poisson,
        out_degs=None,     # out-degree 명시 X -> 자동
        in_degs=None,
        directed=False,
        micro_ers=False,   # False -> Poisson(평균) 모드
        micro_degs=False
    )
    
    print("[Poisson SBM]")
    print(" 노드 수: ", g_poisson.num_vertices())
    print(" 간선 수: ", g_poisson.num_edges())
    
    # 6. 그래프 생성: 미시정준(간선 수 정확)
    g_micro = generate_sbm(
        b=b,
        probs=probs_micro,
        out_degs=None,
        in_degs=None,
        directed=False,
        micro_ers=True,     # True -> microcanonical: probs가 간선 수로 사용
        micro_degs=False
    )
    
    print("\n[Microcanonical SBM]")
    print(" 노드 수: ", g_micro.num_vertices())
    print(" 간선 수: ", g_micro.num_edges())
    
    # 7. 시각화를 해본다면 (단, IPython이 아닌 환경에서 .png로 저장)
    # 레이아웃 위치 계산
    pos_p = sfdp_layout(g_poisson)
    pos_m = sfdp_layout(g_micro)
    
    graph_draw(g_poisson, pos=pos_p, output_size=(300,300), output="sbm_poisson.png")
    graph_draw(g_micro, pos=pos_m, output_size=(300,300), output="sbm_micro.png")
    print("이미지 'sbm_poisson.png' 와 'sbm_micro.png' 에 각각 저장 완료.")

if __name__=="__main__":
    main()

6. 참고: `micro_degs=True`로 차수까지 완벽 고정하기

위 튜토리얼에선 micro_ers=True만 사용했습니다. 만약에 노드별 차수까지 정확히 맞추고 싶다면, 예컨대 out_degs = [3, 1, 0, 2, 2, ...] 식으로 지정한 뒤 micro_degs=True를 주면 됩니다. 그러면 노드 i가 정확히 out_degs[i]개의 간선을 내보내도록 매칭이 이뤄집니다(유향일 때).

무향 그래프에서는 out_degs 대신 동일한 배열을 전체 차수(degree)로 해석.

g_micro_deg = generate_sbm(
    b=b,
    probs=probs_micro,   # 그룹 간 간선 수
    out_degs=out_degs,   # 노드별 정확 차수
    directed=False,
    micro_ers=True,      # 간선 수도 엄격
    micro_degs=True      # 차수도 엄격
)

단, 이 경우 노드 차수들의 총합과 probs[r, s](=그룹 간 실제 간선 수) 총합이 호환되어야 합니다. 즉, 노드 차수 합이 2 * sum_r< s probs[r, s] + sum_r probs[r, r]와 일치하지 않으면 생성 불가능(오류)합니다.

7. 마무리

정리하자면, generate_sbm 함수는 블록 단위로 간선 생성이 이뤄지는 무작위 그래프를 만들어주는 데 매우 유용하며,

(a) 그룹 할당 b
(b) 그룹 간 간선 “평균값(or 정확값)” 행렬 probs
(c) (선택) 노드별 차수 정보 out_degs, in_degs
(d) micro_ers / micro_degs 옵션
등을 알맞게 설정해주면 됩니다.
포아송(Micro_ers=False): probs[r,s]는 기대값(λ), 실제 생성 시 오차 있음.
미시정준(Micro_ers=True): probs[r,s]가 실제 간선 수 그대로, 정확히.
차수 미시정준(Micro_degs=True): 노드 차수를 정확히 강제.

튜토리얼 예시 코드를 활용하면 그래프 생성 과정을 쉽게 테스트해볼 수 있을 것입니다.
추가로, 실제 분산된 대규모 그래프에서 이 함수를 쓰거나, 생성된 그래프를 다양한 알고리즘으로 시각화·분석해보면 SBM 모델을 이해하고 실제 네트워크 분석에 활용하는 데 큰 도움이 됩니다.

이상으로 graph_tool.generation.generate_sbm 함수에 대한 구체적인 설명 및 예제였습니다. 즐거운 네트워크 모델링 작업 되시길 바랍니다!

Sylen

AI가 재밌는 걸

이전 포스트

Graph-tool 7

다음 포스트

Graph-tool 8

0. 개요

1. Latent Poisson 모델과 이종 밀도(Heterogeneous Density)

1.1 Poisson 모델 배경

1.2 Erased Poisson(“지워진” Poisson) 모델

1.3 Latent Poisson vs. Maximum-Entropy Simple Graph

2. Microcanonical(미시정준) SBM 개념

2.1 전통적인 SBM의 “평균값” 강제 vs. 미시정준(정확값) 강제

2.2 Microcanonical DC-SBM(Degree-Corrected Stochastic Block Model)

2.3 Microcanonical vs. Canonical SBM

3. 핵심 수식 요약

4. 이질적 밀도(Heterogeneous Density)에서의 장점

5. 요약

1. 개요: SBM(Stochastic Block Model)이란?

2. 함수 시그니처와 매개변수

반환값

3. 기본 동작 원리

4. 단계별 예시 코드: Poisson한 SBM vs. Microcanonical SBM

4.1 필요한 라이브러리 임포트

4.2 그룹 할당 벡터 `b` 만들기

4.3 그룹 간 연결 확률(혹은 개수) 행렬 `probs` 준비

4.4 (선택) 노드별 차수(`out_degs`, `in_degs`) 지정

4.5 그래프 생성 호출하기

4.6 결과 확인

5. 튜토리얼 전체 코드 예시 (주석 풍부하게)

6. 참고: `micro_degs=True`로 차수까지 완벽 고정하기

7. 마무리

Graph-tool 7

Graph-tool 논문4

0개의 댓글

Graph-tool 8

0. 개요

1. Latent Poisson 모델과 이종 밀도(Heterogeneous Density)

1.1 Poisson 모델 배경

1.2 Erased Poisson(“지워진” Poisson) 모델

1.3 Latent Poisson vs. Maximum-Entropy Simple Graph

2. Microcanonical(미시정준) SBM 개념

2.1 전통적인 SBM의 “평균값” 강제 vs. 미시정준(정확값) 강제

2.2 Microcanonical DC-SBM(Degree-Corrected Stochastic Block Model)

2.3 Microcanonical vs. Canonical SBM

3. 핵심 수식 요약

4. 이질적 밀도(Heterogeneous Density)에서의 장점

5. 요약

1. 개요: SBM(Stochastic Block Model)이란?

2. 함수 시그니처와 매개변수

반환값

3. 기본 동작 원리

4. 단계별 예시 코드: Poisson한 SBM vs. Microcanonical SBM

4.1 필요한 라이브러리 임포트

4.2 그룹 할당 벡터 b 만들기

4.3 그룹 간 연결 확률(혹은 개수) 행렬 probs 준비

4.4 (선택) 노드별 차수(out_degs, in_degs) 지정

4.5 그래프 생성 호출하기

4.6 결과 확인

5. 튜토리얼 전체 코드 예시 (주석 풍부하게)

6. 참고: micro_degs=True로 차수까지 완벽 고정하기

7. 마무리

Graph-tool 7

Graph-tool 논문4

0개의 댓글

4.2 그룹 할당 벡터 `b` 만들기

4.3 그룹 간 연결 확률(혹은 개수) 행렬 `probs` 준비

4.4 (선택) 노드별 차수(`out_degs`, `in_degs`) 지정

6. 참고: `micro_degs=True`로 차수까지 완벽 고정하기