그래프 전파 모형2 - 확률적 전파 모형(Stochastic cascade model)

1. 왜 확률적 전파 모형이 필요한가?

 

코로나19가 전파되는 과정을 모형화하고 싶은데 의사결정 기반의 선형 임계치 모형은 적절한 모형일까?

 

그렇지 않다. 누구도 코로나19에 걸리려고 의사결정을 한것이 아니다.

 

확률적으로 코로나19에 감염되기 때문에 확률에 기반한 전파 모형이 적절하다.

 

 

2. 독립적 전파 모형(independent cascade model)

 

방향성이 있고 가중치가 있는 weighted directed graph를 생각하자.

 

u에서 v로의 weighted link (u,v)의 가중치는 P(u,v)로 u가 감염되었을 때 v를 감염시킬 확률이다.

 

당연하지만 시작점인 u가 감염되지 않았을 때는 의미 없다.

 

node u가 감염될때마다 v를 감염시킬 확률 P(u,v)에 의해 다음 v를 감염시킨다.

 

 

 

g가 현재 감염자인데 다음으로 i를 감염시킬 확률은 0.4이다.

 

서로 다른 이웃이 전염되는, 각 전염과정은 모두 서로 독립이라고 가정하는 것이 독립 전파 모형이다.

 

 

 

최초 감염자부터 시작하여 감염되는 것이 기본인데 최초 감염자의 집합을 선형 임계치 모형처럼 시드 집합이라고 부른다.

 

시드 집합에 속하는 최초 감염자 u는 P(u,v)의 확률로 다음 v에게 감염을 전파 시킨다.

 

위 과정을 반복하여 더 이상 감염자가 나타나지 않을 때 과정을 종료한다.

 

감염이 된 순간 더 이상 회복되지 않는다고 가정한다.

 

물론 회복할 수도 있다고 가정하는 모형도 있다(SIS,SIR모형)

 

 

3. 확률적 감염을 코딩하는 방법

 

독립 전파 모형에서 확률적 감염을 어떻게 코딩하는지가 생각보다 재밌는데

 

임의의 확률을 uniform(0,1)에서 생성하고 감염확률보다 작으면 감염되었다고 판단하는 것이다.

 

 

 

감염된 노드의 이웃 중에서 아직 감염되지 않은 노드라면,

 

p=random.uniform(0,1)로 랜덤 확률을 생성하고

 

p<G.edges[src,dst][‘weight’]로 감염확률인 edge의 가중치보다 작으면 감염시켰다고 판단하고 감염자로 추가