[그래프]4-2. 그래프를 통한 전파 : 확률적 전파 모형

그래프를 통해 다양한 것들이 전파되고 상호작용한다.
온라인 소셜 네트워크를 통해 정치 상황, 과학 정보, 챌린지 등 다양한 정보, 행동이 전파되고, 컴퓨터 네트워크 장비 고장의 전파, 파워 그리드의 정전 등의 고장이 전파될 수도 있다. 또한 코로나19, 사스, 메르스 등의 질병 전파도 그래프를 통한 전파로 설명될 수 있다. 

전파 과정은 다양하고 매우 복잡한데 이를 이해하고 대처하기 위한 많은 수학 모형 중 두 가지를 살펴보려 한다. 

---

1. 확률적 전파 모형

• 전염병의 경우를 생각해보면 의사결정 기반 모형은 적합하지 않다. 전염병에 걸리기로 '의사결정'을 내리지는 않기 때문이다.
• 전파가 확률적 과정으로 일어나는 경우 확률적 전파 모형을 고려해야 한다.
• 가장 간단한 형태인 독립 전파 모형(Independent Cascade Model)을 알아보자

 

---

2. 독립 전파 모형

1. 상황 및 전제조건

• 방향성이 있고 가중치가 있는 그래프를 가정
• 각 간선 (u, v)의 가중치 $p_{uv}$ : u가 감염, v가 비감염 시 u가 v를 감염시킬 확률
  즉, 각 정점 u가 감염될 때마다 이웃 v는 $p_{uv}$의 확률로 전염됨
• 서로 다른 이웃이 전염되는 확률은 독립적
  • u가 감염 시, u가 v를 감염시킬 확률은 u가 w를 감염시킬 확률과 독립적
  • u와 w가 감염 시, u가 v를 감염시킬 확률과 w가 v를 감염시킬 확률은 독립적

 

2. 전파과정

시작은 최초 감염자들로부터 시작하고 이들을 시드집합(Seed Set)이라고 부름.
감영자는 계속 감염된 상태로 남아있다고 가정함. 감염자의 회복을 가정하는 SIS, SIR 등 다른 전파 모형도 있음

1. 최초 감염자 u는 각 이웃 v 에게 $p_{uv}$확률로 병을 전파
2. 위 과정을 새로운 감염자 각각에게 반복
3. 위 과정을 새로운 감염자 각각에게 반복
4. 더 이상 새로운 감염자가 없을 시 종료

 

 

---

edwith의 그래프와 추천 시스템 강의를 듣고 정리 한 내용입니다.

https://www.edwith.org/ai211/joinLectures/316864

그래프와 추천 시스템 강좌소개 : edwith