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)