Creating all strongly connected graphs with given in-degree with equal probability

Question

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), 1 <= k_i <= n-1.

Input

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

Output

• 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.

Answer 1

Keep creating a random path until there is a loop:

node1->node2->node3...->nodek->noder where r<=k

Now, replace the cycle noder->noder+1->nodek with a blob and let us call it blobr. Now keep connecting it to the remaining nodes (such that nodes are not in this blob). Every time you hit a cycle, just create a bigger blob.

This will ultimately create a random minimally strong directed graph. Afterwards, add random edges to fulfill incoming criteria.

This will definitely create all the combinations of your requirements. I think all the combinations are equally likely, but I have to think more.

Algorithm: This is a rough scheme. I am actually not reconding the graph structure here and not addressing the edge conditions, but that should be pretty straighforward.

function randomStrongGraph(list<set<node>> chain, set<node> allnodes)
    Node newnode = random(allnodes - head(chain))
    alreadyEncountered = false
    for (i=0,i<chain.length-1;i++)
        if (newnode in chain(i))
            consolidate(chain, i)
            alreadyEncountered = true
            break
    if !alreadyEncountered
        chain.append(new set().add(newnode))    
    randomStrongGraph(chain, allnodes)