3
$\begingroup$

A (n, m, k)-bipartite graph is a bipartite graphs with:

  • independent sets of size $\{n, m\}$
  • a total of $k \geq n+m-1$ edges

We want an algorithm to generate a (n, m, k)-bipartite selected uniformly at random in the set of all (n, m, k)-bipartite graphs. Ideally the algorithm should be in O(k) but any suggestion is welcome (other than picking a random bipartite with {n,m} nodes and k edges graph until its connected).

For now the only algorithm I have in mind doesn't achieve uniform sampling:

The idea is to first create a connected bipartite graph with the minimum number of edges by iteratively picking isolated nodes and connected them to the other independent set of the bipartite graph. For that we will create two sets N and M and create a first random edge connecting N to M. Then we will pick a random isolated node (from either N or M) and connected it to a random non-isolated node from the other set. Once we don't have any more isolated node we will have exactly n+m-1 edges, we will thus need to add k-(n+m-1) additional edges to the graph to match the original constraints. To add these last edges we simply pick random pairs of nodes from NxM.

Here is the (python) code corresponding to that algorithm

import networkx as nx
import random

random.seed(0)

def biased_random_connected_bipartite(n, m, k):
  G = nx.Graph()

  # These will be the two components of the bipartite graph
  N = set(range(n)) 
  M = set(range(n, n+m))
  G.add_nodes_from(N)
  G.add_nodes_from(M)

  # Create a first random edge 
  u0 = random.choice(tuple(N))
  v0 = random.choice(tuple(M))
  G.add_edge(u0, v0)

  isolated_N = set(N-{u0})
  isolated_M = set(M-{v0})
  while isolated_N and isolated_M:
    # Pick any isolated node:
    isolated_nodes = isolated_N|isolated_M
    u = random.choice(tuple(isolated_nodes))

    # And connected it to the existing connected graph:
    if u in isolated_N:
      v = random.choice(tuple(M-isolated_M))
      G.add_edge(u, v)
      isolated_N.remove(u)
    else:
      v = random.choice(tuple(N-isolated_N))
      G.add_edge(u, v)
      isolated_M.remove(u)

  # Add missing edges
  for i in range(k-len(G.edges())):
    u = random.choice(tuple(N))
    v = random.choice(tuple(M))
    G.add_edge(u, v)

  return G

B = biased_random_connected_bipartite(5, 6, 11)

The bias comes from the correlation between the node degrees and the time at which they have been added to the connected component. For example both nodes u0 and v0 will tend to have higher degree as they will be potential candidates for the $n+m-2$ remaining edges we will add to make the graph connected. The last node added in this same process will always have degree 1 before we start adding the $k-(n+m-1)$ additional edges.

Is there a know result for that? Or any existing result that may help?

edit I found a slightly better solution (smaller bias):

  1. Generate a random (n, m, k)-bipartite graph (picking k random pairs)
  2. While the graph is not connected:
    • pick a random edge (u, v) outside the largest connected component
    • connect u and v to the main connected component

This is a simpler algorithm, and my gut feeling is that it's better than the other as we only have a bias on the redirected edges (which is at most n+m-2). Which means that in the worst case the bias is still slightly less important than in the first solution.

$\endgroup$
  • $\begingroup$ In your second solution, you say you add $k$ edges on $k$ random pairs, and then add more until you get connectivity. But then this isn't a $(n,m,k)$ graph as you defined it (a total of $k$ edges). Is $k$ supposed to a fixed parameter or is it supposed to be a lower bound on the number of edges? $\endgroup$ – JimN Feb 27 at 3:17
  • $\begingroup$ Ah you're right, I didn't even noticed I was splitting existing edges in two different edges. Then I think the second version doesn't work at all ($k$ isn't a lower bound) $\endgroup$ – cglacet Feb 27 at 9:23

Your Answer

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

Browse other questions tagged or ask your own question.