0:00

Here you see three different graphs. What I'm plotting on the x axis is the

neighbor's influence, under y axis is node I state This is node I state and this is

neighbor's influence. The first graph is actually for random

walk model, that we'll talk more about in this lecture's advanced material part of

the video. This and this graph are, are depicting

contagion and infection respectively. For contagion there is a certain threshold

above which you flip, so it's a binary state.

And for infection here however, we'll get to see that an impact on topology can be

modeled by looking at your neighbors' influence.

On your state in a probabilistic way, with a certain slope which is beta Si So, in

particular, when we look at a given graph of connectedness with associated adjacency

matrix A, then we can write down the infection influence model's dynamics

through a different set of differential equations, incorporating this adjacency

matrix. Let's take the simple SI model,

Okay? .

1:29

Then, for node I is not a general global population percentage anymore.

It is the probability that node I is in the state of being susceptible at time T.

So, we have to interpret this as the probability that node I is in state S.

And that probability evolve over time, where the -B beta,

Okay times the summation of all the neighbors.

Let's assume this is a bidirectional graph, so AIJ equals AJI.

That could be zero or one, depending whether J's neighbor of I or not.

If it's zero, the rest of the term doesn't matter.

If it's one, then we look at what would happen.

It would be SI times IJ of T, again, I here is the state of, the probability that

node J finds itself in the state of being infected, SI is the probability that node

I finds itself in a state of being susceptible at time T.

2:41

Okay, we can also write out DI for node IDT, but that would just be minus the

above. For the simple SI model.

So, let's just focus on this expression here.

This expression is in fact, incorrect. It's wrong because, we can't actually

write this down as such. What we actually need to write down in

English, okay, is the following is to write down this as one single entity.

Is the joint probability, okay, that mode I in the state of S and node J in the

state of I, Okay?

And what will that probability be? Then we need to know the probability that

some neighbor of node J, other than node I itself, got to the current state of

infected. Got to the current state by being infected

and then making node J infected. So you have to look at all the neighbors

of node J, that induces this joint probability of node IJ in this state.

But in order to do that you have to look at these neighbor's neighbors.

4:11

And the trajectory of the state transition in the past have led to this state.

As you can see this quickly gets out of hand, it's no longer tractable.

So what we're actually doing is to stop this propagation tracing back, and say,

let's approximate. One standard way to approximate out of

several that we mentioned in the textbook, is the auto-based approximation.

The first auto-approximation actually says, well, let's just pretend that this

joint probability can be written as the following memoryless the composed product

of two individual probabilities. This is actually an approximation.

But, having written down this approximate, then we can say, well.

This SI is not dependent on J. So, we can pull this out of the equation

and start doing approximation. So, let's do that approximation here.

Let's write down, for example. The I-I times t and its rate of change

with respect to t, is beta, okay? Times SI of T after this first order

approximation and pulling SI out of the summation over J times the summation of

AIJ times IJ of T Now this is S, is just one minus I by definition.

5:48

And now, we have to make yet another approximation to say that during the early

time of infection, the percentage of in, the probability of find yourself infected

is very small. So approximate this by erasing this part.

And now we can write this down as a vector equation.

Write a probability of each known may finds itself in the infected state at time

TSI. This is not identity matrix in this

lecture, okay? It's just some vector of these entries stacked up equals beta times

the matrix A, Adjacency matrix times this vector at time

T. This is almost the exact same as before

the scalar evolution, except now is a vector evolution with a, a weighting by

this adjacency matrix A representing the topology's impact.

Again, we can apply the trick to represent this vector S, a weight of the sum of

eigenvectors of the adjacency matrix as before.

Skipping the derivation, we see that the solution of this vector of probabilities,

is the summation of some weighting factor, It doesn't matter times E to the beta

lambda K times T times of VK. These VK's are the eigenvectors of the

adjacent symmetric A of this given draft index by K.

And the summation by K. N is our weighted by this exponential

factor E to the beta. Beta is the given disease spreading right

times. The current time T times the corresponding

eigenvalue so as time goes on, the largest eigenvalue will dominate effect and thus,

going back to our little story again., Okay? Now, I want to end this model, and

therefore actually this lecture. And this sequence of two lectures on

influence model with case study, on the disease of Measles.

Measles is an infectious disease that causes about 1,000,000 deaths worldwide

each year, but in developed countries the population is sufficiently vaccinated.

It effects very few people. Each year was called a herding immunity,

in the sense that there is enough immunized population that the infection

would not cause an, a pandemic, One is a herd immunity then.

8:29

So, we want. S of zero at initialization times sigma to

be less than one to prevent the infect population from flaring up.

That means we need S of zero less than one over sigma.

That means when you need initial recovered presumably through vaccination program,

population percentage being bigger than one minus one over sigma.

From missiles people have estimated from previous outbreaks of the infection that

the sigma is very big, is about 16.67. That means we need.

9:08

This initial, vaccinated rate to be 94%. Which is big but not that close to 100%.

Now, however, the vaccination is not always effective.

It's only about 95% effective. So, that translates we actually need the

vaccination rate to be 99% in order to achieve herd immunity, to achieve this

condition. So, back in 1963 in the US okay?

A measle population started drop because of the introduction of the measles

vaccination but then still stayed around 50,000 people every year.

In 1978,,. The US government tried to, make the

immunization coverage wider to eliminate measles but it dropped to about 5,000, but

stayed around there. In fact, sometimes it went up to 15,000.

So, just increasing the coverage of immunization didn't help.

In 1989, US Government introduced the two dosage program.

So you have to get one dosage when you're around one year old.

Another around five years old before you go to school, a public place, all the

time. And this time, the two dosage program,

which is much more expensive than the single dosage program, was able to achieve

the vaccination rate, 99% needed to counter this large sigma of 16.65 for

measles in order to satisfy this condition, and thereby, achieving Herd

Immunity. And indeed, since then, the number of

reported case of measles dropped to under 100 within a few years time.

11:11

This is a very interesting story, showing the power of the particular differential

equation model we just developed for infection.

Now, we have touched upon four influence models together with three more in the

vast material part of these two lectures videos All together, seven influence

models which one to use is an art. And there is a big gap between theory and

practice. But some take home messages offer

insights. For example different ways to think about and quantify importance of

nose and links. For example in today's lecture of the

contagion model and optimal seeding being a difficult problem and infection model

that we just talked about, How differentiation model change of states

allow us to make some prediction and a very useful public policies.

So with that we finish the influence model part of the lecture and we move on to the

topology reverse engineering part. So see you in the next lecture.