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