Learn how to model social and economic networks and their impact on human behavior. How do networks form, why do they exhibit certain patterns, and how does their structure impact diffusion, learning, and other behaviors? We will bring together models and techniques from economics, sociology, math, physics, statistics and computer science to answer these questions. The course begins with some empirical background on social and economic networks, and an overview of concepts used to describe and measure networks. Next, we will cover a set of models of how networks form, including random network models as well as strategic formation models, and some hybrids. We will then discuss a series of models of how networks impact behavior, including contagion, diffusion, learning, and peer influences. You can find a more detailed syllabus here: http://web.stanford.edu/~jacksonm/Networks-Online-Syllabus.pdf You can find a short introductory videao here: http://web.stanford.edu/~jacksonm/Intro_Networks.mp4
5.7: Solving the SIS Model - Ordering (Optional/Advanced 24:16)
Loading...
来自 Stanford University 的课程
Social and Economic Networks: Models and Analysis
387 个评分
Explore Related Videos
At Coursera, you will find the best lectures in the world. Here are some of our personalized recommendations for you
从本节课中
Diffusion on Networks
Empirical Background, The Bass Model, Random Network Models of Contagion, The SIS model, Fitting a Simulated Model to Data.
与讲师见面
Matthew O. JacksonProfessor
Economics
Hi folks. So, we're back again and let's talk a little bit
more about solving this SIS model and getting
explicit expressions for the infection rates
when there exists a positive steady state infection rate.
And so, if you recall when we were looking at solutions,
we could find the steady state in terms of the theta which is
the fraction of people that you would meet randomly who are infected.
Then it was given by this expression and we can simplify this
by dividing each side by theta and we end up with an expression that looks like this.
And so solving this for the theta would then give us a solution.
So, let's first look at
a regular example with regular network so everybody has exactly the same degree.
Then P(d) is just going to put weight on
some particular degree which is just the expected degree.
And so then things simplify and we end up with
1 = Σ P(d) λd^2 /[ (λθd+ 1) E[d]].
So, that's going to simplify and we'll end up with an expression which looks like this,
1= λE[d]/ (λθE[d] + 1).
So, just plugging in that everybody
has the same degree which is just the expected degree,
then we can get rid of this, Σ P(d),
this is going to become E[d]^2,
and this is the expected degree here, expected degree here.
We can get rid of one of these,
get rid of that and we end up with this expression here, okay?
So, when we solve that we end up with a very simple expression.
Now, we can rearrange this in terms of theta and we
end up with θ = 1 - 1/ λE[d]).
So, if everybody had the same degree then we can solve explicitly for what
the steady state expression is going to be for the infection rate.
And we notice now that this is increasing in λE(d) and in order for this thing to
be at least zero then we need λE(d)
to be greater than
one or greater than equal to one or greater than one for it to be positive.
So, that was what we found in regular networks and
then this thing just scales up with lambda and with
the expected degree so it's actually just linear in the level of λE(d),
which is effectively just this infection rate.
So this is one where it goes back to the original model we looked at where we just had
random meetings and this is just increasing the rate of random meetings
and things are just proportional to the lambda parameter.
Okay. So, let's have a look at a more interesting degree distribution,
one where we have this power law,
and if you plug in the power law
and integrate this out
then you'll end up with an expression that you can solve for theta.
And, in that case if you want to go through and verify,
you can just integrate this and then solve for
theta or you can take my word for it and theta
will come out to be θ = 1 /(λ(e_1/λ - 1) ).
So, what do we end up with?
We end up with theta having an expression which
depends on lambda and we can plot that out.
So, if you plot that function out,
so we're just looking at this function right here,
and plotting this function as a function of lambda.
So, how does it vary with lambda?
And what we see is it's very rapidly increasing.
So, as lambda increases we get a very rapid increase and then eventually it asymptotes.
It can't go above one,
but we're getting a very high neighbor infection rate
as lambda increases because then we've got these very high degree nodes.
They become infected, they infect others and so forth,
and as lambda is increasing,
we get a very rapid infection increase.
Okay, what can we say about how these things change with the degree distribution?
So, if we want to do comparisons and say okay,
if we go from regular to power law or a regular to Erdos Renyi, sort of, graph?
How is that going to change?
And one way we can do that is we can look at this expression
and ask how this right hand side changes with P(d).
Right, because remember the way that we're solving this,
we look at theta here,
we have this right hand side,
which is H(θ) and we're looking for
the solution to this thing and if we can say that H(θ) goes up,
right, so if we do something that changes H(θ) in a way that goes up then
that's going to move the solution to this equation upwards.
So, any kind of comparative static where we're making changes
that change the distribution in a way that
increases this overall expression on the right hand side for each theta gets
a higher value then we can say something about what the resulting change is in theta.
So, let's see what we can say about how this right hand side moves.
Okay. So first thing,
if you look at this function,
what we're doing is we're weighting it by
different degrees and then we've got some function
here that we're taking an expectation over with respect to the different degrees.
And, what can we say about this function right here?
How does it behave?
And one thing we notice,
so we're taking expectations with respective degrees,
this thing is increasing in degrees, okay.
So higher degree nodes are going to have
higher relative expected infection rates and basically that's what we're getting here.
This is remember our old P(d) and so,
this thing is going to tend to be higher for higher degree nodes.
So, more connected nodes are going to tend to have more contact,
they're going to tend to be more infected so this overall function is increasing
in D. So that tells us that any distribution which puts weight,
puts more weight on higher degree nodes,
is going to have relatively higher infection rates.
That's going to move this whole function up.
That's going to give us a higher solution and a higher steady state.
Okay. So one thing we can say is that if we take a distribution and then shift it,
so that we put more weight on higher degree nodes,
that's known as first order stochastic dominance
when you are comparing two distributions.
So, if we have two distributions and we move it towards
higher degree weights then that right hand side of this thing,
this H(θ) is going to increase that
every theta we're basically gonna have higher infection rates.
That's going to lead to a higher steady state.
Okay. So, basically putting weights on
higher degree nodes is going to increase infection.
Okay. So, that's relatively straightforward and
basically we're just shifting the weight towards higher degree nodes.
So when we do that we end up with shifting this H function
higher at every theta and that leads us from a steady state with P. So,
if we go to P prime,
which is increase the weight on higher degree nodes,
we're going to end up with an increased steady state
so the theta that solves this is going to be higher.
Okay. So, let's take another look at this.
So that just says that if we are all shifting weight towards
higher degree nodes in a very well-defined sense
this notion of first order stochastic dominance.
And just to, sort of,
give you a feeling for first order stochastic dominance,
if you're dealing with a frequency distribution
where you've got different degrees down here,
you know, say one, two, etc.,
three, so you've got some degree distribution.
First order stochastic dominance shifts are ones where we're
essentially moving the distribution to the right so we're putting
more weights on higher degree nodes and that's
what's moving us up and having us have more interactions,
higher infection rates, everybody gets a higher steady state of infection.
So, if you have, you know,
when you look at the world and you have increased travel or
increased contact with people,
you're going to have increased spread and things like the flu or other.
In this particular model,
it's something you can catch repeatedly but you're going to have increased contacts
and increased number of contacts per individual are going to
increase the steady state infection rate.
Okay, that's fairly intuitive, fairly simple.
Let's do a little more nuanced calculation now and again we're looking at this function,
this RHO of D function,
so the infection rate for different degrees.
And if we look at that function,
it's also a function which is convex in D, okay.
So if you look at this function,
it's a function of d squared over something which is linear in D. This
is actually a convex function in D. So, in fact,
when you look at what this RHO of D function looks like,
it is not only increasing,
so this function is increasing and convex, okay.
So, that tells us, okay, first of all,
if we put more weight on higher degrees we're going to end up with
higher values for this are going to come out.
Right, so as we, we put on higher degrees,
we get, here is degree,
here is this RHO of D function,
and as we put weight on higher degrees we're getting higher values.
That was what we just showed but also even if you took a mean preserving spread,
so suppose instead of putting all your weight on some particular value E of D. So,
we start with a regular network and instead we spread it out,
so that now we have half our weight on something lower,
half our weight on something higher,
but we move these in equal distance.
If we keep the same mean then when we take the expectation over the higher and lower,
we're going to end up with a higher expected value than what we started with.
Okay. So, the idea is if you're taking an expectation of
a convex function and you do a mean preserving spread,
so you move some weight higher and some weight lower,
when you're moving lower, well,
the rate at which you slow down decreases,
but here you get an increasing rate at which you get higher values.
So the convexity of this function means that the expectation is higher.
So, if you take a mean preserving spread,
so if you start with some P and you
take some expectation with respect to P of some function,
in this case our row of D,
and now you take a mean preserving spread, P prime,
and you take the same expectation of RHO of D. If this is a mean preserving spread,
so you've kept the same mean but you've spread out and put more weight on the extremes,
then what you're going to end up with is a higher expectation
and that's going to lead then to a higher value of the right hand side here, okay.
So this is a form of what's known as
a second order stochastic dominance where you fix the mean.
So, taking mean preserving spreads on convex functions gets you a higher expectation.
So, since this is a convex function,
we can say that mean preserving spread is also
going to increase things and this is why, you know,
so even though you're losing some degree on some nodes,
you're increasing it on other nodes.
The fact that those are hub's could actually increases the expectation overall.
So, if P prime is a mean preserving spread of P,
then the right hand side increases at every theta and so what happens?
Well, it increases everywhere.
We end up with a higher steady state, okay.
So, either way that we went through things, mean preserving spread,
more high degree nodes and low degree nodes,
but the higher degree nodes are more prone to infection.
Neighbors are more likely to be high degree.
So, either first order stochastic dominance or mean preserving spreads,
both of those lead to increases in the infection rate.
So here we are now able to say something about
the degree distributions of interactions and how infection rates,
so it's a nice model in terms of allowing us to be
able to do these kinds of calculations.
Okay, what about average rates?
So, what we've been talking about is theta, right?
So, theta is the chance when you're meeting somebody in the population,
that they're infected and that has been what we showed was increased,
as we increased in the senses of first or second order stochastic dominance.
But what about the actual average,
the RHO in the population?
Okay. So, if we take expectations over all degrees.
So, the higher degree people are going to be infected at higher rates.
So, when you're meeting them at higher values that means
that people you're going to meet are more infected but
if we're somebody who just cares about the average level in the population.
So, if I'm a government and I care about how infected my population is, ultimately,
what I care about is what Rho is,
not what theta is.
So, theta is very important in determining what
the steady state is going to be but the thing I might be
interested in in terms of my policies is
what fraction of my population ends up being infected?
Okay. So, in work with Brian Rogers we looked at
this question in more detail and interestingly the things can
reverse themselves when you get to looking at Rho compared to theta.
So, if you look for instance at what we just
did where you take a mean preserving spread of
a distribution then the highest steady state of theta, that goes up.
So, we end up with a new theta prime which is higher than what it was before.
But, the corresponding Rho,
it goes up if lambda is relatively low,
but it actually goes down if lambda is very high.
So, if you've got a very high infection rate, lambda,
then the corresponding Rho prime goes
up in the case where lambda is low but it actually goes down if lambda is high.
Okay, and what's the intuition behind this?
So, let's sort of go through the intuition and then we
can take a quick look at why this is true.
The intuition is that,
that in situations where lambda is very high,
the high interaction nodes are already going to be very infected.
And so, actually increasing,
in putting weight on higher degrees
isn't going to matter that much because those nodes are
going to be infected at such a high rate that they're going to already be infected.
And so you're not changing that much but putting
more weight on low degree nodes can actually decrease the,
so now you've got some people who have very few interactions.
Those people can actually end up being infected with lower rates.
So, the actual overall infection rate in
the society can be balanced by the fact that you are increasing some of
the higher degree nodes but those people are already going to
be infected even without this increase and
the low degree nodes as you move them towards lower part they can actually end
up with lower infection rates and so that counterbalances it.
So, when you average across the population,
not with the relative frequency of meetings,
you actually end up with a decrease in the overall rate.
So, in terms of pictures,
here's what the picture looks like.
So, here's our, this is actually log of lambda
in this picture and then this is the largest steady state RHO.
So, this is the positive Rho in equilibrium and the blue figure,
these are regular networks,
and these all have the same mean.
Regular network, this one is a power law,
the green one and the red one here is one for an exponential.
So basically, the growing version of
the Erdos-Renyi random network all with the same mean,
it's what you see is the framed is relatively low then
the regular one has everybody right at the mean is the lowest.
Spread it out in terms of exponential, it increases things.
Spread it out even further in terms of going to a power distribution so here,
as you increase the variance,
you end up increasing the relative Rhos so that's what's happens for low lambda
but once you get to very high Lambda the picture completely flips itself and
the regular one has
the highest infection rate and the power one actually has the lowest infection rate.
So these things can reverse themselves as you get to
higher lambdas and that's because Rho
is actually something you're weighting things by
their frequency in the population not by meeting rates.
And so, if you actually want to go through a proof of this,
I'll just go through a quick proof.
So, one way you can do this is remember in a steady state you have to
have these changes in Rhos be equal to zero.
So, zero is equal to this expression,
which is the change in Rho that we got before, which, you know,
remember our expression for what the change in
the infection rate of anybody's given degree was per unit of time
and, again, that was some recovery.
This is the rate at which they recover.
This is the fraction that aren't infected.
This is the rate at which they become infected depending on theta.
And if you just take,
so we've got an expression which looks like this thing is equal to zero.
Now just, let's take an expectation over D.
So we'll just take an expectation over D. What do we end up with?
We're going to end up with V theta D,
times to one take an expectation of that,
you get this expression,
take an expectation of this,
you get that expression,
take an expectation of this you get the actual overall Rho times Delta and
so what do we end up with is an expression where this first one looks like V times theta.
This, if you take that expectation,
is just our definition of what theta was.
So, we get theta squared times E of D and then the minus Rho of D.
And so, you can solve this for how Rho behaves as a function of theta.
So now, what we get is Rho is equal to something which is proportional to theta.
But also, times one minus theta.
So this, so what we can do is as we look,
change theta, how do,
how did that change Rho.
Well, the right hand side here is increasing in theta,
theta is less than a half but
it's decreasing in theta if theta's bigger than a half, right?
So, once theta's bigger than a half then this thing actually starts
decreasing in theta so this is proportional to theta times one minus theta.
This is an increasing function once,
up to one half and then decreasing thereafter and so,
what happens is initially as you're increasing theta you're
increasing Rho up to theta equals a half
and then beyond that,
as theta continues to increase,
Rho actually decreases above this level of a half.
And so what we get is,
initially we get an increasing part of Rho and then actually
then increases in theta lead to decreases in Rho, okay.
And overall we also have that theta as
increasing in lambda so then you can do comparative statics of Rho in
terms of lambda because the lamda's going to change
the theta which then changes the Rho, okay.
So, what we've done is gone through the SIS diffusion model,
our most useful model just to get
some comparative statics out and to study some techniques.
So, these techniques of actually looking at
distributions and talking about changes in degree distributions,
doing stochastic dominance, actually turns out to be quite useful.
It's been used now in other areas besides in
the original paper with Brian Rogers but now been used in games,
on networks and other areas as well.
And the SIS model is a very simple and tractable model.
So, it's very stylized.
It's nice because it brings in relative meeting rates which has
some elements of network structure.
And then we can order infections by properties of
networks in terms of degree distributions.
What are some of the limitations of this model?
Well, important limitations are, first of all,
just in terms of this SIS we lose the fact that a lot of
applications are ones where you become infected but then if you
recover you're actually immune to catching the disease again,
which is actually true of some flus and other kinds of things where if, you know,
if you add new virus protection software to your computer then you won't
get certain viruses again and you get a new virus but not the same old one.
So it limits, it's somewhat limited in terms of the applications.
Also the interactions that we talked about were completely random meeting processes.
So, it was not as if we'd drawn out
a network and actually had people located on the network.
We just had people bumping into each other and meeting each other and so
that's a special kind of process which gives rise to special kinds of conditions.
Now we, more generally what we'd have to do if we start
to work with things where the network architecture is given,
then it's going to be more important to use simulations and so forth.
So, we did some calculations before where we talked about
component science and so forth and that gives us some insights.
But, more generally if we actually want to study
these processes a lot of it's going to be done by simulation.
So, if you give me a particular network and ask what's going to happen on it then
I might have to write down a program and actually simulate what's going to happen there.
So, the next thing we'll look at is a simple model
of diffusion where we'll do some calculations and just
simulate that model and see exactly how it
works and that will allow us to actually fit something directly to data.
And there's a large amount of that that goes on in
epidemiology and marketing and
other kinds of areas where you're trying to make predictions.
If you know something about the network you're working with you can actually simulate
things and that's going to go a long way towards improving your accuracy.
So, the SIS model gives us nicer intuitions,
simple ideas, but it's not one you're going to easily take to data.
We're going to have to enrich the model to fit it to networks.
And that's what we'll talk about next.
