Propagation Models

Network Structure and Propagation

• Diseases, rumors, viral social media, fake news all spread the same way in social networks
• Models for understanding disease help us understand how other things spread in networks
• Questions
• How does this relate to network structure?
• How can we spread spread information better?
• How can we prevent the spread for a disease?

Propagation in Networks

Each pixel is a person. We want to spread a news. Darkening of a pixel means getting exposed to that news.

​

The closer two pixels are, the closer they are in the physical world

​

We want to see how each situation looks like after 8 days

Propagation in Networks

When we choose 500 random seeds as the first who were exposed to the news, the network is not that much affected

​

We do see clusters

Propagation in Networks

When we choose most popular users, things look drastically different.

​

Almost the whole network is now exposed to the news

​

Within only 8 days

Firefighter problem

• Simple network: a grid where each intersection is a node
• Fire starts at one point
• 1 firefighter can be deployed to protect a point at each time step
• Fire spreads to all unprotected adjacent vertices in the next time step
• Repeat

Firefighter problem

Firefighter problem

• Try this out with different firefighter placements
• How much of the network can you protect?

Disease Models

• S Susceptible
• I Infectious
• R Recovered/ Removed
• E Exposed

Disease Model States

• S Susceptible
• They don’t have the disease, but they can be infected by it
• I Infectious
• They are infected and they can spread the disease
• R Recovered/ Removed
• Got the disease, recovered or died, means they cannot spread the disease
• E Exposed
• Exposed to the disease, but not yet infectious
• Usually some diseases have incubation period
• We wont talk much about E, too complex

Disease Modes

• SI
• Susceptible
• Once you catch the disease, you remain infectious forever
• HIV, Herpes etc.

Disease Modes

• SI
• Susceptible
• Once you catch the disease, you remain infectious forever
• HIV, Herpes etc.
• SIR
• Susceptible
• Once you catch, you are infectious for a while
• Once recovered, you cannot catch the disease again
• Chicken pox, mono

Disease Modes

• SIRS/ SIS
• Susceptible person get sick
• Is infectious now
• After recovering, enjoy a period of immunity, is susceptible again
• Then gets infectious again
• Strep throat
• Bacterial diseases

Disease Modes

• What about fake news context?
• Which model does apply when it comes to spreading fake news?
• SI? SIR? SIRS?
• What does it mean to be susceptible? Infectitous? Recovered?

K-threshold models

• Disease is transmitted if k adjacent nodes are infected
• 1 threshold
• C is infected if either A or B or both A &B are infected

C

A

B

K-threshold models

• Disease is transmitted if k adjacent nodes are infected
• 2 threshold
• C is infected if at least 2 of its neighbors are affected

C

A

B

K-threshold models

• How do k threshold models work for information spreading?
• What does it mean to have a 2-threshold for news spreading?
• How can you use this to build strategies?
• Spread meme? Viral video?

C

A

B

Exercise

• S/I/R models and threshold in this network
• K and F are infected
• We want to see how quickly the disease will spread

Exercise

• Suppose, SI model and 1 threshold
• 1 neighbor infected, the node will be infected
• Once affected, always remain affected

​

Exercise

• Suppose, SI model and 1 threshold
• 1 neighbor infected, the node will be infected
• Once affected, always remain affected
• So, at t = 1
• PQABO are infected by F
• LPJ are affected by K

​

​

Exercise

• Suppose, SI model and 1 threshold
• 1 neighbor infected, the node will be infected
• Once affected, always remain affected
• So, at t = 1
• PQABO are infected by F
• LPJ are affected by K
• At t = 2
• All the nodes will be infected!
• Check them out!
• So, in 2 steps, the entire network is affected

​

​

Exercise

• Suppose, SI model and 1 threshold
• 1 neighbor infected, the node will be infected
• Once affected, always remain affected
• Try this out with a 2-threshold model
• SIR model
• You recover after 1 timestep and cannot catch it again

​

​

Exercise

• Suppose, SI model and 1 threshold
• 1 neighbor infected, the node will be infected
• Once affected, always remain affected
• Who do you immunize?
• Suppose no matter what, you want B to be protected. Make sure B does not even need vaccines
• How do you make sure of that?

​

Acknowledgement

• Professor Jen Goldbeck’s slides