Now that we have looked at,
uh, the G_np model.
Let's move on and talk about the small-world model,
and the small-world model,
um, what- the goal of it will be- it,
uh, it will try to- to give us two things.
It will try to give us the average shortest path length to be small,
but it will also give us high clustering coefficient.
And the- the point why this is interesting,
because these two forces kind of go one against the other, right?
You get shortest path length to be small.
If you have a random graph where we have a lot of
these random connections everywhere, right?
But then if you have a lot of random connections,
you have- you- you have low clustering coefficient as we see in, uh, G_np, right?
So if you want low diameter, uh,
be like G_np's, but the problem is you have no triangles,
you have no local structure.
So we have low clustering coefficient.
If you have, let's say
a very irregular network like this lattice where, you know,
uh, you have this triangle,
so you have quite high clustering coefficient.
Everything seems nice, but now the diameter of this thing will be long because it
takes a huge number of steps to get from one corner to the other corner.
So kind of the tangent is the following,
is that regular lattice type grounds they have
high clustering coefficient because nearby nodes are connected to each other.
The problem with the structure is that it has high diameter.
You know, on the other hand,
random graphs have no local structure,
have low clustering, which is bad,
but they have low diameter,
which we also find in real networks.
So the big question is,
can I have both?
Can I have a small diameter but still a lot of clustering coefficient,
a lot of this local clustering structure,
a lot of triangles,
a lot of friend of a friend is my friend type,
uh, structures in the network.
So, um, the point is that this clustering implies what we call edge locality, right?
It basically, um, it implies that friend of a friend is a friend, right?
So it means that if two people, um,
have a friend in common,
then that is more likely to be edge there.
But the problem is that this edge is now just
locally connecting two people that are already connected.
And you cannot use this edge to connect different parts of the network.
So your diameter becomes large.
And we saw that the MSN network has seven orders of magnitude,
larger clustering coefficient, then the corresponding random graph, right?
So it's a huge difference, right?
So 0.11 is massive.
It's a massive clustering coefficient, right?
And to give you an example in- in- in other- for other cases,
for example, this is a movie actor collaboration network.
Here the- I'm telling you the average shortest path length, uh,
on- in the actual graph versus
the random graph with the same number of nodes and the same number of edges.
Um, and you see that, you know, average, uh,
shortest path lengths correspond quite nicely
between the actual graph and the random graph.
While here I have clustering coefficient between the actual graph, and the random graph.
And you see that that is orders of magnitude difference,
at least one order of magnitude.
So at least factor 10,
if not, you know, a few hundred, um,
between the actual clustering coefficient,
and the clustering coefficient in the corresponding random graph.
And this is between movie collaboration networks,
uh, electronic power grid, uh,
you know, stuff that the ways wires are connected to provide power,
like power to Texas.
Uh, and the C. elegans network, uh, which, uh,
is now a network of how neurons in the C. elegans worm are connected with each other.
And again, in all cases you see we have relatively short
shortest paths as nicely captured by an Erdos-Renyi random graph,
but the clustering coefficient is far higher than what a random graph gives us.
So the controversy, or the contradiction,
or something that is unclear is- is the following, right?
The consequence of expansion,
is that shortest paths exist, right?
This means basically that networks that have high expansion, um,
have small diameter because we can,
uh, get it, uh,
if we, uh, by simply traversing, uh, the graph.
But the problem with- with expansion and problem when
you- when you have short paths is that you have no clustering.
You have no local structure.
Um, triadic closure, meaning friend of a friend is
my friend type behavior leads to this local clustering of edges, right?
You have this edge that is close to the friend of a friend.
But the problem is that with high clustering.
You run out of the edges that would serve us kind of shortcuts across,
uh, different parts of the network.
And the problem then becomes that your clustering,
yes would be very high because you close a lot of triangles.
But the problem will be that now your diameter is high as well,
because it takes a long time to navigate from one part of the network to the other.
So the big question is, can we have both?
Um, and here's the idea.
The idea is that we wanna interpolate between
regular lattice graphs and G_np, uh, random graphs.
And, uh, the model that allows us to do this is called the small-world model.
And it will actually lead to high- to high clustering coefficient and low diameter.
So basically we will borrow the best from both sides.
We are going to have local structure,
so we have high clustering coefficient and we are going also to
have shortcuts so that we have, uh, low diameter.
So how do we achieve this?
So G_np, um, has two, uh,
sorry, uh, the small- the small-world model has two components.
First is- we wanna start with the low-dimensional regular lattice like a set of nodes,
uh, on a circle.
And here a node connects with its immediate neighbors and neighbors of neighbors.
So that's why this will have high clustering coefficient,
but also notice it has high diameter because to get from one- one node to the other,
you have to kind of navigate around this, uh, circle.
So I have high clustering,
I have high diameter.
What I will do now is,
I will do in the second phase,
I'm going to introduce some randomness.
I'm going to introduce shortcuts.
And what this means is that I'm going to add and remove
edges to create shortcuts between the remote pairs,
uh, on the- on the lattice- on the circle.
So basically for each edge with probability p,
I'm going to move the endpoint to a random node.
So the idea is that, you know,
I pick a- a- a random edge and I take one of its, uh,
endpoints and select it at random and rewire that edge to the other end.
So this would mean that for example,
this edge from black to, uh,
from blue to black, I would rewire.
It still touches the blue,
but it now connects to some other, uh, random node.
And then this is p, right?
Then the way you can think of it is,
um, on the left,
I have my starting lattice where I have high clustering and high diameter.
On the- when I have p equals 1,
when all the edges are rewired,
then I have a G_np random graph model.
I have low clustering and low diameter.
And what turns out is that for some intermediate values of p,
I- I retain both.
I have enough shortcuts so that enough edges rewire.
So the diameter is small.
And I still have a lot of, uh,
these original edges present so that the clustering, uh, is high.
So basically this rewiring mechanism allows us to interpolate between, uh, the, um,
uh, high clustering, the regular network,
and the, uh, random graph.
And if we create a plot of the following where on the x-axis,
we create the rewiring probability,
and then on one side of the axis we- we
plot the clustering coefficient here in dashed line,
and on the other axis we plot average shortest path length.
And notice how clustering coefficient remains high even as
the- as the probability of rewiring increases and only then starts to decrease.
But the shortest path length drops very quickly as I keep increasing, uh,
the rewiring probability p. So it means that there is this range of
p where I have high clustering but low shortest path length.
And this is what we call the small-world, right?
It's- it's a network that is heavily clustered but still has short, uh, shortest paths.
So to summarize the small-world model,
um, you know, could we have a network with high clustering?
Uh, and the same time,
uh, be a small-world,
meaning have small diameter?
And, uh, the answer is yes.
And you know why?
Because you don't need more than just a few random links to bring the diameter down.
So basically the diameter,
the shortest path lengths are
much less robust property than the clustering coefficient, right?
For- to have a low clustering coefficient,
you need a lot of edges in triangles,
but to have low diameter,
you just need a couple of random shortcuts along distant parts
of the network and that will collapse the diameter very- very quickly.
So, um, what's the significance of the small-world model?
It provides insights into the interplay between the clustering and small diameter.
It captures the structure of, uh,
many, uh, real-world networks.
Uh, and it accounts for high clustering in- in those networks,
um, but what is still missing is,
uh, the degree distribution, right?
The- the- in- in- how- the way we defined the small-world model,
uh, all the nodes have the same degree.
You know, in our case,
I think all the nodes had degree 4 which each- which
is kind of unrealistic as we saw from the messenger network.
But just, um, basically through these two models that they have presented,
I wanted to show you how really you can- you can think of this
as a- as a way to explain formation of networks.
And you can think of it as a way to,
um, capture different properties of the network.
And think about what kind of processes might be happening in the real world,
in, you know, in our everyday social networks that give rise to the networks.
Uh, with properties that we actually observe, uh, in real life.