1
00:00:01,166 --> 00:00:06,136
One of the most important contributions of
Watts and Strogatz's paper was
2
00:00:06,168 --> 00:00:11,118
presenting a simple model of how small-
world networks can be formed.
3
00:00:11,153 --> 00:00:16,373
That is, how a network could be formed
that has low average path length,
4
00:00:16,413 --> 00:00:18,846
yet, still has high clustering.
5
00:00:18,856 --> 00:00:20,812
Here's how the model worked:
6
00:00:20,862 --> 00:00:24,637
The model works by starting with the a
regular network.
7
00:00:24,642 --> 00:00:29,722
By regular, I mean that every node has the
same pattern of connectivity.
8
00:00:29,739 --> 00:00:35,039
For example, this node is connected to
each of its neighbors, on either side.
9
00:00:35,044 --> 00:00:39,044
And similarly, this node has the same
pattern of connections, and so on.
10
00:00:39,061 --> 00:00:45,911
So we're going to say that there's N total
nodes, M neighbors per node, with capital
11
00:00:45,934 --> 00:00:52,944
M being the number of links. So for this
example we have 10 nodes. Each node has
12
00:00:52,955 --> 00:01:00,575
2 neighbors. And thus there's a total of
10 links. What's going to happen in this
13
00:01:00,588 --> 00:01:07,258
model is that some of these links, which
are right now between nearest neighbors,
14
00:01:07,261 --> 00:01:13,111
are going to be rewired. That is, they're
going to be ripped apart and then
15
00:01:13,129 --> 00:01:18,659
reattached to some distant neighbor, to
model the making of a distant connection.
16
00:01:18,669 --> 00:01:25,219
In this model, there's a parameter, called
beta, which is the probability of rewiring
17
00:01:25,229 --> 00:01:29,226
each link. For this example, let's let
beta equal 0.2.
18
00:01:29,226 --> 00:01:36,546
That means each one of these links has a
probability of 0.2 of being rewired.
19
00:01:36,546 --> 00:01:40,781
So right now, the way that this is going
to work here, is we're going to randomly
20
00:01:40,781 --> 00:01:43,896
choose beta times M links.
21
00:01:43,896 --> 00:01:48,116
So that's going to be 0.2 times 10, which
is 2.
22
00:01:48,116 --> 00:01:53,065
So I choose 2 links, the ones that now
appear in red,
23
00:01:53,066 --> 00:01:57,166
just chosen at random, and I'm going to
rewire one end
24
00:01:57,166 --> 00:02:01,066
of each of those links to another randomly
chosen node.
25
00:02:01,067 --> 00:02:06,707
So here's where I rip them off their
existing end and reattach them to a
26
00:02:06,707 --> 00:02:13,015
randomly chosen node. So here's our new
network, where most of the connections are
27
00:02:13,019 --> 00:02:17,019
between nearest neighbors, but there's 2
exceptions that are long-distance
28
00:02:17,019 --> 00:02:21,449
connections. As usual, we're going to look
at an implementation of this model in
29
00:02:21,449 --> 00:02:26,338
Netlogo. Here's what the interface of the
model looks like:
30
00:02:26,338 --> 00:02:31,645
We have parameters 'node-count,' that's
how many nodes there are; how many
31
00:02:31,650 --> 00:02:37,130
neighbors each node has; and our beta
parameter, the probability of rewiring
32
00:02:37,130 --> 00:02:45,007
So if I could do setup, I have 10 nodes,
each connected to its nearest neighbor,
33
00:02:45,007 --> 00:02:50,892
so each node has 2 links, 2 neighbors,
and I set beta to 0 now, so there's no
34
00:02:50,907 --> 00:02:53,767
probability of rewiring, nobody's
rewired.
35
00:02:53,772 --> 00:02:59,732
Now, we can look over here, and we can see
the degree distribution. This shows that
36
00:02:59,743 --> 00:03:03,743
all the 10 nodes have degree 2, we
already knew that.
37
00:03:03,778 --> 00:03:10,068
This also tells us the global average
distance between pairs of nodes - 2.5 hops
38
00:03:10,078 --> 00:03:14,528
and the clustering coefficient - 0 - no
clustering in this one.
39
00:03:14,539 --> 00:03:18,809
There's a couple of other things we can
do. For instance, we can click on this
40
00:03:18,812 --> 00:03:22,812
'show-neighborhood' button and then click
on a node, and the neighborhood of that
41
00:03:22,833 --> 00:03:29,053
node is shown. We can also show the link
distances, and click on a node, and that
42
00:03:29,060 --> 00:03:33,060
says from this node, here are the
distances to that node.
43
00:03:33,062 --> 00:03:35,022
So those are different things we can do.
44
00:03:35,022 --> 00:03:36,982
I click 'setup' again to clear those.
45
00:03:36,982 --> 00:03:40,002
Ok, so now, I can change beta.
46
00:03:40,002 --> 00:03:46,412
So what happens if I change beta to 0.1,
which means that one of the links will be
47
00:03:46,422 --> 00:03:50,419
rewired. I click setup again, and you see
this link was rewired.
48
00:03:50,419 --> 00:03:55,979
Here the global average distance went up,
but that's because we have so few nodes.
49
00:03:55,979 --> 00:04:02,279
Ok, so let's do this for a more realistic
number. Let's do 100 nodes, beta back to 0
50
00:04:02,279 --> 00:04:10,067
Setup. Now you see that same regular
pattern of links, will 100 nodes
51
00:04:10,089 --> 00:04:14,089
Global average distance is 25 hops.
52
00:04:14,114 --> 00:04:19,244
Now let's change beta to 0.5, 5%. Now we
do setup.
53
00:04:19,256 --> 00:04:25,456
Now remember that here, beta is the
probability that a node gets rewired.
54
00:04:25,456 --> 00:04:30,846
So each node has a 5% probability of
getting rewired
55
00:04:30,846 --> 00:04:33,516
And actually rewired a lot of them
56
00:04:33,516 --> 00:04:45,096
And we see that global average distance
went way down, from 25 to 9.24.
57
00:04:45,096 --> 00:04:49,096
So this relatively small percentage of
rewiring allowed the distance to decrease
58
00:04:49,096 --> 00:04:56,596
dramatically. It also changed the degree
distribution.
59
00:04:56,596 --> 00:05:01,826
Ok, now let me try rewiring 10% of the
links
60
00:05:01,865 --> 00:05:11,025
Well, it went up. But if we do it again,
it goes down, because it's random.
61
00:05:11,132 --> 00:05:14,202
There's a lot of randomness here. We
still have low clustering.
62
00:05:14,202 --> 00:05:17,582
Clustering shows up when we have more
neighbors
63
00:05:17,582 --> 00:05:19,622
So let's change the neighbor count to 4
64
00:05:19,640 --> 00:05:22,470
The beta back to 0
65
00:05:22,510 --> 00:05:27,300
Here, each node is connected to 2
neighbors on either side
66
00:05:27,300 --> 00:05:33,450
If I change beta here, here the
distance is 12.75.
67
00:05:33,477 --> 00:05:37,647
Let's make beta 5% again, 'setup'.
68
00:05:37,647 --> 00:05:43,587
Here, both the global average distance
decreases dramatically, and the clustering
69
00:05:43,588 --> 00:05:48,658
increases. You'll get a chance to play
with this small-world network model for
70
00:05:48,670 --> 00:05:56,310
the homework. Let's finish off this
sub-unit by a summary of what we learned
71
00:05:56,325 --> 00:06:02,355
about small-world networks. We saw that
there's a spectrum of networks from very
72
00:06:02,401 --> 00:06:09,711
regular to very random. Regular networks
have high average distance between nodes
73
00:06:09,727 --> 00:06:14,857
and high clustering. The high clustering
comes in if you have more than just the
74
00:06:14,890 --> 00:06:20,910
2 neighbors. Here we have 4 neighbors per
node. Then a random network has small
75
00:06:20,932 --> 00:06:24,782
average distance but low clustering.
Whereas the small-world networks, which
76
00:06:24,793 --> 00:06:29,593
are in some ways more like real world
networks, have small average distance and
77
00:06:29,610 --> 00:06:33,610
high clustering, similar to the real
world networks that Watts and Strogatz
78
00:06:33,000 --> 00:06:37,000
investigated