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.

Â