Graph-tool Dynamics

아래 내용은 graph-tool.dynamics 모듈에 포함된 다양한 동적(動的) 모델들을 간단히 나열한 것이며, 각각의 모델이 어떤 특징과 적용 목적을 갖는지를 상세하게 정리했습니다. 도시·교통 빅데이터나 네트워크 분석 관점에서도 어떤 식으로 응용될 수 있는지 짧게 언급하였으니 참고하시기 바랍니다.

---

1. Discrete-time dynamics (이산 시간 동역학)

(1) DiscreteStateBase

• 개요: 이산 시간에서 정의되는 네트워크 동역학(discrete-time dynamics) 계층 구조의 기본(Base) 클래스.
• 주 역할: 다른 이산적(의견·상태가 유한 정수 값) 모델들의 공통 인터페이스와 동작을 정의.
• 특징: 상속받은 클래스들이 “단계별 업데이트”(iterate, iterate_sync/async 등)을 구현하는 틀을 제공.

(2) EpidemicStateBase

• 개요: 전염병(Epidemic) 계층의 기본 클래스. 전염병 확산 모델(SI, SIS, SIR, SIRS 등)이 공통적으로 사용하는 메커니즘(감염률, 회복률 등)을 정의.
• 용도: 그래프에서 전염병이 퍼지는 과정을 시뮬레이션할 때(교통 네트워크 상에서 바이러스 전파, 정보 확산 모사, 등).

(3) SIState

• 개요: SI 전염병 모델. 노드는 S(감염 안 된 상태) 또는 I(감염된 상태) 중 하나를 가짐.
• 동역학 규칙:
  1. 감염된 노드(I)가 이웃 노드(S)에 일정 확률로 전염.
  2. 감염된 노드는 회복되지 않고 계속 I 상태 유지(즉, S→I 전환만 존재).
• 특징: 전염 과정이 일방향적이고, 결국 전체 노드가 I 상태가 되거나 일부만 I로 남아 정체되는 형태.
• 응용: 교통망에서 어떤 사건(사고, 장애, 공사)이 ‘전염’되어 다른 구간에 지연을 유발하는 경우를 단순화해 모사할 수 있음.

(4) SISState

• 개요: SIS 전염병 모델. 노드는 S(감염 안 된 상태) 또는 I(감염된 상태).
• 동역학 규칙:
  1. S → I: 이웃 중 I가 있으면 감염 확률에 따라 S→I.
  2. I → S: 감염된 노드는 일정 회복률로 다시 S가 됨.
• 특징: 감염과 회복이 지속적으로 반복되어, 유행병의 유입/유출 동학을 반영.
• 응용: 교통 병목(neck)이나 정체가 한 구간에서 다른 구간으로 번졌다가(감염), 어느 시점에는 해소(회복)되는 상황을 단순 모델로 표현 가능.

(5) SIRState

• 개요: SIR 전염병 모델. 노드는 S(감염 안 됨), I(감염됨), R(회복/면역) 상태 중 하나.
• 동역학 규칙:
  1. S → I: 이웃 I 노드로부터 감염 확률.
  2. I → R: 감염된 노드는 일정 시간이 지나면 회복되어 R(면역상태)이 됨.
  3. R 상태는 재감염 없음(면역).
• 특징: 감염 파동이 지나가면 감염되었던 노드는 R로 고착되므로 재발 불가. 한 번의 파동으로 끝나는 형태.
• 응용: 한 번 발생한 사건(예: 특정 사고)가 주변 구간에 파급된 뒤, 그 파급을 받은 구간은 다시 같은 현상에 민감하지 않게(면역) 된다고 가정할 때.

(6) SIRSState

• 개요: SIRS 전염병 모델은 SIR에 “R → S” 전이가 추가되어, 면역이 영구적이지 않고 일정 시간이 지나면 사라짐.
• 동역학 규칙:
  • S → I: 감염 확률
  • I → R: 회복
  • R → S: 면역이 사라져 다시 감염 가능(S로 복귀)
• 응용: 교통망에서 같은 유형의 사건/장애가 반복해서 발생할 수 있는 경우(일정 시간이 지나면 “면역” 해제).

(7) VoterState

• 개요: q-상태 Voter 모델. 네트워크상의 노드들은 q가지 “의견(opinion)” 중 하나를 가짐.
• 동역학 규칙: 비동기 업데이트 시, 무작위 노드가 이웃 한 명(또는 여러 명)에게서 의견을 “복사”하여 자기 의견을 바꾸는 식.
• 특징: 단순히 “주변의 의견에 따라가겠다”는 사회학적 모형에 가깝고, Voter 모델은 detailed balance를 만족하지 않는 비평형 모형 중 하나.
• 응용: 도시민의 정책 선호도, 교통수단 선택 등에서 이웃(주변) 영향에 의해 의견이 확산/변화되는 양상을 최소 모델로 모사.

(8) MajorityVoterState

• 개요: q-상태 다수결(Majority) Voter 모델. 단순 Voter와 달리 “이웃의 다수” 의견에 따라가려는 동역학.
• 동역학 규칙:
  1. 어떤 노드가 업데이트될 때, 확률 (r)로 무작위 의견을 선택
  2. 그렇지 않을 땐 이웃 중 가장 많은(다수) 의견을 따라감. (동률일 땐 무작위 선택)
• 특징: 집단 동조(conformity) 현상을 비평형적으로 모사. Ising 등과 유사한 임계 현상(대칭 깨짐)을 보이기도 함.
• 응용: 교통망(또는 도시 정책 네트워크)에서 “주변이 대부분 어떤 선택/방향을 취하면 따라가는” 현실적 의사결정 패턴을 가볍게 표현 가능.

(9) BinaryThresholdState

• 개요: 이진 임계값(Binary Threshold) 모델. 각 노드는 0 또는 1의 상태.
• 동역학 규칙: 노드가 1로 전환되는 조건은 “이웃 중 1인 노드 비율/개수 ≥ 임계값(Threshold)” 등으로 정의.
• 특징: 한 번 1이 되면 0으로 돌아갈 수 없거나(단방향) 특정 규칙으로 복귀 가능 등 다양한 변형 가능. Cascade 현상을 모사하는 데 자주 쓰임.
• 응용: “어느 교차로가 한계 교통량(Threshold)을 넘어가면 혼잡(1) 상태로 전환, 그 상태가 주변 노드에 영향을 준다” 같은 시나리오.

(10) IsingGlauberState

• 개요: 이산 스핀(±1) Ising 모델의 Glauber 동역학. 이웃 스핀 배치를 고려하여 에너지를 낮추는 방향으로 확률적 전이.
• 특징: 전통적 통계물리 모형(2차원 Ising). detailed balance(평형역학) 만족. 격자뿐 아니라 임의 그래프 위에서 돌릴 수 있음.
• 응용: +1/−1을 “교통량이 높음/낮음” 등 이진 상태로 대응시키고, 이웃에 따른 경향성/상호작용을 넣어 모델링.

(11) CIsingGlauberState

• 개요: Continuous Ising 모델(연속 값을 갖는 스핀)에서의 Glauber 동역학.
• 특징: 고전적인 ±1 이진 스핀 대신, 노드 상태가 실수 범위(continuous)로 확장된 Ising 유사 모델.
• 응용: “이산”보다 좀 더 세밀한 수준으로(예: 교통 혼잡도 0~1 범위) 상태를 표현 가능.

(12) IsingMetropolisState

• 개요: 이진 Ising 모델에서 Metropolis-Hastings 규칙으로 업데이트.
• 차이점: Glauber와 유사하나 전이 확률 계산 방식이 “에너지 변화((\Delta E))”에 기반한 Metropolis 규칙(( \min(1, e^{-\beta \Delta E}) ))을 사용.
• 응용: 교통망에서 “거시적 에너지(비용) 최소화”를 가정하는 시뮬레이션 등에 유추적 사용 가능.

(13) PottsGlauberState

• 개요: Potts 모델(q-상태 스핀)이 Glauber 동역학으로 진화.
• 특징: Ising(2상태) 모델을 q상태로 확장한 것. 상 전이, 도메인 구조 등 복잡한 현상을 모사.
• 응용: “지역(노드)이 여러 카테고리(상태) 중 하나를 택하는” 등, 도시 기능(상업/주거/공업 등 여러 종류) 분포를 몬테카를로적으로 시뮬레이션할 때 응용 가능.

(14) PottsMetropolisState

• 개요: q-상태 Potts 모델에서 Metropolis-Hastings 업데이트 규칙 적용.
• 특징: PottsGlauberState와 마찬가지로 q-상태 상호작용이지만, 전이율 계산이 Metropolis 방식을 사용.

(15) AxelrodState

• 개요: Axelrod의 문화 전파 모델. 노드마다 여러 문화 특질(feature)들을 가지고, 이웃 간의 상호작용으로 점차 유사해지거나 갈라지는 다이나믹스.
• 특징: 한 노드가 이웃 노드와 공유하는 특질 수(유사도)가 많을수록, 그 이웃의 다른 특질도 받아들일 확률이 커짐.
• 응용: 도시 지역 간 생활양식(문화/관습/교통수단 선호 등)이 상호영향으로 동질화되거나 분극화되는 현상을 가볍게 모형화할 수 있음.

(16) BooleanState

• 개요: 불리언 네트워크(Boolean network) 동역학. 노드는 0 또는 1 상태, 업데이트 규칙은 논리 연산(AND, OR 등)으로 정의 가능.
• 특징: 생물학적 유전자 조절 네트워크, 디지털 회로, 간단화된 의사결정 프로세스 등을 모사하는 데 종종 쓰임.
• 응용: 도시·교통 시스템의 “신호(0/1) 로직”을 네트워크로 구성해, 병렬 업데이트나 시스템 안정화 등을 탐색할 수 있음.

(17) KirmanState

• 개요: Kirman의 “개미 군집(ant colony)” 모델. 노드는 어떠한 선택(가령 “항구에 모이는 개미 수”) 상태를 갖고, 무작위 전이와 상호작용으로 동역학이 전개.
• 특징: 개체들이 집단적으로 특정 자원에 몰리거나 분산되는 현상(Kirman 모델은 금융 시장, 종잡을 수 없는 이동성 등에도 적용).
• 응용: 교통체계에서 특정 도로(자원)에 인구가 몰렸다가 분산되는(개미의 집합/이탈 현상) 패턴을 모사.

(18) NormalState

• 개요: 다변량 정규 분포(Multivariate Normal) 상태. 노드별로 연속값을 가지며, 전체 시스템이 다변량 정규로 진화.
• 특징: 상태 간 상관구조(covariance matrix) 등을 고려해 연속 상태 업데이트를 수행.
• 응용: 연속적인 교통 흐름(속도, 차량량) 변화를 통계적으로 모델링할 때 참고 가능.

(19) LinearNormalState

• 개요: 선형 이산시간 + 노이즈가 포함된 확률적 동역학. 매 스텝에 선형 변환을 거치고, 정규분포 노이즈가 더해짐.
• 특징: AR(Autoregressive) 프로세스, Kalman filter와 유사한 관점에서의 모형화.
• 응용: 교통 수요(시계열) 예측, 도시 성장 모델 등에서 선형 시계열 가정을 하는 경우.

---

2. Continuous-time dynamics (연속 시간 동역학)

(1) ContinuousStateBase

• 개요: 연속 시간에서 정의되는 네트워크 동역학(continuous-time dynamics) 모델들의 기본(Base) 클래스.
• 특징: ODE(상미분방정식) 형태 등으로 노드 상태가 시간에 따라 연속적으로 변화할 때 사용.

(2) LinearState

• 개요: 선형 연속 동역학. 예컨대 (\dot{x}(t) = A x(t) + \eta) 같은 형태(행렬 A, 잡음 (\eta) 등).
• 특징: 네트워크 구조에 따라 A를 구성할 수 있음(인접행렬, 라플라시안 행렬 등).
• 응용: 교통 네트워크의 미소 유량 변화나, 도시 인구 흐름의 연속적인 변동을 선형 근사로 표현하는 경우.

(3) LVState

• 개요: 일반화된 Lotka-Volterra 모델. 포식자-피식자 등 생태계 모형에서 유래. 그래프 위에서 종간 상호작용(혹은 노드별 자원 경쟁/협동)을 모델링.
• 특징: (\dot{xi} = x_i(\alpha_i + \sum_j \beta{ij} x_j)) 형태, 상호작용 계수에 따라 증식 또는 감소가 일어남.
• 응용: 교통 흐름 측면에서 다중 노선 간 경쟁·협력 관계를 (생태계적 관점)으로 해석할 수도 있음.

(4) KuramotoState

• 개요: 쿠라모토(Kuramoto) 위상 동기화 모델. 노드(진동자)가 위상 (\theta_i)를 갖고, 이웃과 결합하여 동기화 현상을 일으킴.
• 특징: (\dot{\thetai} = \omega_i + K \sum{j} A_{ij} \sin(\theta_j - \theta_i)) 형태의 고전적 모델.
• 응용: 신호등 동기화, 분산 시스템의 위상 조절(전력망 위상 동기화) 등을 모사할 때.

---

3. Belief propagation (BP, 신념 전파)

(1) BPBaseState

• 개요: Belief Propagation(신념 전파) 알고리즘 구현을 위한 기본(Base) 클래스.
• 특징: 그래프상의 확률적 분포를 근사적으로 계산하기 위해, 메시지 전달(Message Passing) 방식을 사용.
• 응용: 큰 확률 그래프 모델에서 근사 추론(MAP 추론, 주변 분포 계산), 예컨대 도시 교통 네트워크에서 노드 상태(혼잡 확률 등)를 근사 추정.

(2) GenPottsBPState

• 개요: 일반화 Potts 모델에 대한 Belief Propagation 구현.
• 특징: q-상태 Potts 모형이 그래프 위에 정의될 때, BP 알고리즘으로 근사 추론(노드별 상태분포, 마그네타이제이션 등) 수행.
• 응용: 복수 범주(카테고리)가 있는 교통·도시 분포 문제에서, 그래프적 사전 정보(이웃과 비슷할 가능성이 높다 등)를 활용해 추정.

(3) IsingBPState

• 개요: Ising 모델에 대한 Belief Propagation 구현.
• 특징: ±1 상태의 Ising 계, 에너지 함수가 그래프 간선으로 정의될 때, BP로 근사적 분포 계산.
• 응용: 도시·교통 빅데이터에서 2가지 상태(혼잡/비혼잡 등)로 나타나는 지도·시뮬레이션을, 확률적(전역 상호작용) 관점에서 풀어낼 때.

(4) NormalBPState

• 개요: 다변량 정규분포(Multivariate Normal Distribution)를 대상으로 한 Belief Propagation.
• 특징: 노드들이 연속 변수로 연결되어 있을 때, 공분산 구조를 그래프 연결로 표현한 뒤, BP로 주변분포나 조건부분포를 추정.
• 응용: 교통량, 유동 인구 등을 연속 변수로 놓고, 네트워크 구조에서 상호의존적 확률분포를 근사 추론.

---

요약 & 시사점

• Discrete-time vs. Continuous-time
  • 이산 모델들은 보통 시간 스텝을 분할해서 각 스텝마다 상태 전환을 계산(몬테카를로 시뮬레이션처럼).
  • 연속 모델들은 ODE(또는 SDE) 형태로 시간축을 계속 추적.
• Epidemic 계열: 전염/회복 과정을 네트워크에서 쉽게 모사. 교통, 정보확산, 전파 현상 등 응용.
• Voter / Majority: 사회적(또는 에이전트 기반) 동조나 합의(콘센서스) 과정을 단순화한 비평형 모델.
• Ising / Potts: 통계물리적 상호작용(‘비용’ 최소화 혹은 상호작용에 따른 에너지)를 그래프 위에서 시뮬레이션.
• Axelrod / Kirman 등: 사회·문화적 확산, 개미 군집 동역학 등 특정 분야에서 제안된 이론적 모델을 그래프 위에 구현.
• Belief Propagation: 확률적 그래프 모델에서 근사 추론을 수행하는 핵심 알고리즘. 대규모 네트워크에서 유용.
• 도시·교통 빅데이터 관점
  • 이런 모델들은 “네트워크 위의 상태 변화”를 다룬다는 공통점이 있어, 교통 흐름, 혼잡 전파, 의사결정, 지역 간 상호작용 등을 탐색할 때 가벼운(또는 심층적인) 시뮬레이션 툴로 활용 가능.
  • 다양한 동역학적 프로세스가 네트워크(도로, 지하철, 버스, 통신망 등)와 맞물려 작동하는 현상을 이해·예측하기 위한 모형적 토대가 될 수 있음.

위와 같은 모델들을 활용해, 예를 들어 graph_tool 라이브러리 내 제공되는 동기/비동기(iterate_sync/iterate_async) 시뮬레이션 메서드, 병렬화(OpenMP) 기능 등을 조합하면, 복잡한 도시·교통 네트워크에서 발생하는 전염, 확산, 상호 의존성 등을 탐색·분석하는 데 도움을 받을 수 있습니다. 또한, Belief Propagation 계열은 데이터가 부분적으로만 관측되었을 때(예: 일부 구간의 교통량만 측정 가능)에, 네트워크 전체에 대한 확률적 추론을 효율적으로 수행하는 기반이 될 수 있습니다.