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.