Math Mutation: 232: Overcooked Bacon

Audio Link

You’ve almost certainly heard of the “Six Degrees of Separation” phenomenon, sometimes known whimsically as the “Six Degrees of Kevin Bacon”, where it supposedly takes only an average of 6 connections to reach any person on the planet from any other. In the case of the common Kevin Bacon parlor game, you name any actor, and he’s acted in a movie with someone who acted with someone (dot dot dot), and after naming less than six movies, you can always reach Kevin Bacon. For example, let’s start with Kristen Bell, one of our greatest living actresses due to her role as the Hexagon in Flatland The Movie. For her, we just need two steps: she was in Big Miracle with Maury Ginsberg, and Ginsberg was in My One and Only with Kevin Bacon. In earlier podcasts, I’ve mentioned that mathematicians often think of this in the slightly geekier terms of paper authorship and Paul Erdos. Although this concept is well known, its truth is not actually as well-established as you might think. I’m not referring to the well-documented fact that numerous actors are better-connected than Kevin Bacon— perhaps his lack of math podcasting has damaged his career in recent years— but to the general idea of connecting any two people in six steps.

Wikipedia mentions several early precedents for the Six Degrees concept, starting with Hungarian author Frigyes Karinthy in the 1920s. However, it really got its kickstart in recent times from a Psychology Today article in 1967, where Stanley Milgram described an experimental test of the theory. He gave volunteers assignments to send a letter to random people around the U.S., with the rule that they could only send it to people they knew on a first-name basis, who then had to forward it on under similar restrictions. He found that on average, it took only six steps of forwarding for the letters to reach their targets. As you would expect, news about the surprising result spread rapidly. However, many years later, a writer named Judith Kleinfeld looked up Milgram’s original raw data, and was surprised at what she saw. In the Psychology Today article, Milgram failed to report that less than 30 percent of the letters ever made it to their destination— the six degrees were only measured in the small minority that succeeded, making the overall result much less impressive. Sure, perhaps there were legitimate reasons for some failures— people in the middle of the chain may have been suspicious of being asked to forward a random item to a stranger— but it still makes the reported result very questionable.

To think about why the Six Degrees idea might be true or false, it’s useful to abstract the question into a problem in graph theory. This means we should think of people as dots, or vertices, on a large piece of paper, with connections between them symbolized by edges between any pair of vertices. If we’re representing people on Earth, there are around six billion vertices. We’re asking the question: to get from any vertex A to any other vertex B, how many edges do we need to traverse? If we assume each person has about 1000 acquaintances, then in one step we can reach 1000 vertices, in two steps 1000x1000 or one million, and in three steps one billion. So we would expect to reach anyone on the planet in an average of fewer than four connections, making the Six Degrees idea actually seem a bit pessimistic.

But something seems too easy about this random graph model. Are any two random vertices really equally likely to be connected? Am I just as likely to know an arbitrary computer geek from Oregon as an arbitrary goat farmer from Cambodia? It seems that we should somehow be able to account for being more likely to know people in a similar location, job, social class, etc. A nice article on the “Mathematics Illuminated” website discusses some alternative models. As an opposite extreme to the random graph, suppose we arrange the vertices in a large circle, where every vertex is connected to only its thousand nearest neighbors. Now to get from one vertex to the one on the opposite side of the circle, who is about 3 billion vertices away, we need 3 billion over 5 hundred, or six million connections. Definitely more pessimistic than our original model.

But this is an extremely negative model: while we all know many more people among our neighbors, most of us certainly do know some people who are well-connected in far-off locations. If we just allow a few of these long distance connections, we significantly reduce the number of hops needed. For example, suppose we designate 1000 equally spaced “world traveler” vertices, representing people who are well-connected in global organizations, that are all connected to each other. Then, to get anywhere, we just have to traverse the average of 3 million people to get to the nearest long-distance edge, cross it, and visit the same number of people on the other side— reducing the average traversal from 6 million connections to about 12000.

This leads to what mathematicians call a “small world” graph, where most vertices are connected to a large number of neighbors, but a few “hub” vertices have a lot of distant connections. You can think of this like an airline routing map: to get to a distant city, you first fly to a nearby hub, then make a long-distance flight from there to another hub, and finally from that hub you can reach your destination. It’s probably easy for you to think of some “hub” people in your life. In my case, while most people I talk to daily are from Oregon, my old friend Ruthe graduated from Oxford and worked until last year in the Obama white house— so thru her, I probably have a very short path to numerous prominent politicians, for better or worse. As we have seen, these hub connections drastically reduce the hops needed to connect any two vertices. The addition of 1000 world travelers to the circular graph actually strikes me as a major underestimate of likely real-life long-distance connections, making the original idea of Six Degrees of Separation start to seem quite reasonable.

We should add, of course, that Milgram’s flawed experiments were not the final word on the topic. There have been many similar efforts over the years, and this experiment has gotten easier as the world has become more interconnected in trackable ways, through the growth of the Internet. Microsoft did an experiment in 2006 analyzing users of their Messenger network, and found an average of 6.6 hops to connect any two people, with a worst case number of 29. So Milgram may have been right after all, despite the problems with his trials. On the other hand, the number might be noticeably higher for the non-electronically-gifted portion of the world population— would that hypothetical Cambodian goat farmer be on the internet, or know someone who is? Hopefully soon the internet will be bringing this podcast (as well as personal connections) to every human being on the planet, but we’re not quite there yet.

And this has been your math mutation for today.

References:

Math Mutation

Sunday, July 30, 2017

232: Overcooked Bacon

No comments:

Post a Comment