5.4: Giant Component Poisson Case

Loading...

En provenance du cours de Stanford University

Social and Economic Networks: Models and Analysis

316 notes

Stanford University

Social and Economic Networks: Models and Analysis

316 notes

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

À partir de la leçon

Diffusion on Networks

Empirical Background, The Bass Model, Random Network Models of Contagion, The SIS model, Fitting a Simulated Model to Data.

5.1: Diffusion12:57

5.2: Bass Model12:21

5.3: Diffusion on Random Networks 9:08

5.4: Giant Component Poisson Case 15:09

5.5: SIS Model17:50

5.6: Solving the SIS Model 9:17

5.7: Solving the SIS Model - Ordering (Optional/Advanced 24:16)24:16

5.8a: Fitting a Diffusion Model to Data (Optional/Advanced 22:47)22:45

5.8b: Application: Financial Contagions (Optional/Advanced 12:47)12:48

5.8c: Application: Financial Contagions - Simulations (Optional/Advanced 13:41)13:42

5.9: Diffusion Summary 3:45

5.10: Week 5 Wrap4:25

Rencontrer les enseignants

Matthew O. Jackson
Professor
Economics

Okay, so we're back and we're going to talk a little bit more about computing

the size of a giant component in a random graph and in particular,

we'll focus in on poisson or GMP random graph, [inaudible] random graphs.

And, so we're doing giant component calculation and we're going to do sort of

a heuristic calculation but one that turns out to be fairly accurate.

And the idea here is we'll just do the following kind of calculation.

Let's let q be the fraction of nodes in the largest component.

Now, let's look at a given node and if we just pick a node at random,

the chance it's in there is q.

But another way to figure out that chance that a given node

is in the giant component has to be that all of its neighbors are

outside of the giant component if it's outside the giant component or if it has

any neighbor inside the giant component it'll be inside the giant component.

And so that'll give us an ability to do a calculation.

So the probability that a given node is outside the giant component,

so it's not in the giant component,

is 1-q since q is the probability that it's in there.

But that's also equal to the probability that all of its neighbors are outside.

So if the node has degree d,

if it has d neighbors,

then the chance that each one of those is outside of

the giant component is (1-q) we raised that to

the dth power and we end up with

(1-q)^d is the chance that it's outside the giant component.

And so what we can do is just look at the expected degree,

take an expectation over this based on the probability of it having

different degrees and then find an equation based on that.

So we have this q,

we're going to try and solve for q.

So the probability that you're outside the giant component that's 1-q,

it's also the probability that all of your neighbors are outside the giant component.

You have d neighbors.

What's the probability that you have d neighbors?

Well, it's given by a degree distribution.

So p(d) here is our degree distribution,

so this is the chance that you have

d neighbors and once we've got a degree distribution then we can solve for q.

Now this is a calculation you could do.

It's a heuristic calculation because I'm not worrying

about correlations and some of these variables.

I'm treating this as if they're independent.

They're not quite independent.

You can do a more exact calculation using generating functions.

There's some of that in the book but this will give us

a fairly good approximation and work fairly well especially on large networks.

So what we want to do is solve for q.

Now, this is an equation so far that doesn't require

us to work with a specific degree distribution.

You could plug in any degree distribution you wanted into

this and then solve for what q is.

It's a non linear equation so it's going to be a

little difficult to solve for a closed form for q,

but you can plug in whatever degree distribution you want and then

solve that for q or get

an approximate solution for q as a function of your degree distribution.

So this is a nicely well-defined equation.

And basically, when we look at this

there's always going to be a solution of q equals zero.

So there is one solution to this equation which has q equals zero.

Right? So we're basically solving this equation.

One possibility is, well,

if we put in q equals zero here and q equals zero

here then we're just summing across all degrees for the probability of d,

we get one on both sides.

That's always going to be a solution.

The interesting solution to this is going to be the one where we have a non-zero q.

So we want to solve to a non-zero q.

So one possibility is we assume everybody is outside

the giant component and then everybody ends

up outside the giant component because all their neighbors are.

That's the nonsensical solution in a lot of situations so the one we want to solve

for is going to be the one where there's a positive solution to this equation.

So if we look at this and try and solve for

the positive solution it's going to be the point where 1-q is equal

to the ∑(1-q)^d P(d).

And so we're trying to solve for what's,

what 1-q is solve this simultaneously,

that gives us a solution to q. That's what we need.

You could solve this for different degree distributions.

Let's do it for the case of GNP or approximately a poisson random graph.

So we'll plug in a poisson distribution for PFD.

So we have the poisson distribution here.

So this is the probability that a given node that has degree d is given by this formula.

And when we plug that in then we end up with this equation.

So now we can solve this for q and this looks like a daunting equation.

It's got sum over factorials of d. So again this is sum over different ds.

We've got factorials here.

It looks like a fairly nasty equation.

But luckily there are some nice parts to this equation.

So when you look at things that look like sums of

some expression raised to the d over d factorial,

that actually has a nice exponential form.

So that sum is a nicely behaved sum.

And one useful approximation,

just to have in the back of your mind,

is that when you look at writing down a Taylor series approximation for e^x,

that looks like ∑e^x/d!.

So Taylor series approximation tells you that e raised to

some power of x is the same thing it's suming x to the d over d factorial.

So you've got a nice expression here and in particular when we go

back we look like we're summing something to the d over d factorials.

That's going to look like an exponential.

So when we plug in that expression now we say we can

rewrite this given our formula as exponents of what's inside here.

So we rewrite this in a nice form so that

now we've got 1-q is equal to this expression here.

Okay? And collecting terms,

sum of our P simplify here and we end up with e^(-q(n-1)p).

Remember that (n-1)p is the expected degree, right?

So P is the probability of any link,

multiply that (n-1) times,

that's the the expected degree.

So what we end up with is here 1-q is equal to e^(-qE(d)) and if we

take a log of both sides we get -log(1-q)/q= E(d).

So a very nice simple equation.

Now we've got a relationship between the q

on the one side and the expected degree on the other side.

So now we've got an expression that tells us how

large the giant component is as a function of the expected degree.

It's not quite a solution directly in q because it's

-log(1-q)/q but what we can do is at least plot this out and see what it looks like.

So if you plot that out as a function of the E(d)s and then see what the qs look like,

basically what happens is as q gets close to one there is no giant component, right,

so q is very small at one and then the giant component

grows and by the time you get up to three as an expected degree,

your q is actually very large.

It's already close to 95%.

So by a degree of three we've already hit close to 95% in

terms of the size of the giant component and at one we're close to zero.

So this is interesting and this is, you know,

somewhat characteristic of these rationally random graphs.

We get these Tyche phase transitions.

So if people have expected neighbors

less than one expected interactions that would transmit a diffusion of less than one,

we don't get diffusion.

Once you hit one we get a diffusion and then

it grows fairly rapidly and by the time you have

three interactions then we're already to the point

where you're very likely to hit most of the population.

So if you remember in our promo video I said tell at least two friends.

Well, if you tell just one friend about this then we don't get much diffusion.

Two friends is at least enough to start pushing us fairly far along this.

And you get to three friends and you're most of the way there.

So just in terms of giant component size here we are.

We see that there's a fairly tight transition from having

no giant component to having almost everybody being

connected and so most of the play is in this one region.

And indeed when people study epidemiology there's

this idea that having at least one contact that's going to transmit something

if people are doing more than one you're going to get diffusion or contagions and if

people are having less than one transmission then things are going to die out.

And that makes perfect sense. You need at least, you know,

more than one and it's growing,

fewer than one and it's shrinking.

That's the critical point.

And then here we find that it actually

transitions very rapidly so that by the time you've got

three interactions that are likely to lead to

contagion then our diffusion is quite extensive.

Okay, so given that,

we can also do calculations of what's the probability of being in a giant component.

Well, this was the probability that you weren't in the giant component.

Probability that you are is one minus that,

this is increasing in d,

it's an increasing function of d. M basically that just tells you more connected,

you're more likely to be infected.

And this is exponential M d. So

it tells you that increasing your interaction rate makes it much more likely,

exponentially more likely that you end up in the giant component.

So you're more likely to be infected at any point in time if we do a

dynamic and much more likely to end up infected.

And this gives us some insight behind that Coleman,

Katz, and Menzel finding,

that the people with more interactions we're adopting the antibiotic,

prescribing antibiotic at an earlier time.

So here we see this directly in terms of this model.

Okay, extensions.

Let's talk about some extensions quickly.

Immunity, well, that's easy.

If some nodes are immune then they can't catch something.

They can't transmit it so we can just drop those out of

our model to begin with and then study the giant component on the remaining nodes.

And what's that's going to do is actually decrease the degree, right?

So if we have some fraction of the nodes that disappear then that's going to decrease

the degree and that decreases the overall interaction.

In terms of probabilistic infections, you know,

we just have links fail and we can incorporate that directly into the link probability.

So we can think about, you know, some nodes initially exposed to infection.

We could have some fraction pi of the nodes that are

immune and we can think

also that maybe only some of the links are actually going to transmit.

Let's let a fraction f of the links transmit and then we ask what's the extent of

the infection and basically we can just start with our network on end nodes,

we delete some fraction of the nodes,

delete some fraction of the links and we look at what's left.

And if we get an infection in the giant component on what's left then we'll get

to reach whatever the giant component is

on what's left and otherwise we don't get an infection.

So it's a very simple extension to start to incorporate these things and, you know,

if we let q be the fraction of knowledge remaining on

the network and the remaining network in the giant component,

then q times 1-P is the probability of having a non-trivial contagion and that's also,

sort of, the extent of the infection.

So basically what we can do is just resolve

the equation where now what we've got is we're going to have

a lower expected degree for the individuals plus moving that down to lower given the fact

that they're not going to have as many neighbors because some of those neighbors are

immune and then also scaling down by the f. And

once we've done that we end up with basically the same exact equation

just taking these two modulations into effect.

And so what we end up with is a similar curve as we had before but now what

we have is on the x axis the expected degree.

The one that's, sort of, relevant here is now

modulo the fact that some

of the nodes are going to be missing and some fraction are going to transmit.

And so it has to still be at least one out of what's

remaining in this and then going up to three.So you can just do direct calculations,

this just scales things back.

So implications. The infection can fail now if pi is high enough or

if f or p are low enough so that basically puts you below the one.

So high pi, high immunization, low f,

low contagiousness of the process,

low p, low contact among the population.

So you can think of these different modulations

to what we had before and that's going to affect the eventual process.

Okay, so that takes us through

a quick look at component size and doing these kinds of calculations.

This has been for a process that just spreads through one network.

The next thing we're going to look at is an ongoing process where people

can change back and forth between state one and zero.

So maybe you support somebody, you don't,

you like a technology, you don't like it.

So you can change your mind over time or there are certain kinds

of diseases that people can catch and then re-catch.

And so, you know, these are ones that can last in the population.

So I can clean my computer of a virus,

get the virus back,

it can infect other people and so forth.

So I can go back and forth between the states zero

and one over time and we can look at that kind of model as well.

That will be the next thing we have a look at.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2018 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play