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.0425; Max distance: 6

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