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.

Â