Wednesday, January 11, 2012

A small world in time

Do you know someone who knew someone who knew someone who knew someone who knew someone who knew someone who knew someone who knew George Washington personally?

We could imagine trying to run Milgram's experiment: give a message to someone who we think might lead to Washington; that person thinks of someone they used to know, to whom they could have given that message, and who might lead closer to Washington, etc. But it is impossible to implement: we cannot run an experiment into the past. The social networks of the past are gone. They have disappeared forever. They seem inaccessible.

Then, how could you estimate the number of degrees of separation between you and George Washington?


  1. I suggest 15-20 as a rather conservative estimate for myself (and most other people): I know a friend who knows a member of parliament. The PM knows the prime minister of Canada. The current prime minister knows Mr. Obama. Obama knows some of the former presidents of US (I am sure about him knowing Jimmy Carter). I guess every US president had met about 2-4 presidents before himself. Let's take 3. We have 44 US presidents, which makes about 15 connections. Add the aforementioned connection from me to the current president, and the result would be about 18-19.

    This is a conservative estimate as I specified a particular path throughout history. I guess a better estimate is possible, noting that one can find many two-generation paths that spans about 70 years (grandparents and their grandchildren). One can then go back through the era of Washington by 3 of these two-generation hops. Then it would be the usual spatial small world problem, which I believe leads to having about 2-3 intermediate persons to reach a very famous person of the time. So this estimate gives about 5-6 as the distance.

  2. Your first construction gives one way: first move in space until you get to a descendent (professional, academic or genetic) of the person you're trying to reach, then go straight up the genealogical tree (of US presidents, in 15 hops).

    Your second construction is similar but starts with time: first go back in time by hops of 70 years, then, once you've reached a person of Washington's time (after 3 hops), move in space until you get to him.

    Can you do better?

    Are you sure that the six degrees of separate held in society in Washington's days?

  3. Very good point: move in space while moving in time.
    My estimates were indeed crude. They suggested something like T + S number of connections with T: temporal distance, and S: spatial distance. We may model the population through time as a multi-layer graph. Temporally, it looks like a chain, so I think the temporal distance would be almost like Time difference / time resolution of jumps (and this may not be improved). But if we can move along spatially too, we may actually get rid of S (when S < T). So the expected number of hops, under the same condition, would be T.

    And no, I am not sure about the degrees of separation at his time. I am not even sure about the degree of separation at the current time. I believe Duncan Watts has recently done some empirical studies about that, but I cannot remember the details (as far as I remember, the number in his studies was actually larger than 6. Maybe the average was 10). But I do not expect that the behavior would be significantly different: If I am right, for a small-world network with n nodes, the expected hop length between two randomly chosen nodes is O(log n). The population of the world at 1800 was around a billion. So we have about a log(7) difference. Of course, this is based on the assumption that we always had a small-world network graph all the time. Doesn't sound unreasonable.

    What do you think?

  4. And what about the distance with someone in the future? :-)
    For this problem it is possible to run Milgram's experiment.
    What is the distance between you and the Nobel Prize for Medicine 2034?
    or the great grand son of the next mayor of Tokyo ?
    or someone "defined" by its Social Security Number ?

  5. We can use the Mathematics Genealogy Project. I have lineage to Gauss who in turn was a friend of Alexander von Humboldt, who in turn spent three weeks as guest of Thomas Jefferson, who in turn was Washington's Secretary of State (before becoming president). This gives at least a nice bound on the distance.

  6. On that note, it might be more direct in general to first go up your own genealogical (or mathematical-genealogical) tree and then move in space, than to first try and move to a tree which you can then traverse. I'm descended, on my mother's side, from someone who was an ensign at Valley Forge.

  7. Say that people know their parents, siblings, children, and spouse. Is that enough to define a social network with the small world phenomenon? We do have access to a lot of that data thanks to people's interest in genealogical trees.

  8. I am with Nicolas B. on that one. We may find it hard to run the experiment now, but with Facebook, LinkedIn and the rest of the social networks, in the future one can run the experiment with us as targets...

  9. Maybe doing something similar to what SoloGen suggested but in the opposite direction would be better. More precisely, how many people Washington knew? It take one step to one of them. How many grandsons did they have on average? Repeating this until you get nowadays, you get a list of people alive with "short" paths to Washington. Then just take the shortest path from you to one in this list. The good part is that you don't need the "six degree" assumption on Washington's days and since there are lots of candidates to find in the present days, you can hope to reach one with less than 6 steps.


Note: Only a member of this blog may post a comment.