CODEWITHSUNDEEP
rigraphbipartite
avgoustisw
avgoustisw

Reputation: 223

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)).

Upvotes: 2

Views: 568

Answers (2)

ThomasIsCoding
ThomasIsCoding

Reputation: 102241

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

enter image description here

Upvotes: 2

Szabolcs
Szabolcs

Reputation: 25703

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.

Upvotes: 1

Related Questions