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.
