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
3.1: Growing Random Networks
Loading...
Do curso por Stanford University
Social and Economic Networks: Models and Analysis
315 ratings
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.
Conheça os instrutores
Matthew O. JacksonProfessor
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.
© 2018 Coursera Inc. Todos os direitos reservados.
