Sunday, November 1, 2015

Friends and Strangers

joão pestana

Many things can be mathematically proven even if, at first, it seems rather unlikely. How people connect with each other might fall into that category. It could be pretentious to suggest that something as stochastic — fancy word to say unpredictable — as human behaviour can be mathematically modelled. Though I'm a believer of such possibility, I'll try to remain neutral here and state only what is currently accepted.

Think about how people connect. You have some easily countable number of friends and the remaining people are the non-friends — also known as strangers. It's easy to describe the relation between you and any given person at any given moment as either a friend or a stranger. That is, at any given moment, you have a fixed network that connects you to the rest of the people in the world. Of course, this may change over time.

Now I know this might seem confusing and complex, but I assure you it's as simple as watching people pass by and simply categorize them as "I know that person, it's a friend" or "I don't know that person, it's a stranger." To illustrate my point, I present the image in Figure 1.

Figure 1 — Diagram of someone's friendship network depicting 3 friends and 3 strangers.

In the diagram, imagine you are the one portrayed in a black contour, those in blue are your friends and the ones in red are strangers. If the world had only this set of 7 people, it would perfectly describe your instant social network. Not portrayed are the networks of each of the remaining 6 people. You can imagine a similar picture for each individual. It may happen that someone is friends with everybody or friends with nobody.

This is when mathematics enters the picture. The study of networks is a branch of graph theory, but it is also a pilar stone in sociology. Paul Erdős, Alfréd Rényi, and Vera T. Sós published what is called the friendship theorem in 1966. Though it relates directly with graph theory, it can be described in terms of friends and strangers — hence the name.

It goes something like this. Imagine you're at a party and there is an unknown number of people attending. If you choose any pair of people at that party and it always happens that they share one and only one common friend, then there must be one person at the party which is friends with everybody. I would suppose this person to be the host of the party — also called the politician.

Figure 2 — Representation of the friendship theorem with 9 people.

Look at the Figure 2 and you can easily see that each individual shares exactly one common friend with a different individual. You, the host, lie at the center and are friends with everybody while still fulfilling the common friend property.

There is another theorem in mathematics and it can be applied to the same line of thought we've been through. It's called the theorem on friends and strangers — a simple case of a more general theorem published by Frank P. Ramsey in 1930.

Let's revisit the party scenario, but allow for only 6 people to attend. If we consider any 2 of them at random, they might be meeting for the first time — mutual strangers — or they might already have met before — mutual friends. What the theorem states is that there is always a group of at least 3 people at a party of 6 which are either all mutual strangers or all mutual friends among themselves.

Figure 3 — Possible connections between 6 people.

If you see the Figure 3, we've a diagram that displays the total `C(6,2)=15` possible different connections among them. I didn't specify whether they're friends or strangers and that's why the lines are coloured black. If you try to create any friend or stranger connections among them, for example, by colouring them green and red respectively, you'll find that it's impossible not to create triangles. These triangles — either green or red — are the groups of 3 mutual strangers or friends the theorem mentions.

We were able to calculate the total amount of connections among 6 people. Can we do it for the entire world population? Yes! We need just to use the `n` combinations of 2 where `n` is the total world population. Thus, `C(n,2)=1/2(n-1)n` is a positively growing second degree polynomial function of `n`.

I should emphasize that this number means the total connections you have with all the people in the world either as friends or strangers. The number of possible ways you can colour each connection is much greater!

Stanley Milgram conducted several experiments to determine the average path length for social networks. That is, the average number of people needed to go through to reach any given person within the social network. Imagine you want to meet someone who's friends with your best friend. The path length between you and that person is 2. You need to go to your best friend and only then can you reach the other person you want to meet. The result from what is known as the small-world experiment was that the average path length was about 6.

This result would become associated with the six degrees of separation theory, a concept originated by Frigyes Karinthy in 1929. It states that you can reach any person within a network with 6 or fewer friend of a friend chains.

Interestingly enough, a mathematitian called Manfred Kochen published a paper in 1979 entitled contacts and influences in which he stated the following:
We noted above that in an unstructured population with `n = 1000` it is practically certain that any two individuals can contact one another by means of at least two intermediaries. In a structured population it is less likely, but still seems probable. And perhaps for the whole world’s population probably only one more bridging individual should be needed.