Reconstructing Graphs from Degree Distribution

Question

Given a degree distribution, how fast can we construct a graph that follows the given degree distribution? A link or algorithm sketch would be good. The algorithm should report a "no" incase no graph can be constructed and any one example if multiple graphs can be constructed.

Answer 1

If you mean how to construct such a simple graph (no self loops and no parallel edges), maybe Havel-Hakimi theorem is what you are looking for. You can google it yourself, and the wikipedia page Degree (graph theory) is also helpful.

Answer 2

If the degree distribution is given as a list of degree, then you can do the following, given $n$ nodes with degrees $d_1, ... ,d_n$:

Create a complete graph $K_n$ on $n$-vertices. For each vertex $v_i$ in $K_n$, split it into $d_i$ copies. Split here means, create a number of copies with edges to every vertex $v_i$ has an edge to, but no edges to other copies of $v_i$. If $d_i = 0$ then simply remove the vertex. In the new graph, call these vertices $v_{ij}$ for $1 \leq j \leq d_i$.

Once you are done, you have a very dense graph on $N = d_1 + ... + d_n$ vertices; call this graph $H$. Pick your favorite algorithm for maximum matching (since the graph is so dense, you should probably use one of the fast matrix-multiplication based algorithms) and run it on $H$. This will return a matching $M$. If the matching is not perfect (i.e. if it does not cover every vertexes) then your degree distribution was impossible; so return no.

If you have a perfect matching $M$, then remove all edges not in $M$ from $H$, and then for every $1 \leq i \leq n$ merge the $d_i$ many vertices $v_{i1}, ... , v_{id_i}$ into one vertex $u_i$. Merging two vertices means combining them into one, such that the resulting vertex has edges to every vertex at least one of the original had an edge to. Call the resulting graph $G$; it has the desired degree distribution.

The resulting runtime is $O(N^\omega)$ where $\omega$ is the constant for the fastest matrix-multiplication algorithm (which at the time of writing is about $2.373$). In terms of number of vertices in the resulting graph, in the worst case of degree distribution being dense, we have $O(n^{2\omega})$.