3.1: Growing Random Networks

Loading...

Do curso por Stanford University

Social and Economic Networks: Models and Analysis

407 classificações

Stanford University

Social and Economic Networks: Models and Analysis

407 classificações

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

Na lição

Random Networks

Poisson Random Networks, Exponential Random Graph Models, Growing Random Networks, Preferential Attachment and Power Laws, Hybrid models of Network Formation.

3.1: Growing Random Networks17:42

3.2: Mean Field Approximations 8:12

3.3: Preferential Attachment 10:56

3.4: Hybrid Models 14:45

3.5: Fitting Hybrid Models 17:05

3.6: Block Models 9:37

3.7: ERGMs 9:05

3.8: Estimating ERGMs 15:58

3.9: SERGMs 9:43

3.10: SUGMs 6:00

3.11: Estimating SUGMs (Optional/Advanced 21:03)21:05

3.12: Week 3 Wrap3:16

Conheça os instrutores

Matthew O. Jackson
Professor
Economics

Okay, hi folks, we're back again, and we'll be talking a little bit more about

Random Networks. And in particular, we're going to start

looking at Growing Random Networks. So, situations where there are new nodes

entering over time. And, so this fits into our study of

network formation. So in terms of the course, we are now in

the second part of the course. And we're looking at Network formation

models. And again, we've looked at Static Random

Network models. And now we're going to be looking at

Dynamic, Random Network models. Where there's growing numbers of nodes

over time. And there's lots of examples where this

happens in the world. So, the prime example is citation

networks. New articles are born over time.

New articles can form links, by citing old articles.

Old articles can't cite new articles. so articles are going to accumulate links

over time. Newer articles are going to have fewer

links then older ones, so there's a natural form of heteragenania that forms

this way. Same thing with the web, in terms of web

pages. Collaboration networks and

co-authorships, you have older researchers, younger researchers older

researchers will have had more collaborations than younger ones.

Societies you known generally human situations you're going to have some

older. And some younger and they're going to

have different characteristics based, just simply, solely on age.

So there's a natural form of heterogeneity.

That comes in in form of age. So let's think a little bit about what

they add. why do we care about having growing

random networks? Well you know, one answer people say okay

what's more realistic. And one thing I want to emphasize just

from the start is when we build models, we know that we're not going to try and

capture everything in the world. And so, realism is not usually a good

reason for building a model to, to try and match reality.

the, the reason that we build models, is to try and use as few moving parts as

possible in order to pro, reproduce the world.

So the only reason we want to add this feature of growing random networks is not

because that's the way the world is. But because this richer model might

capture something in the real world that was not captured in the static models.

So again, you, you shouldn't judge models based on realism.

They're always wrong. the question is are they capturing

reasonable elements and so here. The natural form of heterogeneity versus

age is going to be useful in getting out more connected nodes and less connected

nodes. And, and starting to see, power laws and,

and fat tails. So we're going to get a natural form of

dynamics. And in particular, we're going to end up

with a natural way of getting different degree distribution without just building

them into the statistical distribution. So, we could just assume that there's a

distribution that has the, the, the features of reality.

But instead we want to do is see if build a model that will end up generating.

Features that look like the real world, and this sort of dynamics is going to

help quite a bit. Okay,[COUGH] , so in, in order to start

this, what we're going to do is start by taking Erdos-Renyi random network

situation. but instead, just enriching it to have

nodes being born over time. And so that'll be a simple benchmark,

that'll give us an idea of some of the techniques.

And then we can enrich it to have different kinds of formation processes

besides the uniform at random. Okay, so, this idea of growing and

uniformly at random, what we're going to have is each day is going to be a new

node's birthday. So nodes come in at time one, two, three,

four, etcetera. And when they are born, they will form a

number of links to existing nodes. And, to start, in terms of this

Erdos-Renyi kind of setting. What we're doing, we're going to assume

that each mode is going to form it's links, uniformly at random to the ones

that are already existing out there in society.

Okay so you're born, you decide who to link to, you form some numbers of links

and you form them to over the existing node.

To keep things simple, we're going to have the, the link formation process only

occur when the node is born. So you don't keep forming them over your

lifetime. You'll get new ones as new nodes are born

and they form their links. But a, a given note only forms it'[s

links it, it, it's outward links in some sense when it's born.

But it can accumulate more links later on as new nodes are, are forming their

links. Okay.

So in order to have some nodes that you can form links to when you're born what

we're going to do is each one is going to form m links at random.

So, we'll have m nodes that are already existing which are fully connected so

that when the first node is born it has somebody to connect to.

So the, the process is going to start out, we'll start it with a very simple

seed of already having some m nodes fully connected.

You could start with a whole series of different situations.

That's not going to effect the asymptotic limit of it, it might effect what it

looks like for the short periods of, of time, until you get to a very large time.

Okay, new node is born, it forms m links to existing nodes.

Say two, three, four, how, what, whatever, how, however many we want.

And what that means, is if I'm already born and, there's some time t then I'm

going to have a probability That's, that's roughly m of the, the

number of links being formed, compared to t of the existing number of, of nodes

that are, are already there, of, of getting one of the new links, right?

So, m over t will give, give us the probability.

So, the more nodes that are out there over time the less chance that any

particular node is going to get one the new links, right?

Okay, so very simple process, but, it, it's going to have some dynamics to it.

Okay. So, now let's think about sum node i,

that was born after the original m nodes that we started with that we fully

connect and, and before sum time t. Okay.

And now let's ask how many links has it, does it expect to have collected by time

t? Well, the first thing is, that it forms

some m links when it was born. So it's going to have m links for sure.

Then in terms of expectations, the next day after it was born, if it was born at

time i, then the date now is, i plus 1. And there's some new node which is born

and it's forming it's m links. There's already existing i plus 1 links

nodes out there. And so it has a chance m over i plus 1 of

getting these new links, okay? And then at time, the next state there's

i plus 2. It's going to, a number of new links are

formed, and so forth. Right?

So, so this is the overall sum of what it's going to get over time.

Right? So, we had the first m that it got when,

at birth, you expect it from the next node born, and so on.

So it has this sum.

[BLANK_AUDIO].

Now, if you want to look at a sum like this.

So, you look at this kind of sum, what is an approximation for this sum, well these

are harmonic numbers. So if you can if you remember your, your

number theory, these are what are known as harmonic numbers.

So, they're growing proportionately to i plus some number so it's growing

proportionately to the inverse of t. And if you sum a series like this an

approximation for this is going to be m times 1 plus log of t over i.

So, depending on, on how far you go out and when you started this series.

You're going to end up with sum that looks like this.

So, we have an approximation for what the expected degree is of any node, after

some time period t. Okay?

So, very simple calculation. And now what can do is we can ask what

does this generate in terms of the distribution of degrees in society.

Or the distribution of expected degrees in society at any point in time?

Okay, so let's do a simple calculation. How many nodes have an expected degree of

less than d at sometime t? Well, it's those for whom their expected

degrees at time t are less than some d. Right?

So if you say okay how many are going to have degree less than 100?

Then we can ask that. How many are going to have degrees less

than 35? We'll get some numbers.

So, at time t, it's going to be the i's for which this inequality holds.

Okay, so let's have a look at that inequality in more detail.

So, let's suppose that we did this calculation at time 100.

So, we've got here our t is 100. And let's suppose that each node at each

time is, is forming 20 new links. So, what does the degrees of different

nodes look like at time100? So here we have the birth date of the

node. So, here is birth date of the node and

this is then the equation that we had. So, so, so this is our equation that we

had in terms of m times 1 plus log t over i, right.

So, this equation right here is m times 1 plus log t over i.

So, that's plotted out here. And what that means is, as you can see

the older nodes, have gotten more links than the younger nodes.

So, the youngest node is only formed at 20 and not gotten many more.

Some of the slightly older nodes have gotten a little bit more than 20 because

they've happened to get some of the new ones.

These ones have been around for a longer time, they have gained more links.

And the, the, the reason you have curvature here, is always easier to get

links early on. And as more and more nodes are born, it's

harder and harder to get the new links. So, ones that are born later and later,

are going to have a harder time getting new links than the ones that we're born

earlier and could get one. So, you get a natural curvature here,

just due to that fact. Okay.

So, what do we get? well we can do the same thing for degrees

at time 200. And at degree time 200 we'll have a

slightly different curve. And you know, the ones that were born at

100, time 100, now I've had a chance to gain more links.

Everybody's gained more links. how much they've gained more, depends on

what their birth date was. And now we've got the, the 200th, node

born has just formed it's initial 20 links, and so forth.

So, we're going to get different degree distributions at different times.

We'll have a different, a, this is expected degrees over time.

we'll have a different distribution as time evolves.

Okay, so what does this distribution look like?

Well, we can ask then what are the nodes for instance, that have degree less than

35? What's the fraction of nodes?

So, let's go back to our time 100, and figure out what is a distribution

function. So, what is, you know, how many nodes?

What does F of d look like. So, how many nodes have degree less than

some d. So, what does F of 35 look like, alright?

We can do that kind of calculation. Okay, these are the nodes with degree

less than 35, are the ones are expected degree less than 35.

there's going to be some node, which has expected degree right at 35.

And basically the nodes with degree, expected degree less than 35, are

going to be the ones that were born afterwards, right?

So, these ones. So, if we want to figure out the fraction

of nodes that were born after, that have degree less than 35.

It's going to be the ones that were born after this, compared to the overall 100

that exist in the society so far. So, let's go through that calculation.

So, what we want is the actual amount that they have, the expected degree they

have. Remember that this is m1 plus log t over

i. So, here we have t is 100, m is 20.

So, these are the nodes for which this equation is less than 35.

Okay we've got that, and so if we solve that equation.

Then what do we end up with? We end up with, these are the i's for

which they're greater than, you know, you just take exponentials of both sides of

this, solve out for i. And what you'll get is these are the i's

for which, they were born after time 47.2.

So, basically the ones that were born 48 or later are going to have expected

degrees less than 35. The ones that were born 47 and before are

going to have expected degrees, bigger than 35.

So, this is 47.2, this point right here, and now if you want to ask, what's the

fraction of nodes that have degree less than 35?

[SOUND] Well, that's going to be the 47.2.

So, we're going to have 100 minus 47.2 over 100.

Right? So, this is going to work out to be,

0.628. Right.

So, the, the fraction of nodes that are you know, rough, roughly 63%, are

going to be the ones that have degree less than 35.

So, some where between 62 and 63% in this case have expected degrees less than 25.

Okay? So, given this process we can figure out

how degrees grow. We can figure out a degree distribution.

And, more generally for any degree, the ones that have expected degree less than

d at some time. Are going to be the ones for which i is

bigger than same solution as we just saw for the 35 t times e at the exponent of

minus d minus m over m. Okay.

So, if you go ahead and solve that out, what we'll end up with is a degree

distribution at time t. That says the fraction of nodes that have

an expected degree of less than d, is given by this formula 1 minus e minus to

the minus d minus m over m. Okay, so very simple set of calculations,

little bit of algebra invovled, some exponentiation, some summation of series.

But basically what we're able to do is now calculate what the degree

distribution looks like for this growing for this growing random network.

this is a exponential, negative exponential, distribution.

So what we have is the distribution of expected degrees is such that d minus m

is exponentially distributed with a mean of m.

what about the actual degrees? Well, a good approximation for large t,

we're going to have to you know, so, so here we did the calculations of expected

degrees. Right?

So we, we, we can say how many each node expected, and we got a nice curve.

Well some, some nodes are going to happen to get more, some are going to happen to

get few. So, the actual degrees of the true nodes

are not going to follow that really nice, smooth curve.

They're going to bounce around a bit. And what that means is that the

distribution can be slightly different than this distribution of expected

degrees. it turns out that this distribution of

expected degrees, is a good approximation of what the actual distribution of

degrees will look like. Some will end up pushed above, some will

end up pushed below. But on average, you'll still expect

around 60%, less than 35 and time 100 and so forth.

So, if you go through and actually calculate the true distribution function.

It's going to look as t becomes large, it's going to be well approximated by

this negative exponential function. Now actually doing that, you need some

careful law of large numbers argument I'm not going to do that here.

I, in the book there's some discussion of how you go about doing that.

It's fairly straightforward. Again, it's just making sure that the

variation in the actual distribution isn't too large.

As you get to a large t, the noise in the system is going to be well approximated

by the mean. So, so here we've got a distribution of a

growing random network things have worked out well.

Okay, so in terms of where we're going next we'll look at slightly richer

growing models. We'll also talk about mean field

approximations, other kinds of ways of calculating these things.

So, we'll at at another set of growing random network models that will allow us

to get richer and richer, the degree distributions out.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2019 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play