13. Probabilistic Contagion and Models of Influence

Epidemic Spreading 에서는, Probability 에 기반해 질병이 퍼져나가게 됩니다.

Probabilistic Spreading Model

d : subtree 개수, q : 질병에 감염될 확률 이라고 했을 때,
1. Run forever : $\lim\limits_{h \to \infty}$ [a node at depth h] > 0
2. Die out : $\lim\limits_{h \to \infty}$ [a node at depth h] = 0
$h$를 $\infty$ 로 보냈을 때, 확률이 0보다 크다면 전염병이 확산된다고 할 수 있고, 확률이 0이라면 전염병이 끝났다고 할 수 있습니다.

따라서, 임의의 node h 에서 감염될 확률 $p_h$ 값을 통해 전염병의 지속 여부를 판단합니다.
$p_h = 1 - {(1 - q \cdot p_{h-1})}^d$
(= 1 - 이전 node 에서 나온 subtree 들이 모두 감염되지 않을 확률)

위의 식을 $\infty$ 로 보냈을 때의 결과물은,
$\lim\limits_{h \to \infty}p_h = f(x) = 1 - {(1 - q \cdot x)}^d$
가 되며, 해당 식에서 $x=0$ 에서의 접선의 기울기 값을 통해 전염병 확산 여부가 결정됩니다.
$f'(0) = R_0 = q \cdot d \geq 1$ : epidemic never dies
$f'(0) = R_0 = q \cdot d < 1$ : epidemic dies out

Epidemic Models

Virus Propagation 에는 두 개의 parameter 가 있습니다.

• $\beta$ : Birth Rate, 전염될 확률
• $\delta$ : Death Rate, 치료될 확률

각 node 는 여러 phase 에 도달할 수 있습니다.

• S : Susceptible
• E : Exposed
• I : Infected
• R : Recovered
• Z : immune

위와 같은 phase 에 기반하여, 여러 epidemic model 이 적용됩니다.

1. SIR Model

한 번 감염되어서 치료되면, 더 이상 감염되지 않는 모델입니다.

2. SIS Model

감염되어서 치료되어도, 다시 감염 가능성이 존재하는 모델입니다.
Virus Strength : $s = \beta / \delta$ 로 설정하고, Epidemic Threshold 값을 설정하여 전염병의 확산 정도를 판단합니다.

3. SEIZ Model

phase S : 루머를 믿지 않는 회의적인 상태여서, spread 하지 않는 상태를 나타냅니다.
해당 모델에서는 예측값과 실제값의 차이를 최소화 하는 방향으로 grid search 를 진행해 parameter 를 추정합니다.

Contact rate $\beta, b, \rho$ 값을 통해 아래의 식을 도출해 감염 확산 정도를 파악합니다.
$R_{SI} = \frac{S → E}{E → I} = \frac{(1-p) \beta + (1-l)b}{\rho + \epsilon}$

Independent Cascade Model

edge(u,v) 가 각각 다른 확률값 $p_{uv}$ 를 가지고 있는 모델입니다.
이 때 모든 weight 를 추정하는 것은 어려우므로, Exposure Curve 를 통해 판단합니다.

• Exposure : node's neighbor exposes the node to the contagion
• Adoption : The node acts on the contagion

Exposure Curve : Adopting new behavior 의 여부는 이미 behavior 가 전파된 neighborhood node 의 수에 의존하게 됩니다.

추가적으로, persistence 개념이 등장합니다. 그래프의 가장 높은 peak 를 찍은 후에도, 그래프의 곡선이 낮아지지 않는다면 해당 모델은 지속성이 크다고 할 수 있습니다.

모모남 홍정님 띵강 감사합니다 ~

13강. Probabilitic Contagion and Models of Influence

오늘은 포기를 모르는 홍정님께서 13강. Probabilitic Contagion and Models of Influence 에 대해서 강의해주셨습니다. 저번 12강에서 Cascade 가 의사결정이 되지 않는 경우는 probabilitic 한 모델을 사용한다고 했는데, 역시 13강은 그런 모델들에 대해서 잘 설명해주셨습니다.

크게 3가지를 살펴봤습니다.

• Probabilitic Spreading Models
• Epidemic models
• modeling using SEIZ model & Independent Cascade Model

Probabilitic Spreading Models

• Random Tree 베이스의 감염 모델입니다. 감염은 시기,시간(h)에 따라 계속 확산할 수도 있고 멈출 수도 있습니다.
• 감염될 확률 p_h를 정의하고, h가 무한대로 발산할 때에 대해서 구해봅니다.
• p_h = 1 - (h만큼 깊이에서 적어도 1개의 node가 감염되었을 확률) , 여사건으로 구함
• 유저가 사진을 보게 되었고, 사진이 확산 되는지 확인하는 실험에 대해서 이 모델을 적용한 예시를 봤습니다.

Epidemic models

• epidemic model들은 전염병을 상상하면 쉽습니다. -> 전염확률과 치료확률이 있습니다.
• SEIR, SIR, SIS model 등이 있습니다. (S : 걸리기쉬운, E : 노출, I : 감염, R : 치료, Z : 면역)
• 각 모델마다 파라미터에 따라 진행이 다르며, virus strength s = beta/delta 입니다.
• Epidemic threshold tau -> 전염/ 치료 보다 큰 값으로 1/ lambda 입니다. (인접행렬의 가장 큰 고유값)
• 루머가 확산되는 상황에 이 SEIZ 모델을 적용한 예시를 봤습니다. -> 트위터를 통해 루머가 확산되는 상황에 대해서 SEIZ 모델로 각 파라미터와 error를 정의하고 그리드서치를 사용해서 error를 최소화했습니다. (추정)
• 노출속도와 감염속도를 파악해서 루머의 경우 빠르게 사실로 받아들여지는(감염)되는 것을 파악했습니다.

Independent Cascade Model

• 위의 모델들과 다르게 랜덤트리가 아니라 그래프에 적용되는 모델입니다.
• 각 edge 마다 확률(weight)p를 가지고 있습니다. (독립시행)
• weight에 대한 전체적인 추정은 어렵기 때문에 노드의 Exposure&Adaption을 정의합니다.
• 이 모델에 대해서는 자세하게 보다는 plot을 그려서 exposure 일 때와, adaption에 대한 커브를 확인했습니다.

이번 강의는 모든것을 가진남자 이홍정님께서 감염병을 예로 들 수 있는Probabilistic Spreading Model에 관해 강의해주셨습니다.

Probabilistic Spreading Models

임이의 노드에서 다른 한 노드로 감염이 진행될 때, 감염 확률이 0보다 크면 전염병이 확산되는것이고, 감염확률이 0이면 전염병이 소멸한다고 말할 수 있습니다.

• 시작노드(임의의 노드)로 부터 depth d의 노드가 감염될 확률 : $p_h = 1-(1-qp_{h-1})^d$
  임의의 노드에서 depth d의 한 노드가 감염될 확률은 1에서 deph d에 위치한 노드 중 하나의 노드라도 감염될 확률을 빼면 됩니다. 그 확률을 극한으로 보내면,
  $\lim_{x\to\infty}p_h=f(x)=1-(1-qx)^d$
  이고, $f'(x)$는 [0,1]에서monotone non-increasing이고, $x=0$에서의 값이 전염병 확산 여부를 결정합니다.
• $f'(0)=R_0=qd \geq1$ : 전염병 확산
  -$f'(0)=R_0=qd < 1$ : 전염병 소멸

Epidemic Models (전염병 모형)

전염병 전파에는 두 개의 파라미터가 있습니다.

• birth rate 전염될 확률
• dead rate 치료될 확률

전염병 모델에는 대표적으로 SEIR,SIR,SIS Model등이 있습니다.

• SIR : SIR 모형 안에서 진행 상태는 크게 3가지로 구분하여 S(susceptible) ,I(infected),R(removed)로 나타내게 되는데, 여기서 S(susceptible)는 감염대상군으로 전체 모집단 안에서 감염될 가능성이 있는 대상을 일컫습니다. 다음으로 감염대상군에서 감염이 된 집단은 I(infected)으로 나타나게 되고 그로부터 사망하거나 회복된 개체의 집단은 R(removed)로 나타낼 수 있습니다. SIR모형은 이와 같이 S에서 I로 진행, I에서 R로 진행되는 과정을 가지게 되며, 그 과정에서 질병의 확산을 나타낸 모형이라고 할 수 있습니다.
• SEIR : SEIR 모형은 감염대상군 S(susceptible)으로부터 감염되어 감염군 I(infected)이 되는 과정에서 질병의 접촉군 E(exposed)이라는 단계를 추가한 모형입니다. 즉, 질병에 감염된 후 감염력이 생기는 잠복기가 있는 경우에 연구에 활용될 수 있습니다. 이에 대한 연구는 시간이 지날수록 다양한 분야로 응용되었고 지금도 많은 연구에서 모형으로 활용되며 실제 전염병의 확산 예방에 사용되고 있습니다.
• SIS

Independent Cascade Model

edge (u,v)는 확률값을 가지고 있으며, 다른 edge들과 독립적입니다. 하지만, 실제 데이터로부터 이 weight들을 모두 추정하는 것은 굉장히 어렵기 때문에 *새로운 행동(전염)의 전파여부는 이미 행동(전염)이 전파된 주변 노드의 수에 의존하는 것으로 파악합니다.