[SOLVED] How do I create a random bipartite graph with fixed degree sequence?

How do I create a random bipartite graph with fixed degree sequence?

I would like generate a random bipartite graph with a fixed degree sequence in igraph or other r package. I am familiar with how to generate a random graph with a fixed degree sequence and how to generate random bipartite graph in igraph--but I cannot sort out how to generate a random bipartite graph with a fixed degree sequence (as described by Newman, Watts and Strogatz (2002)).

Solution

Use a bipartite version of the configuration model:

create vertex IDs for each of the two partitions
replicate each vertex ID as many times as its degree
shuffle the lists if IDs and match them up, creating a graph

deg1 <- c(3,2,1,1,1)
deg2 <- c(2,2,2,2)

edgelist <- cbind(sample(rep(1:length(deg1), deg1)), sample(rep(length(deg1) + 1:length(deg2), deg2)))

graph <- graph_from_edgelist(edgelist)

You can now check degree(graph).

Note that this may create multigraphs (graphs with parallel edges), and that it does not sample uniformly over the set of bipartite multigraphs. However, it can be shown that if you reject all non-simple outcomes, the sampling becomes uniform.