Six Degrees of Separation

This is building off of the post where I talked about how any two majorities in a set must overlap by at least one element. This is because if you break up a group into a majority and minority and try to make a majority with the minority group, you won’t be able to. You’ll have to take at least one element from the majority group. We’re going to use this fact to talk about how people are connected in social networks. In particular, I want to talk about what kinds of assumptions we need to make in order to find the farthest distance between two people. Distance between people is measured by the number of people you have to go through to be connected to them.

Example: If I know my brother, and he knows his boss, then I’m 1 degree separated from his boss.

Let’s start by laying out the main assumption that we’re making in this problem. We’re going to assume that each person knows the same number of people (which is obviously untrue, but is a reasonable assumption to make). We’ll call this number . We’ll represent friendships with a graph, where two people are nodes, and a friendship between them is represented by an edge. Since everyone has the same number of friends, every node should have the same number of edges coming out of it. Here’s a sample of what a graph like this would look like.

Note that each node has three total edges coming out of it (except for the bottom layer). Our goal is figure out a general formula for the total number of nodes in this graph, which represents the total number of people accounted for by this graph.

The first layer adds the number of friends that each person has, which is , or 3 in this case. In the next layer, we add 6 people, which is . After a little bit of playing around with sums, you can find that the total of number of nodes in this graph is equal to , where is the number of layers of the graph – 1.

So now, we can imagine somebody else building a network like this one with their friends. We want to figure out when each network will have enough people in it (more than half of the total population) so that we can guarantee that they overlap by at least one person.

In particular, we’d like to find the smallest value of such that , where is the total population size.

Here’s an example. Consider a group of 2000 people, where you assume everyone knows 10 people. We want to find the smallest value of such that . Plugging in these particular values, we want to find the smallest such that , or . The smallest such for which this is true is . That means that once we get to the fourth layer of this graph (number of layers ), the total number of nodes accounts for more than half of the population.

Now we can imagine this same process happening for anyone else in the population who’s not accounted for in this graph, and it would also take 4 layers to reach more than half of the population.

Since any two majorities in a set overlap by at least one element, the fourth layer of both sets must share at least one element (person)! That means that we can use that common person to connect both of these graphs. So the maximum distance between the two roots of each graph is (depth of each graph), or 7 in this case!

The reason that is so cool is because by just making a few assumptions about how many people are in a population and how many people each person knows, you can figure out the most number of people you’d have to go through in order to connect any two people. What’s amazing about this is that the assumptions you make are pretty reasonable, but the conclusion that you can draw is pretty powerful!

You can do the same thing, but instead think about the population of the whole world and then make assumptions about how many people most people know (this might be how people came up with the 6 degrees of separation idea)!