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)).
2 Answers
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.
We can use sample_degseq by defining out.degree and in.degree (borrowing data from the answer by @Szabolcs)
sample_degseq(c(deg1, 0 * deg2), c(0 * deg1, deg2)) %>%
set_vertex_attr(name = "type", value = degree(., mode = "out") > 0) %>%
plot(layout = layout_as_bipartite)
which produces a graph like below
Related