Small worlds

What do human networks look like?

Hard to measure for a long time

• Erdos and Reyni came up with random graphs
• Each edge has equal probability of existing
• This obviously isn’t true
• Most of us are much more likely to be connected to those near us (along multiple dimensions)

What do “groupy” networks look like?

• High clustering (triadic closure)
• Long path lengths
• High “geodesic distance” (longest path between any two nodes)

Milgram Experiment and 6 degrees

• Try to get a letter to Mr. X
• Found that (of those that made it) it took ~6 steps
• Similar results found in 2003 using email (Dodds, Muhamad, Watts)

The puzzle

• We know that we are in “groupy” networks yet all ~8 billion of us seem to be connected within a relatively short number of steps. How?

Watts and Strogatz big insight

“Groupy” graph:

Average distance: 5.25; Max distance: 10

Just a few random “rewirings” make a clustered network with low distances

10% of edges rewired:

Average distance: 3.24625; Max distance: 7

Where do these “rewirings” appear?

• Hubs
• People who move far from home
• People whose interests diverge from those around them

Lots of other networks have these same characteristics

• Oracle of Bacon
• Six Degrees of Wikipedia