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.