12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Welcome! How is the "degree distribution" given? As stochastic distribution, as list of degrees, ...? $\endgroup$ – Raphael May 17 '12 at 13:00
  • 1
    $\begingroup$ See Exercise 2.6 here. An algorithm for creating a graph from a given degree-sequence is given. $\endgroup$ – utdiscant May 17 '12 at 13:41
  • 2
    $\begingroup$ To clarify Raphael's comment, when I read degree distribution, I think of a probabilistic distribution on degrees. As utdiscant mentions, degree sequence is probably what you want. If you mean the probabilistic sense, you're probably looking for some randomized construction algorithm that tries to "approximate" the distribution. It doesn't make a lot of sense to me to "report a no" in this setting, though, because I think most graphs will be some sort of outlier? $\endgroup$ – Lucas Cook May 17 '12 at 15:03
  • $\begingroup$ And if you actually want to generate a graph with a given degree distribution, then this paper seems to have the trick. It seems the algorithm described in my previous comment, is actually the Havel-Hakimi algorithm in the answer by Wu Yin. $\endgroup$ – utdiscant May 17 '12 at 15:52
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ thanks. yes wiki page is helpful in this case.. $\endgroup$ – singhsumit May 18 '12 at 5:26
11
$\begingroup$

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})$.

$\endgroup$
  • $\begingroup$ From your (quite clear) explanation it is not at all clear why matrix multiplication enters the equation. $\endgroup$ – Raphael May 17 '12 at 16:24
  • 2
    $\begingroup$ @Raphael matrix multiplication is one of the ways to solve maximum matching and it is the preferred method for dense graphs, since the best version of Edmonds's matching algorithm runs in $O(\sqrt{|V|}|E|)$ which would give $O(N^{2.5})$ for this problem, since $H$ is pretty dense. So if you have access to a good fast matrix multiplication (or working with a matrix-oriented language like Matlab) I would use Mucha and Sankowski's matrix approach to matching. $\endgroup$ – Artem Kaznatcheev May 17 '12 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.