There are two kinds of collaboration graphs (using data from Math Review by the courtesy of Jerry Grossman and Patrick Ion). In both graphs, vertices are authors, and edges are between coauthors. The second collaboration graph only involves papers with exactly two authors, while the first collaboration graph is based on all papers with at least two authors. In a way, the collaboration graph I is really a hypergraph rather than being a graph. In both graphs, Erdos is the vertex with the largest degree (502 in the collaboration graph I, and 229 in the collaboration graph II).

A natural phenomenom in massive graphs is the power law distribution. It says the number of vertices with degree*
i* is
roughly proportional to a negative power of* i* . We can see that the collaboration graphs
obeys the power law with the power coefficient 2.2. as seen from the two
figures on degree distribution below.

The distribution of connected components are also shown below. Both collaboration graphs have a unique giant components.

Here we show a portion of the collaboration graph II. Namely, the last two
figures are the induced subgraphs on the set of vertices associated with
all coauthors of Erdos. (Erdos himself is excluded in this graph.) The
layout is generated by an algorithm involving several variables corresponding to
"spring" and "expansion" constants.