Random bipartite graphs?

Question

RandomGraph[{n,m}] generates a random graph with $n$ vertices and $m$ edges. I want to generate a random bipartite graph, like RandomBipartiteGraph[m,n,e], where I can specify the number of vertices in each partition $m,n$, and the number of edges $e$. How can I do this?

Answer 1

A possible solution:

RandomBipartiteGraph[m_, n_, e_] := 
 Graph[Range[m + n], 
  RandomSample[Flatten@Table[i <-> j, {i, m}, {j, m + 1, m + n}], e]]

But I wonder if I can do it with some of Mathematica built-in graph generator functions?

Also, this is very slow if $m$ or $n$ are large. I am generating the list of all posible edges, which is a big waste if in the end the actual number of edges is small.

Answer 2

Here is my fast entry:

randomBipartiteGraph[m_, n_, e_] :=
 Module[{edges, mat},
  edges = ConstantArray[1, e] ~Join~ ConstantArray[0, m*n - e];
  mat = Partition[RandomSample[edges], m];
  AdjacencyGraph@ArrayFlatten[
    {{0, Transpose[mat]},
     {mat, 0}}
    ]
  ]

Graph[randomBipartiteGraph[10, 20, 80], GraphLayout -> "BipartiteEmbedding"]

Here is my simple entry:

randomBipartiteGraph[m_, n_, e_] := 
 Graph[Range[m + n], RandomSample[EdgeList@CompleteGraph[{m, n}], e]]

Answer 3

IGraph/M has two functions for this since version 0.2.0.

?IGBipartiteGameGNM

IGBipartiteGameGNM[n1, n2, m] generates a bipartite random graph with n1 and n2 vertices in the two partitions and m edges.

Use this when you know how many edges you want exactly.

?IGBipartiteGameGNP

IGBipartiteGameGNP[n1, n2, p] generates a bipartite Bernoulli random graph with n1 and n2 vertices in the two partitions and connection probability p.

Use this when you don't want to fix the number of edges, but instead each edge is present independently with probability $p$.

These functions have two special options:

• DirectedEdges controls whether they should produce a directed graph

• "Bidirectional" controls whether edges should run in both directions between the partitions, or only in one direction, when generating directed graphs.

---

Example:

g = IGBipartiteGameGNM[5, 6, 14, VertexLabels -> "Name"]

IGBipartiteQ[g]
(* True *)

IGBipartitePartitions[g]
(* {{1, 2, 3, 4, 5}, {6, 7, 8, 9, 10, 11}} *)

---

Be aware that Mathematica's BipartiteGraphQ has a bug where it sometimes incorrectly (and apparently randomly!!) reports False for directed graphs. This means that GraphLayout -> "BipariteEmbedding" will also fail to properly visualize these graphs. So if you get a graph from these functions that doesn't visualize, it is due to this Mathematica bug, not a problem with the package. The graph is still usable as usual. An example of such an incorrectly handled graph is AdjacencyGraph[{{0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 1}, {0, 1, 1, 0, 0, 0}, {1, 0, 1, 0, 0, 0}, {0, 1, 0, 0, 0, 0}}].

Workarounds: use IGBipartiteQ for testing bipartiteness and use IGLayoutBipartite for visualization.