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