3
$\begingroup$

I am looking for a way to sample uniformly from the space of all strongly connected directed graphs (without self-loops) of $n$ nodes and in-degree $k=(k_1,...,k_n)$ with $1 \leq k_i \leq n-1$.

In other words, I am looking for an algorithm with input

  • $n$, the number of nodes
  • $k=(k_1,...,k_n)$, where $k_i =$ number of directed edges that enter node $i$ (in-degree)

that outputs

  • a strongly connected directed graph of $n$ nodes (without self-loops) with the given in-degrees $k_1,...,k_n$ where each possible such graph is returned with the same probability.

I am particularly interested in cases where $n$ is large and $k_i$ is small so that simply creating a graph and checking for strong connectedness is unfeasible because the probability is essentially zero.

I looked through all sorts of papers and methods but couldn't find anything that deals with this problem.

$\endgroup$
1
+50
$\begingroup$

One approach is to use a Markov Chain Monte Carlo (MCMC) method. The algorithm in its basic form would go like this:

  1. Begin by selecting an arbitrary strongly connected graph $X$ with the specified parameters (For instance, just start with an $n$-cycle and then add edges arbitrarily to bring each node $i$ up to in-degree $k_i$.)

  2. Given the selected graph $X$, select a vertex uniformly at random, and replace one of its incoming edges with a new incoming edge from a uniformly randomly chosen vertex. If the resulting graph $X'$ is strongly connected, then set $X'$ to be the new selected graph $X$ (Otherwise, do not change $X$).

  3. Repeat step 2 a fixed large number of times $M$. Then output the selected graph $X$.

The idea is that the collection of strongly connected graphs itself forms a graph (call it a "metagraph"), where we define two graphs $X$ and $X'$ to be adjacent if it is possible to go from $X$ to $X'$ in one step as described above. What we are doing is taking a random walk on the metagraph. This method will work, in the sense that $X$ converges to the uniform distribution on the metagraph (as $M\to\infty$), if and only if the metagraph is connected and not bipartite. The non-bipartite assumption is not much of a concern, because it is always satisfied except in the fairly trivial case $k=(2,2,1)$. (Proof: if there exists at least one graph with the specified in-degrees which is not strongly connected, then there will be a pair of graphs $X$ and $X'$ which are one "step" apart, but for which $X$ is strongly connected but $X'$ is not, and in this case the metagraph will have a loop at $X$ (i.e., a cycle of length 1) since if we "tried" to transition from $X$ to $X'$ we would fail and just stay at $X$, and this means the metagraph is not bipartite; in the other case, if $n\geq 4$ the metagraph will contain a triangle, except in the trivial case where all $k_i=n-1$. The cases $n\leq 3$ can be checked by hand.)

As far as whether the metagraph is connected, I've written a program which verified that for $n \leq 6$, for all possible choices of $k$, except for the uninteresting case $k=(1,1,\dots,1)$, it is connected. It might take some work to prove that it is always connected for all $n$.

The other issue is how large must $M$ be in order to achieve convergence. Basic theory of Markov chains implies that any deviations from the uniform distribution decay at an exponential rate, where this rate is essentially determined by second largest eigenvalue of the transition matrix. There are general results for bounding this eigenvalue based on the geometry of the (meta)graph, but some theoretical work would be required in order to apply them to the specific problem at hand.

There are some optimizations which could be made to the basic algorithm. For example, it is not necessary to do a full check of strong connectivity at every iteration: if $(a,b)$ is the removed edge, then it is only necessary to check that there remains a directed path from $a$ to $b$. Another idea is to maintain a spanning in-tree and a spanning out-tree for a designated vertex: if the removed edge is not contained in these two trees, then strong connectivity is guaranteed to be maintained so there is no need to check anything at all; if the removed edge is in one (or both) of these trees, then the result will be a disjoint union of two directed trees, and they just need to be patched back together by finding a single edge (going the right direction) connecting any vertex of the main component to the root of the other component.

$\endgroup$

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.