Collaboration Networks, networks in which nodes represent researchers and edges between two nodes indicate collaboration on a paper, give a way of modeling the flow of ideas in the academic world.  In the paper “Some Analyses of Erdos Collaboration Graph”, the authors Vladimir Batagelj and Andrej Mrvar apply techniques of analyzing large graphs to the connected component of the global Collaboration Network containing Paul Erdos, a prolific mathematician of the 20^th century.  According to the paper, Paul Erdos wrote over 1500 papers, and was a strong supporter of mathematical collaboration.

Given a vertex v of the graph, define the Erdos Number of v to be the distance from v to Paul Erdos, with Erdos himself having Erdos Number 0.  The paper analyzes the subgraph of vertices having Erdos number two or less, called the Erdos Graph, because not much is known about collaboration between mathematicians of Erdos number at least two.  It’s clear that the Erdos Graph is connected since Erdos himself is in the graph, but if we remove Erdos, the paper says that there will be seventeen connected components.  As one expects with large social networks, of these seventeen components there is one giant component of 6045 vertices while all other components contain 12 vertices at most.  This is not all that surprising since intuitively as we add edges to a large graph they will bring together connected components.

While the paper gives several methods for analyzing large graphs, I will discuss one which I found interesting.  Define the k-core of a graph to be the largest subgraph in which each of the vertices has degree at least k, and let the main core be the k-core with k maximal.  For each vertex v we can define core(v)=k where v is in a k-core but not a (k+1)-core, and we can define core(v)* to be the average of all the core values of the neighbors of v.  Note that high values of core(v)* seem to indicate that an important mathematician is collaborating with mostly other important mathematicians so the authors of the paper define the collaborativeness of a vertex v to be: coll(v) = core(v)/core(v)*.  The authors propose that this gives a good measure of how open a mathematician is to collaborating with mathematicians who are less important.  While the paper never delves into whether this is a good metric or not, there is some intuition here since for large values of core(v)* we have that v is collaborating with a group of elitists, and for large values of core(v) we have that v is collaborating with a lot of people.

As a final remark, I would like to give some possible directions for research on collaboration graphs, and that of the Erdos graph in particular.  Firstly, each edge {v,w} in the graph corresponds to some collaboration between mathematicians v and w, but it may also be worthwhile to know how many times v and w collaborated on papers.  Thus it may be of some use to model the collaboration using multigraphs where each edge represents a specific paper that the researchers collaborated on.  Furthermore, it would be interesting to see whether the collaboration graph satisfies triadic closure, or at least how often it occurs.  If Jon collaborates with Eva and Eva collaborates with Dexter is it likely that Jon and Dexter will take note of this and collaborate on a future research?

It doesn’t seem likely that much insight can be gained from the entire collaboration network as it is far too large, but if social scientists continue to analyze subgraphs such as the Erdos graph, it is entirely possible that we may learn more about the larger collaboration graph.