UK Guardian newspaper publishes USA NSA papers

[Robert J. Hansen]

> That's phenomenal: isn't everybody in the world separated by an
> average of just six hops?

That's more urban myth than reality.  Reality is hard to model.  An  
isolated village in a remote area of Africa might have a very hard  
time connecting to London in six hops, but the instant one villager  
gets a cell phone suddenly they're on the phone jawing with 10 Downing  
Street.  It's hard to give simple "six hops is about it, yes" answers:  
what we have to talk about instead is the degree of connectivity  
within a network.  Given a network with a certain set of nodes and a  
certain set of connections between nodes, how many hops will it take  
to traverse the network?  This is a function of both how many nodes  
there are, and the particular connections they have.

When the network forms a bunch of neighborhoods and there are few if  
any long-distance connections, the hop count quickly goes out of  
control.  As a historical example, look at the Black Death.  Despite  
the worldwide conditions being virtually ideal for the various forms  
of plague (principally bubonic), it still took many years for the  
Black Death to spread from China to Europe.  At that time in history  
the overwhelming majority of people not only had never traveled more  
than 30km from their homes, they didn't even know someone who had  
traveled more than 30km from their homes.  The Black Death was  
condemned to spread 30km at a time -- ravaging a 'neighborhood' of the  
network and then moving on.

Today, though, many of us have traveled internationally and virtually  
all of us are connected to someone who has traveled  
intercontinentally.  (Including all of you.  I've traveled to Europe  
multiple times and you know me, so even if you've never left your  
small rural village you're still connected to someone who has traveled  
a long distance.)  It turns out that if you have even a small number  
of long-distance connections, neighborhoods get bridged *very* quickly.

Let's connect me to Vladimir Putin as an example.  I'm looking for a  
good long-distance hop that will get me most of the way to Russia.  I  
attended undergrad with a Russian woman named Yelena (last name  
omitted for her privacy), whose great-uncle sat on Gorbachev's  
Politburo (his name omitted again for her privacy).  He, in turn, is  
*scary*-well connected among the political elite.  If he doesn't have  
a certain former KGB counterintelligence agent on speed-dial, I'll eat  
my hat.  So:

     Rob --> Yelena --> Y's Great-Uncle --> Vladimir Putin

Three hops.  It's worth asking: if I didn't have that long-distance  
hop, could I still make it to Putin?

Sure.  I just need a different hop.  It turns out my co-worker Greg,  
who was born and raised in Moscow, knew Yelena's great-uncle (and  
hated him something fierce, but that's beside the point).  So now it's:

     Rob --> Greg --> Y's Great-Uncle --> Vladimir Putin

Okay, so the real 'focus' node is Yelena's great-uncle.  Let's get rid  
of that.  And let's do something weird, like require that the  
connection be made through official government contacts and  
coordinated through the Department of State.  Well, my father is a  
federal judge who has professional and personal connections with  
Senator Tom Harkin (D-IA).  Senator Harkin happens to be a close  
friend of John Kerry, the United States Secretary of State.  Secretary  
Kerry in turn has Vladimir Putin on speed-dial.  So there's...

     Rob --> Rob's dad --> Harkin --> Kerry --> Putin

It's not hard to come up with ways I'm connected to Vladimir Putin.   
Try to connect yourself to Putin: seriously, it's a fun game.  :)

Hop counts will be lowest where each node in the network is connected  
to a modestly-large neighborhood, and where each of those neighbors  
has a good chance of having one or more long-distance connections.  It  
used to be that a neighborhood consisted of no more than a couple of  
hundred people, none of whom had long-distance connections of their  
own.  This would be the case for a medieval village, for instance.   
Nowadays we may have *thousands* of connections, and each connection  
has an extremely good chance of having one or more long-distance  
connections.

The combination of large neighborhoods and long-distance connections  
is called the "Small World Effect," and it has a lot of academic  
literature backing it.  You may want to check out the Wikipedia page  
for more information:

http://en.wikipedia.org/wiki/Small-world_network