0:00

Okay, folks. So, let's have a deeper look now at these

growing random network models. And in particular we're going to look

start talking just about Mean Field Approximations, a useful technique for

solving these kinds of models. So, one thing we can do is instead of

actually working out the expected number of links that each node is going to gain

over time, we can use a Continuous Time Approximation.

Which will allow us to just solve a differential equation to figure out what

the nodes expected degrees should be over time.

So what we can do, let's, let's just go back and, and think again about our

simple Erdos-Renyi variation where now each node is born, forms m links at

random to the existing ones. But we'll, we'll just smooth this out and

do a Continuous Time Approximation. So, what do we end up with in terms of

the basic structure here? Well, first of all, the starting

condition. When a node i is born so its degree at

time i is going to be m. So, when its first is born, it forms its

m new link. And then, how does this degree change as

we change time? So, what's the differential of the degree

of i with respect to time t? well, this, this differential is

expecting to gain m links over the time period, right, so there's t existing

nodes, m new links being formed, so its chance of getting one of those is m over

t. So, it's gain per unit of time is

going to be proportional to m over t. And so now, we have a differential

equation which says that this is the change over time, this is the initial

starting condition, and that's something that's fairly easy to solve.

So, if you fall or solve a differential equation with this starting condition and

this differential, what do you end up with?

You end up with di of t is equal to m plus m times log t over i.

It's exactly the same equation as before and then, you know, you can just do the

same of the, of the calculation where we try and figure out, well, how many nodes

have degree less than 35 at some time t. Well, that's going to be the ones for

which this equation is less than 35. And so, figuring out the distribution

function once we have this degree over time is quite simple, okay?

So, this is just saying that, that we could have done this with a differential

equation can be quite a bit easier. Basically, you know, we, we set up

starting conditions, a differential, and then if you either remember your

differential equations, or you can go and, and look them up and find the

solution for this kind of equation. Okay, again so what we've got now is

we've talked about these growing distributions.

Let's get into them and a little more detail now.

So, we said this is a natural form of heterogeneity via age and we saw that and

the other distribution. Older nodes are going to have more links.

it gives us a form of dynamics and in particular this is going to give us a

natural way of varying degree distributions by making different

assumptions about the way that new, new nodes form their degrees.

So, depending on how they form those, we can end up with different degree

distributions. So, let's have a, a closer look at that

question. so, preferential attachment is one of the

most well-known of these alternative methods of forming new links in one of

these growing systems. And this is different than finding, just

forming links uniformly at random. And in particular, it's going to help us

get things like other degree distributions such as, say, a Power Law

where we have these fatter tails, more degrees that have an extremely high and

extremely low number of links. So, again just to remind you Price's

finding in, in Citation Networks was one of the early sets of evidence on this

where Citation Networks had too many that had no citations, too many with high

numbers of citations for these things to be coming uniformly at random.

it exists in a lot of other settings, wealth, city size, word usage, a lot of

things have these kinds of fat tails. And we saw this in terms of the Albert,

Jeong, and Barabasi analysis of the Notre Dame part of the world wide web.

Where we see that the number of nodes that have high degree and the number of

ones that have very low degree exceed what would be coming up if it was

uniformly random. And, in fact just to, to let you know

now, this curve is the one that's actually coming from a growing random

network. The exponential one that we just saw, and

in fact, we're still seeing these things exceed that curve.

So, when I, when I talk, talked about this being a random, a uniformly random

network earlier in the course, in fact, this distribution corresponds to

uniformly random but one with growing numbers of nodes overtime.

And so, we, we, that's not quite enough to capture these fat tails still though,

we've got a fatter tail than that. And power, these kinds of Power Law

explanations work by Simon in, in the 1950s gave an explanation for how this

might occur. And there's sort of two different

properties, which are important in these kinds of systems.

One is that new objects growing coming in over time, so we've got our new nodes

coming in over time. And the other is a sort of rich get

richer. So, the more links you have, the easier

it is to get links. so more wealth you get, the easier it is

to get more wealth. The bigger your city is, the easier it is

to get more population. These kinds of things where you get a

multiplicative growth together with new objects being born over time, so new

articles, new cities, in this case new nodes.

those things being grown born over time are going to gain proportionally to how

large they already are and we'll, we'll end up with power loss.

So, the preferential attachment Price had a paper which worked at a simple version

of this through Citation Networks. Barabasi and Albert generalized this to a

more general class of, of preferential attachment things.

And again, the previous models aren't generating fat enough tails.

And so now, what we're going to have is, nodes are still going to be born over

time, just as we talked about before. But now instead of forming links at

random with existing nodes uniformly at random, the probability that links are

going to form is going to be proportional to the number of links that a node

already has. That’s going to be the rich get richer

part and that’s the preferential attachment I prefer to attach to nodes

that already have high numbers of links, okay?

So, that’s the, the system that we’re looking at.

If you generate a network that looks like this, so here's 25 links preferential

attachment simulation and what do we see? Well, we begin to see, if you look at

some of the older nodes, the nodes born in early time periods, two, three four,

they have many more links than the ones that were born at later time periods.

So, in this case, everybody was forming two links.

The ones that were born later high number of nodes 23, 15, 25 here, 21 manages to

get an extra link. So, there's a few that, that gained extra

links that were born late. But most of the ones that gained extra

links were ones that had links to begin with.

And then, it was easier for them to get more links, and the more you get, the

more you grow. And, in fact, the largest degree node

here is, is node 2 and so, we see a system which has preferential attachment

and we see a more skewed network than we see if you had an Erdos-Renyi kind of

system. So, what we're going to do next is take

a, a deeper look at exactly what the distribution is, how we can solve that

for preferential attachment. And then, begin to look at the comparison

between preferential attachment and other models of network formation.