The Collaboration Paradox

Sophie Maclean

Paul Erdős is undisputedly the most prolific mathematician to ever have lived. He published over 1500 papers while he was alive, and worked with over 500 collaborators. It is perhaps the number of collaborators which stands out even more so than the number of papers published. 

To have co-authored a paper with Erdős is a badge of pride among mathematicians. In fact, it is a famous challenge to get as few degrees of separation from co-authoring with Erdős as possible. If you have written a paper with him, it is said that you have an Erdős number of 1. We shall say that Erdős himself has an Erdős number of 0 (classic mathematician trick). Then everyone else has an Erdős number of 1 + the lowest Erdős number of any of their collaborators.

This should not put off any aspiring mathematicians, though. Paul Erdős is very much the exception – the vast majority of mathematicians do not even get within an order of magnitude when it comes to the number of collaborators. But what of the rest of us? Us mere mortals who have not ascended to his legendary status? Most people still feel like they have fewer collaborators than others.

I am here to tell you not to worry. Maths can explain this too! In fact, though it may seem paradoxical, most people have fewer collaborators than their own collaborators do on average. This is known as the “friendship” paradox and is normally framed as your friends having, on average, more friends than you. So good news, that’s not your fault either.  Once again, maths saves the day!

G is for Graph

To do anything with the question of whether or not a person’s collaborators have more collaborators than they themselves do, we need to decide how we will handle this information. For example, let’s suppose we have 5 people: Ada, Blaise, Carl, Dorothy, and Emmy (who will be referred to sometimes by just their initials). Ada has collaborated with Carl, Dorothy and Emmy; Blaise has worked with Carl and Emmy; and Dorothy and Emmy have also collaborated.

How might we represent this? A computer coder may immediately want to represent this information in an array:

But to me, it makes most sense to draw a diagram:

Long-time followers of this blog will immediately recognise this as a graph, the likes of which Ben, Katie and I have all written about in the past. In case this is new to you, this graph is different from the ones you learn about in school. In graph theory, graphs are points (known as vertices) connected by lines (known as edges). In this case, the vertices represent the people, and an edge is included if they have collaborated with one another. 

We can denote the sets of vertices and edges as \(V\) and \(E\) respectively, so here \(V = \{ Ada, Blaise, Carl, Dorothy, and Emmy\}\) and \(E = \{ \{ Ada, Carl\}, \{ Ada, Dorothy\},  \{ Blaise, Carl\},\) \( \{ Blaise, Emmy\},  \{ Dorothy, Emmy\} \}\). We use \(|V||\) and \(|E|\) to denote the number of vertices and edges respectively (here \(|V| = 5\)) and \(|E| = 6\)).

We call the set of vertices sharing an edge with the vertex \(v\), the neighbourhood of \(v\), denoted \(Γ(v)\), e.g. \(Γ(Ada) = \{Carl, Dorothy, Emmy\}\). The only other concept we will be using is the “degree” of a vertex. This is the number of neighbours a vertex, \(v\) has, and is denoted \(d(v)\). Notice also that the degree of v equals the number of points in its neighbourhood, in symbols \(d(v) = |Γ(v)|\).

Now we can rephrase our statement about collaborators into the language of graph theory: The expected degree of a vertex chosen at random is at most the expected mean degree of its neighbours. In fact, aside from one special type of graph, the expected degree of a vertex chosen at random is strictly less than the expected mean degree of its neighbours.

A Note on Language

If you are paying very close attention, you may notice that the graph theoretic statement above is subtly different to my original claim that “most people have fewer collaborators than their own collaborators do on average” in two ways.

Firstly, the original wording is very vague – I did not initially define what I meant by “on average.” Such a definition is so much easier in the language of graph theory, particularly if you want to avoid a lengthy sentence that has to be read four times to be understood.

Secondly, I generalised the statement from being about collaborators to being about graphs. Not only does this mean we can later apply this paradox to many other situations, but it also means that I have removed the ambiguity over whether there is something sociological going on. No sociology. Only mathematics.

How Do We Prove It?

Now we have all the ingredients, let’s put them together. First, we need to establish the average degree of a randomly chosen vertex. There are \(|E|\) edges in total, and each edge joins two vertices. So

\( ∑_{v ∈ V} d(v) = 2|E|\).

The expected degree of a vertex chosen uniformly at random is the sum of all the degrees divided by the number of vertices, i.e.

\(μ = \frac{2|E|}{|V|}\).

Now for the harder step – finding the average degree of the neighbours of a randomly chosen vertex. What we will end up doing is using the conditional expectation formula:

\(\mathbb{E}(A) = ∑_{all possible B}\mathbb{E}(A|B)\mathbb{P}(B)\).

We now want to know how many neighbours the neighbours of a randomly chosen vertex have, on average. To do this, we first choose an edge uniformly at random, then choose one end of it to be our vertex and the other to be our neighbour \(n\).

The probability of the neighbour \(n\) being vertex \(v\) is therefore \( \frac{d(v)}{2|E|} \) where the \(2\) comes from the fact that each edge joins two vertices.

\(v\) has \(d(v)\) neighbours of its own, so the expected number of neighbours of a neighbour, given that \(n\) is vertex \(v\) is \(d(v)\).

Therefore, the expected numbers of neighbours of a randomly chosen neighbour is

\(∑_{v} \frac{d(v)}{2|E|} d(v) = \frac{∑_v d(v)^2}{2|E|} \).

By definition, the variance \(σ^2 =  \frac{∑_v d(v)^2}{|V|} – μ^2 \).

So, the expected number of neighbours of a randomly chosen neighbour is

\(\frac{∑_v d(v)^2}{2|E|}  = \frac{|V|}{2|E|}(μ^2 + σ^2) = \frac{ μ^2 + σ^2}{μ} = μ + \frac{σ^2}μ \).

Hence this is at least the same as the degree of a randomly chosen vertex, and the two are only actually equal when the variance is zero, i.e. when all vertices have the same degree.

We Can’t All Be Erdős

So there we have it – we have mathematically proven that it is not your fault if your collaborators have more collaborators than you. Tell that to the grants committee! 

Though for about 500 of you, I’m sure none of this will come as a surprise. Of course your collaborators have, on average, more collaborators than you. You’ve collaborated with Erdős and Erdős is an outlier adn [sic] should not have been counted.

 

The post The Collaboration Paradox originally appeared on the HLFF SciLogs blog.