One of the most important contributions of
Watts and Strogatz's paper was

presenting a simple model of how small-
world networks can be formed.

That is, how a network could be formed
that has low average path length,

yet, still has high clustering.

Here's how the model worked:

The model works by starting with the a
regular network.

By regular, I mean that every node has the
same pattern of connectivity.

For example, this node is connected to
each of its neighbors, on either side.

And similarly, this node has the same
pattern of connections, and so on.

So we're going to say that there's N total
nodes, M neighbors per node, with capital

M being the number of links. So for this
example we have 10 nodes. Each node has

2 neighbors. And thus there's a total of
10 links. What's going to happen in this

model is that some of these links, which
are right now between nearest neighbors,

are going to be rewired. That is, they're
going to be ripped apart and then

reattached to some distant neighbor, to
model the making of a distant connection.

In this model, there's a parameter, called
beta, which is the probability of rewiring

each link. For this example, let's let
beta equal 0.2.

That means each one of these links has a
probability of 0.2 of being rewired.

So right now, the way that this is going
to work here, is we're going to randomly

choose beta times M links.

So that's going to be 0.2 times 10, which
is 2.

So I choose 2 links, the ones that now
appear in red,

just chosen at random, and I'm going to
rewire one end

of each of those links to another randomly
chosen node.

So here's where I rip them off their
existing end and reattach them to a

randomly chosen node. So here's our new
network, where most of the connections are

between nearest neighbors, but there's 2 
exceptions that are long-distance

connections. As usual, we're going to look
at an implementation of this model in

Netlogo. Here's what the interface of the
model looks like:

We have parameters 'node-count,' that's
how many nodes there are; how many

neighbors each node has; and our beta
parameter, the probability of rewiring

So if I could do setup, I have 10 nodes,
each connected to its nearest neighbor,

so each node has 2 links, 2 neighbors,
and I set beta to 0 now, so there's no

probability of rewiring, nobody's
rewired.

Now, we can look over here, and we can see
the degree distribution. This shows that

all the 10 nodes have degree 2, we
already knew that.

This also tells us the global average
distance between pairs of nodes - 2.5 hops

and the clustering coefficient - 0 - no
clustering in this one.

There's a couple of other things we can
do. For instance, we can click on this

'show-neighborhood' button and then click
on a node, and the neighborhood of that

node is shown. We can also show the link
distances, and click on a node, and that

says from this node, here are the
distances to that node.

So those are different things we can do.

I click 'setup' again to clear those.

Ok, so now, I can change beta.

So what happens if I change beta to 0.1,
which means that one of the links will be

rewired. I click setup again, and you see
this link was rewired.

Here the global average distance went up,
but that's because we have so few nodes.

Ok, so let's do this for a more realistic
number. Let's do 100 nodes, beta back to 0

Setup. Now you see that same regular
pattern of links, will 100 nodes

Global average distance is 25 hops.

Now let's change beta to 0.5, 5%. Now we
do setup.

Now remember that here, beta is the
probability that a node gets rewired.

So each node has a 5% probability of
getting rewired

And actually rewired a lot of them

And we see that global average distance
went way down, from 25 to 9.24.

So this relatively small percentage of
rewiring allowed the distance to decrease

dramatically. It also changed the degree
distribution.

Ok, now let me try rewiring 10% of the
links

Well, it went up. But if we do it again,
it goes down, because it's random.

There's a lot of randomness here. We
still have low clustering.

Clustering shows up when we have more
neighbors

So let's change the neighbor count to 4

The beta back to 0

Here, each node is connected to 2
neighbors on either side

If I change beta here, here the
distance is 12.75.

Let's make beta 5% again, 'setup'.

Here, both the global average distance
decreases dramatically, and the clustering

increases. You'll get a chance to play
with this small-world network model for

the homework. Let's finish off this
sub-unit by a summary of what we learned

about small-world networks. We saw that 
there's a spectrum of networks from very

regular to very random. Regular networks
have high average distance between nodes

and high clustering. The high clustering
comes in if you have more than just the

2 neighbors. Here we have 4 neighbors per
node. Then a random network has small

average distance but low clustering.
Whereas the small-world networks, which

are in some ways more like real world 
networks, have small average distance and

high clustering, similar to the real
world networks that Watts and Strogatz

investigated