0:00

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.

Â 5:20

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.

Â