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.