- 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)

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

- 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)

- 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?

“Groupy” graph:

Average distance: 5.25; Max distance: 10

10% of edges rewired:

Average distance: 3.24625; Max distance: 7

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

- Oracle of Bacon
- Six Degrees of Wikipedia