# Chapter13. Probabilistic Contagion and Models of influnce

## Probabilistic Contagion and Models of Influence

### Epidemics vs Cascade Spreading

결정을 기반으로한 모델 노드들은 전략을 채택해서 드는 비용에 기반하여 결정을 내립니다.

In epidemic spreading(전염병 확산 문제)

Lack of decision making

Process of contagion is complex and unobservable(복잡하고 관찰하기 힘듦)

In some cases it involves (or can be modeled as) randomness

### Example with k=3

감염 확률이 커지면 전염병은 커지고, 낮은 감염 확률을 가지면 질병은 사라집니다.

### Probabilistic Spreading Models

Epidemic Model based on Random Trees

a variant of branching processes

A patient meets d new people

With probability q > 0 she infects each of them

Q : For which values of d and q does the epidemic run forever?

### Probabilistic Spreading Models

q와 d로 depth가 커질 때 확률값이 얼마인지 계산할 필요가 있습니다. 우리는 이값을 인접한 부모, 자식 노드와의 관계를 통해 iterative하게 정의할 수 있습니다.

### Fixed Point : f(x) = 1 - (1-qx)^d

## Probabilistic Contagion and Models of Influence

### Epidemics vs Cascade Spreading

결정을 기반으로한 모델 노드들은 전략을 채택해서 드는 비용에 기반하여 결정을 내립니다.

In epidemic spreading

Lack of decision making

Process of contagion is complex and unobservable

In some cases it involves (or can be modeled as) randomness

### Example with k=3

### Probabilistic Spreading Models

Epidemic Model based on Random Trees

a variant of branching processes

A patient meets d new people

With probability q > 0 she infects each of them

Q : For which values of d and q does the epidemic run forever?

### Probabilistic Spreading Models

### Fixed Point : f(x) = 1 - (1-qx)^d

If we want to epidemic to die out, then iterating f(x) must go to zero. So, f(x) must be below y=x.

What's the shape of f(x)

what do we know about the shape of f(x)?

If we want to epidemic to die out, then iterating f(x) must go to zero. So, f(x) must be below y=x.

What's the shape of f(x)

### Fixed Point: When is the zero?

what do we know about the shape of f(x)?

### Important Points

### Fixed Point: When is the zero?

Reproductive number R0 = q*d:

It determines if the disease will spread or die out.

There is an epidemic if R0>= 1

Only R0 matters:

R0 >= 1 : epidemic never dies and the number of infected people increases exponentially

R0 < 1 : Epidemic dies out exponentially quickly

### Measures to Limit the Spreading

### Important Points

When R0 is close 1, slightly changing q or d can result in epdemics dying out or happening

Quaratining people / nodes [reducing d]

Encouraging better sanitary practices reduces germs spreading [reducing q]

HIV has an R0 between 2 and 5

Measles has an R0 between 12 and 18

Ebola has an R0 between 1.5 and 2

Reproductive number R0 = q*d:

It determines if the disease will spread or die out.

There is an epidemic if R0>= 1

Only R0 matters:

R0 >= 1 : epidemic never dies and the number of infected people increases exponentially

R0 < 1 : Epidemic dies out exponentially quickly

## Application : Social cascades on Flickr and estimating R0 from real data

### Measures to Limit the Spreading

### Dataset

When R0 is close 1, slightly changing q or d can result in epdemics dying out or happening

Quaratining people / nodes [reducing d]

Encouraging better sanitary practices reduces germs spreading [reducing q]

HIV has an R0 between 2 and 5

Measles has an R0 between 12 and 18

Ebola has an R0 between 1.5 and 2

Flickr social network

Users and connected to other users via friend links

A user can like/favorite a photo

Data:

100 days of photo likes

Number of users : 2 million

34,734,221 likes on 11, 267, 320 photos

## Application : Social cascades on Flickr and estimating R0 from real data

### Cascades on Flickr

### Dataset

Users can be exposed to a photo via social influence (cascade) or external links

Did a particular like spread through social links

No, if a user likes a photo and if none of his friends have previously liked the photo

Yes, if a users likes a photo after at least one of her friends liked the photo-> Social cascade

Example social cascade: A->B and A->C->E

Flickr social network

Users and connected to other users via friend links

A user can like/favorite a photo

Data:

100 days of photo likes

Number of users : 2 million

34,734,221 likes on 11, 267, 320 photos

### Cascades on Flickr

### How to estimate R0 from real data?

Users can be exposed to a photo via social influence (cascade) or external links

Did a particular like spread through social links

No, if a user likes a photo and if none of his friends have previously liked the photo

Yes, if a users likes a photo after at least one of her friends liked the photo-> Social cascade

Example social cascade: A->B and A->C->E

### R0 correlation across all photos

### How to estimate R0 from real data?

Data from top 1, 000 photo cascades

Each + is one cascade

### R0 correlation across all photos

### Discussion

Data from top 1, 000 photo cascades

Each + is one cascade

The basic reproduction number of popular photos is between 1 and 190

This is much higher than very infectious diseases like measles, indicating that social networks are efficient transmission media and online content can be very infectious.

## Epidemic models

### Discussion

### Spreading Models of Viruses

The basic reproduction number of popular photos is between 1 and 190

This is much higher than very infectious diseases like measles, indicating that social networks are efficient transmission media and online content can be very infectious.

Virus Propagation : 2 Parameters:

## Epidemic models

Virus Birth rate

probability that an infected neighbor attacks

Virus Death rate

Probability that an infected node heals

### Spreading Models of Viruses

Virus Propagation : 2 Parameters:

### More Generally : S+E+I+R Models

Virus Birth rate : beta

probability that an infected neighbor attacks

Virus Death rate : delta

Probability that an infected node heals

General scheme for epidemic models

Each node can go through phases

Transition probs. are governed by the model parameters

### More Generally : S+E+I+R Models

### SIR Model

General scheme for epidemic models

Each node can go through phases

Transition probs. are governed by the model parameters

Subceptible : 병에 걸리기 쉬운, Expose: 노출, Infection, Recover, Immune

SIR model : Node goes through phases

Models chickenpox or plague:

Once you heal, you can never get infected again

### SIR Model

Assuming perfect mixing (The network is a complete graph) the model dynamics are:

SIR model : Node goes through phases

Models chickenpox(수두) or plague:

Once you heal, you can never get infected again

Assuming perfect mixing (The network is a complete graph) the model dynamics are:

### SIS Model

Susceptible-Infective-Susceptible (SIS) model

Cured nodes immediately become susceptible

Virus "strength" : s = b/r

Node state transition diagram:

### SIS Model

### SIS Model

Susceptible-Infective-Susceptible (SIS) model

Cured nodes immediately become susceptible

Virus "strength" : s = beta/delta

Node state transition diagram:

Models flu:

Susceptible node becomes infected

The ndoe then heals and become susceptible again

Assuming perfect mixing (a complete graph):

Models flu:

Susceptible node becomes infected

The ndoe then heals and become susceptible again

Assuming perfect mixing (a complete graph):

### Question : Epidemic threshold

### Question : Epidemic threshold Tau

### Epidemic Threshold in SIS Model

### Epidemic Threshold in SIS Model

### Experiments (AS graph)

### Experiments (AS graph)

### Experiments

Does it matter how many people are initially infected?

### Experiments

Does it matter how many people are initially infected?

### Modelling Ebola with SEIR

### Modelling Ebola with SEIR

### Example : Ebola

### Example : Ebola

### Example : Ebola, R0 = 1.5-2.0

### Example : Ebola, R0 = 1.5-2.0

## Application : Rumor spread modeling using SEIZ model

### SEIZ model : Extension of SIS model

## Application : Rumor spread modeling using SEIZ model

### SEIZ model : Extension of SIS model

### Recap: SIS model

### Recap: SIS model

### Details of the SEIZ model

### Details of the SEIZ model

### Dataset

### Dataset

### Method : Fitting SEIZ model to data

SEIZ model is fit to each cascade to minimize the difference |I(t) - tweets(t)|:

tweets(t) = number of rumor tweets

I(t) = the estimated number of rumor tweets by the model

Use grid-search and find the parameters with minimum error

### Method : Fitting SEIZ model to data

SEIZ model is fit to each cascade to minimize the difference |I(t) - tweets(t)|:

tweets(t) = number of rumor tweets

I(t) = the estimated number of rumor tweets by the model

Use grid-search and find the parameters with minimum error

### Fitting to "Boston Marathon Bombing"

### Fitting to "Boston Marathon Bombing"

### Fitting to "Pope resignation" data

### Fitting to "Pope resignation" data

### Rumor detection with SEIZ model

### Rumor detection with SEIZ model

### Rumor detection by Rsi

### Rumor detection by Rsi

## Independent Cascade Model

Initially some nodes S are active

Each edge(u, v) has probability(weight) puv

## Independent Cascade Model

Initially some nodes S are active

Each edge(u, v) has probability(weight) puv

When node u becomes active/ infected

It activates each out-neighbor v with prob. puv

Activations spread through the network!

Independent cascade model is simple but requires many parameters!

Estimating them from data is very hard

Solution : Make all edges have the same (which brings us back to the SIR model)

Simple, but too simple

Can we do something better?

### Exposures and Adoptions

When node u becomes active/ infected

It activates each out-neighbor v with prob. puv

Activations spread through the network!

Independent cascade model is simple but requires many parameters!

Estimating them from data is very hard

Solution : Make all edges have the same (which brings us back to the SIR model)

Simple, but too simple

Can we do something better?

From exposures to adoptions

Exposure : Node's neighbor exposes the node to the contagion

Adoption : The node acts on the contagion

### Exposures and Adoptions

From exposures to adoptions

Exposure : Node's neighbor exposes the node to the contagion

Adoption : The node acts on the contagion

### Exposure Curves

Exposure curve:

Probability of adopting new behavior depends on the total number of friends who have already adopted

What's the dependence?

### Exposure Curves

Exposure curve:

Probability of adopting new behavior depends on the total number of friends who have already adopted

What's the dependence?

From exposures to adoptions

Exposure : Node's neighbor exposes the node to information

Adoption : The node acts on the information

Examples of different adoption curves:

From exposures to adoptions

Exposure : Node's neighbor exposes the node to information

Adoption : The node acts on the information

Examples of different adoption curves:

### Diffusion in Viral Marketing

Senders and followers of recommendations receive discounts on products

### Diffusion in Viral Marketing

Senders and followers of recommendations receive discounts on products

Data: Incentivized Viral Marketing program

16 million recommendations

4 million people, 500k products

### Exposure Curve : Validation

Data: Incentivized Viral Marketing program

16 million recommendations

4 million people, 500k products

### Exposure Curve : Validation

### Exposure Curve: LiveJournal

Group memberships spread over the network:

Red circles represent existing group members

Yellow squares may join

Question:

How does prob. of joining a group depend on the number of friends already in the group?

### Exposure Curve: LiveJournal

Group memberships spread over the network:

Red circles represent existing group members

Yellow squares may join

Question:

How does prob. of joining a group depend on the number of friends already in the group?

### Exposure Curve : Live Journal

LiveJournal group membership

### Exposure Curve : Live Journal

LiveJournal group membership

### Exposure Curve : Information

Twitter

Aug 09 to Jan 10, 3B tweets, 60M users

### Exposure Curve : Information

Twitter

Aug 09 to Jan 10, 3B tweets, 60M users

Avg. exposure curve for the top 500 hashtags

What are the most important aspects of the shape of exposure curves?

Curve reaches peak fast, decreases after!

### Modeling the Shape of the Curve

Avg. exposure curve for the top 500 hashtags

What are the most important aspects of the shape of exposure curves?

Curve reaches peak fast, decreases after!

Persistence of P is the ratio of the area under the curve P and the area of the rectangle of height max(P), width max(D(p))

D(P) is the domain of P

Persistence measures the decay of exposure curves

Stickiness P is max(P)

Stickness is the probability of usage at the most effective exposure

### Modeling the Shape of the Curve

Persistence of P is the ratio of the area under the curve P and the area of the rectangle of height max(P), width max(D(p))

D(P) is the domain of P

Persistence measures the decay of exposure curves

Stickiness P is max(P)

Stickness is the probability of usage at the most effective exposure

### Exposure Curve : Persistence

Manually identify 8 broad categories with at least 20 HTs in each

### Exposure Curve : Persistence

Manually identify 8 broad categories with at least 20 HTs in each

### Exposure Curve : Stickness

### Exposure Curve : Stickness

Technology and Movies have lower stickness than that of a random subset of hashtags

Music has higher stickness than that of a random subset of hashtags(of the some size)

Technology and Movies have lower stickness than that of a random subset of hashtags

Music has higher stickness than that of a random subset of hashtags(of the some size)

Last updated