1
$\begingroup$

I want an algorithm that takes the following

Input: $M,N,k,d$ positive integers such that $kM = dN$.

and produces the following

Output: Random bipartite graph, with $M$ vertices all of degree $k$ on one partition, and $N$ vertices all of degree $d$ on the other partition. No loops allowed. The output should be uniformly distributed among all possible graphs.

Does an algorithm like this exist? If so please provide a reference.

$\endgroup$
6
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael Jun 1 '16 at 15:17
  • $\begingroup$ @Raphael This is not homework (if it is, can you point out a course or textbook?). I need to generate this ensemble of random bipartite graphs to test the statistical properties of a different algorithm. I tried placing links at random, checking that no self-loops or parallel edges were created and checking the degrees, but this leads to contradictions and the generator gets stuck frequently. $\endgroup$ – becko Jun 1 '16 at 15:28
  • 1
    $\begingroup$ Googling for random graph generation leads to many, many resources. Which have you tried, and why have you dismissed them? $\endgroup$ – Raphael Jun 1 '16 at 18:25
  • $\begingroup$ @Raphael Did you find anything for random bipartite bi-regular graphs?? $\endgroup$ – becko Jun 1 '16 at 18:45
  • $\begingroup$ I don't know. I suspect what Raphael is implying is: We want you to search before asking here, and tell us in the question what research you've done. What have you looked at? Have you done a literature search to look through the literature on generating random graphs, to see if any of it covers bipartite regular graphs? Have you looked at known techniques for generating regular graphs, to see if any of them can be adapted to this situation? Have you search Google Scholar to look for algorithms for generating a random biregular graph? $\endgroup$ – D.W. Jun 2 '16 at 6:53
1
$\begingroup$

The problem of generating random $d$-regular graphs uniformly at random has been extensively studied. Some of the proposed algorithms are quite sophisticated. In general, the problem becomes more difficult as $d$ grows as a function of $n$. To the best of my knowledge, the problem is still open for $d = \omega\left(\sqrt{n}\right)$.

However, if one assumes that $d$ is a constant, then there is a simple and efficient algorithm called the configuration model:

https://en.wikipedia.org/wiki/Configuration_model

It can be easily adapted to the case of biregular graphs with $M$ vertices of degree $k$ on the left side, and $N$ vertices of degree $d$ on the right side. Of course, for this to be possible at all we need $Mk=Nd$.

The algorithm is as follows:

  • Assign each vertex on the left side $k$ ``half-edges", and each vertex on the right $d$ half-edges.

  • Choose a uniformly random perfect matching of size $Mk$ matching all of the half-edges on the left side to the half-edges on the right side.

  • This tells you which vertices to connect to which, but there may be double edges. Repeat the above procedure until there are no double edges.

It is pretty easy to see that the resulting distribution is uniform by counting the number of perfect matching that can yield a given graph. It is harder to analyze the probability that there are no double edges, which is critical if we want to bound the expected runtime. However, it turns out that for constant $k$ and $d$, the probability that there are no double edges is a constant independent of $n$, and so we only need to repeat the algorithm $O(1)$ times.

$\endgroup$
0
$\begingroup$

Because it seems nobody will answer this question any time soon, I will give you what I tried for the same problem. I guess my answer lacks a formal proof but it successfully solved my case. The following python style pseudocode generate edges which contains tuples of vertices.

# Assuming there are M a_nodes and N b_nodes
cur_b_nodes = set(range(N))  # b nodes with the lowest degrees
next_b_nodes = set()  # b nodes with the second lowset degrees

edges = []
for a_node in range(M):
    for _ in range(k):
        if not cur_b_nodes:
            cur_b_nodes = next_b_nodes
            next_b_nodes = set()
        b_node = sample(cur_out_nodes, 1)[0]  # Random sampling
        cur_b_nodes.remove(out_node)
        next_b_nodes.add(out_node)

        edges.append((a_node, b_node))

I think this is an approach with the lowest time complexity. Any comments will be welcome.

$\endgroup$
3
  • 1
    $\begingroup$ We're not a coding site, and we're not looking for answers that consist solely of a bunch of code. Instead, we'd prefer answers that explain the approach or ideas, and possibly give concise pseudocode and potentially a proof of correctness. That said, I don't see how this answers the question. I don't see any randomness in your code: it seems it always returns the same result, so I don't think it meets the requirements in the question. $\endgroup$ – D.W. Feb 24 '20 at 9:17
  • $\begingroup$ @D.W. Well, I see your point. But please note that I intended it to be as a makeshift answer until somebody else comes and improve it or rather gives a more proper answer for the question. And about the pseudocode, I hardly believe any procedural algorithm can be more terse than this. The randomness you are asking comes from sample function. $\endgroup$ – bombs Feb 24 '20 at 9:51
  • $\begingroup$ Thanks for clarifying where the randomness comes from. I don't find it very clear. I don't know what the semantics of sample are, for instance. I don't know what out_node is, or where it gets set or defined. One would have to know Python to know what not cur_b_nodes does (for instance), and not everywhere here understands Python, so we prefer language-independent pseudocode. We'd like to see you explain the ideas. Do you have any proof or justification for why this gives a uniform distribution over all such graphs? $\endgroup$ – D.W. Feb 24 '20 at 17:01

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.