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.
