Okay so now we're going to talk a little bit about random networks and, and enriching them to start to capture some properties that we actually observe in real networks and we'll talk about small world. And before I get in to that, let me just sort of put in context where we are in term of the course. Again, we're talking about network formation now. random network models and we had a whole series of properties that we observed in real networks that are sort of stylized facts that, that sometimes emerge in different contexts and we might begin to start thinking about, well what kinds of models would we need to match that and so. simple Erdos-Renyi networks gave us some insight in to why the average path links might be small. But one thing that they didn't do very well was give an of of clustering, so we saw that that social a lot of social networks that one observes actually have clustering coefficients which look significantly different Than what would have happened if we were just working with a Erdős–Rényi random network. So somehow, those networks are missing features that are actually going on. So, when we look at enriching models, what we might want to do is, is start to generate some clustering. So how can it be that we get clustering. which is, is non trivial and you know, that's going to be one thing we might be interested in. the other thing we saw, we saw that the distributions didn't necessarily match the Erdős–Rényi random graphs. We saw these fat tails. Can we generate models that have different tails? can we generate more flexible classes, general classes of models to, to fit data? So that's where we're going and in particular we're going to start by just asking you know, something about clustering. And then we'll move on to sort of enriching the model to become richer and richer, and, and try to fit more things as we go along. okay, so, err, an early paper, Watts and Strogatz paper in 99, was basically asking the question, how do we match these two different features of networks, small average path length together with high clustering in one model. In the, one important observation is that the Erdos-Renyi model misses clustering because the clustering is on the ordering of p which is going to have to go to 0 unless the average degree is becoming very, very large. And, you know, with billions of, of people in the world is not as if we each have billions of heighbours. we, we have a, you know, hundreds or thousands of neighbors. So the idea is that, we, we need to have something which captures the, the, high clustering, and yet has, a small p. and, and so their idea was what they we're going to do is, is a, has a, a following observation. Those started with what's known as a ring lattice, a very particular structure of a network, and then randomly picked some links and rewired them, okay. And the idea is you, by starting with this lattice structure you start with a network which had very high clustering but also has high diameter. And then you just change a few links in it. And the idea is that as you begin to change these links, that actually you don't need to change many links in order to get a very low diameter. So a few randomly placed links will actually shrink the diameter of a graph very quickly. Any average path length as well. And if you don't rewire too many, you sort of keep this high clustering. And so let's have a peek at that, and and then we can talk a little bit more about some of the conclusions of it. So here's just picture I drew of here of a set, a set of nodes. So 25 nodes in a ring lattice. And so initially they're connected, each node is connected to its two immediate neighbors. So if we look here we have node one, and it's connected two and three, and also connected to 25 and 24. Right? So it's got these connections going here and here. and then, each one of the nodes is, in terms of these in terms of the red, have connections to the, the different neighbors, okay? So we've, we've, we are connected to your 2 neighbors. What that does is, in terms of this original lattice is give you very high clustering. So 1 is connected to both 2 and 3, and 2 and 3 are connected to each other. 1 is connected to the 2 and 25, and 2 and 25 are connected to each other. And so forth. So the clustering is is high when you start. And then what you can do is is actually what I've done is this picture is rewire the links but just to had a few random links. Links. So let's just stick a few random links in a network. And so what happens is initially if you wanted to get without these initial, without these random links here, if you wanted to get from node one to node 15 your path length would be quite far. Right? You'd have to go sort of marching around the circle. Your path length, especially if you expanded this thing to be a much larger graph, your path link would be quite far. By putting in these few connections, these extra ones, now to get from 1 to 15, you just go, you know, you've got a, a fairly short path, right? You're connected in a, at a distance 4. to get from one to 14, you know, you're connected at a distance three. So a few of these extra things allow you to get so one can get to ten now through, in, in just two hops, and so forth. So a few extra links actually dramatically shortens the average path length. but it doesn't change the clustering too much. Right? And if you just, you know, deleted some links, but some of these new ones in, as long as you're keeping it in the sort of sweet spot, what Watson Strogeth noticed Wwas that you could just do a little bit of rewiring that shrinks the diameter dramatically, and yet you keep reasonably high clustering. Okay? Now of course, if you look at this network, and you look at the, the shape of it, it's still not going to match a lot of real-world networks. why not? Well, because, you know, a lot of these nodes basically have degree four still, or, or, you know, fairly regular. So it's, it's not going to fat, match the fat tails and other kinds of things that we actually observe, but what it does do is it begins to sort of answer some of the questions so that if that for some reason we had high clustering on our, on, to start with in terms of some local level And then we just add a few random links on top of that. We can get at least two features in common, right, so it gives us some explanation of how these things can begin to arise in common. You don't need many random links to actually shorten average path length dramtically. Now, you know, this model is far from one we would want to take to data. But it begins to put some different things together. And what we'll going to begin to do now is start to enrich the models so that they're at the level where we can begin to look at different things, put them in, take them to data and then ask things about, you know, are we reproducing a lot of the features that we actually observe in, in real world networks. So, we'll, we'll take a more detailed look at random networks.
