We've all heard some variation of this phrase,
it's a small world!
Often you have some unexpected
connections with someone you just meet,
or you have some friends in common,
or relative,
that just seems like an incredible coincidence!
The notion of small world networks
tries to quantify this phenomenon.
how connected are we all really.
To illustrate this, we can play a little game
that you can play yourself.
The idea is,
to take yourself -
here is me in Portland Oregon -
and to ask ; how can I reach
some, say, very well known person.
I'll pick our president, Barack Obama,
via a network of friends and relatives
or people that you know well.
So the question is;
can I find a path in my social network,
to Barack Obama,
and how long does that path have to be.
The question is how do you start,
who's the first person you go to.
Well I picked my mother, who lives in Los Angeles,
because, for one thing,
she's a lawyer
and Barack Obama is a lawyer,
so there is a connection.
Also, my mother actually is a very
sociable person,
she knows a lot of people,
which also helps.
So the idea is to pick
someone who is connected
to your target person
and who also maybe has a large circle of friends.
So I asked my mother;
"Who do you know who might know Barack Obama,
or who might know someone that knows Barack Obama?"
And she thought for a while,
and she said ;
"Oh, well maybe my friend Nancy Bekavac,
who's a former president of Scripps College,
in Claremont California,
might have a connection".
And it turns out that she went to law school,
with Hilary Clinton,
who, of course, knows Barack Obama.
So amazingly, my connection to Barack Obama
only takes,
one,
two,
three,
four hops!
I don't think there is anything particularly special about me,
I think any of you can pick a famous person
in your own country
and try and find
a relatively short path to that person.
Later, after thinking about this more,
I realized I might even have a shorter path.
I thought about my cousin,
Matt Dunne, who is a politician
in Vermont.
He used to be a member of the
Vermont state legislature,
and it turns out that he knows
senator Patrick Leahy,
who knows Barack Obama.
So there we go with,
1, 2, 3 hops!
And I was amazed.
You can try it yourself,
it is a fun game,
and you can realize that
it is a rather short
path from yourself to, probably,
many well known people.
And the reason that its short
is because of people that you know,
who might be called hubs
in the social network,
such as my cousin or my mother.
In the 1950's,
the social psychologist Stanley Milgram
from Harvard tried an experiment
to quantify this small world phenomenon.
He did the following experiment,
back then in the days before email,
he had a targeted person;
his Boston stockbroker.
So he was in Boston, at Harvard,
and he knew a stockbroker
and then he recruited a group of people
he thought would be very far away,
socially speaking,
from a Boston stockbroker,
that is Nebraskan farmers.
So he putted an ad in newspapers in Nebraska,
Trying to recruit people for this experiment.
Their goal would be to transmit a letter to
the Boston stockbroker.
They only knew his name and that he was a stoke broker,
via people they knew well,
that is, people they knew
on a first name basis.
And so they were given the letter,
and they figured out who to give it to,
that person then is tasked to give it
to someone else, and so on,
to create a chain of
friends or relatives by which
these Nebraskan farmers can
get a letter to the target person,
the Boston stockbroker,
who they don't know.
And what Milgram found was that,
on average,
there were approximately
what he calls 6 degrees of separation.
Now that is a well known phrase now,
that idea that we are all separated by 6 degrees.
Here's the idea,
from one of his articles
that he looked at the number
of completed chains,
and the number of intermediaries
needed to reach the target person
and he found that it ranged from about
2 to 10 intermediate acquaintances.
And the median was 5,
which is where he got the notion of
the sixth degrees of separation,
that it took 6 hops to get there.
So this illustrates the small world property,
the idea that a network has relatively few
long distance links,
but there are short paths
between most pairs of nodes,
usually created by hubs.
And what's interesting
is that not only social networks,
but many other kinds of networks,
in fact most real world world complex networks
seem to have this small world property.
In the 1990's,
two mathematicians,
Duncan Watts and Steven Strogatz,
wrote a paper on this phenomenon
from a mathematical point of view.
It appeared in Nature in 1998 ;
"Collective dynamics of 'small-world' networks".
Here's Watts and Strogatz.
And this paper was perhaps the trigger
that really started the whole study
of networks in an interdisciplinary way.
Here's the idea:
Watts & Strogatz looked at
3 kinds of real world networks.
A network of film actors,
where the nodes were individual actors,
and two nodes were linked if
the 2 actors appeared in the same movie.
They also looked at a very different kind of network,
the power grid in the US,
where nodes where generators, transformers, substations
and 2 nodes were linked if they had a
transmission line between them.
And finally the network that we saw a picture of,
the brain of the worm C. Elegans,
where the nodes are neurons
and 2 nodes were linked
if they are connected by a synapse
or gap junction.
So is there any reason why these
3 extremely different kinds of network
should have anything in common?
Well, what Watts and Strogatz found
was that they had this common structure
that they called the small world property.
To explain that, let's look at a naive guess
for what network structure of
real world networks might be.
One guess is that they would be
very regular.
Here you have an abstract picture
of a network with our nodes;
here the nodes are arrayed in a circle,
and each node is connected
to its 2 nearest neighbors
on either side of it.
So this node, for example,
is connected to this neighbor
and to this neighbor.
And this node is connected on this side
to this neighbor
and to this neighbor.
And exactly the same kind of connections for every node.
So this is called a regular network,
and it turns out that this network,
if you scale up to many many nodes,
has a very high average distance between nodes.
It takes a long time to get via hops
from one node to some other random node
in the network,
but it has an high average clustering;
that is,
this node for instance,
its 2 neighbors are connected to each other
and its neighbors over here
are connected also.
So this has a high clustering coefficient.
At the other extreme,
you might consider a random network,
that is, each node has the same number of connections,
but they are connected randomly instead of to neighbors.
And this kind of network have low average distance
between nodes, that is
it doesn't take very long to get, via hops,
from one node to another,
but low average clustering.
Well, what Watts and Strogatz found
for the 3 real world networks they studied,
was that neither of these naive guesses were correct.
Here is some results reported in Watts' and Strogatz's paper;
they report for each of these 3 networks they looked at
the average distance between pairs of nodes in the given network.
So here is what they found for the average distance
in these networks,
and they compared that
with a randomly connected network,
that has the same number of nodes and links.
And you can see that
the random average path length,
shortest path length,
is a little bit lower,
but not too much lower.
So each one of these has relatively
small random path length,
for the given number of nodes
or a huge number of nodes in each of these.
And then they looked at the clustering coefficient
of these networks,
and the clustering coefficient
in the real world networks,
were much much higher
than the clustering coefficient in the random network.
In summary,
if we compare are two extremes,
the regular network and the random network,
we can see that these so called small wold networks
as defined by Watts and Strogatz,
have low average path length,
and high clustering,
compared to either of the extremes.
And it seems that this middle ground
is where most real world networks lie.
That is, small world networks can be defined
as having low average distance between nodes,
but high clustering.