如何创建具有固定度数序列的随机二分图？

Question

我想在 igraph 或其他 r 包中生成一个具有固定度序列的随机二分图。我熟悉如何生成具有固定度数序列的随机图以及如何在 igraph 中生成随机二分图——但我无法弄清楚如何生成具有固定度数序列的随机二分图（如 Newman，Watts 所述和 Strogatz (2002)）。

Answer 1

使用二分版的配置模型：

为两个分区中的每一个创建顶点 ID
将每个顶点 ID 复制与其度数一样多的次数
如果有 ID，则打乱列表并匹配它们，创建一个图

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)

您现在可以查看 degree(graph)。

请注意，这可能会创建多图（具有平行边的图），并且它不会对二分多图集进行均匀采样。但是，可以证明，如果您拒绝所有 non-simple 个结果，则抽样变得均匀。

Answer 2

我们可以通过定义out.degree和in.degree来使用sample_degseq（从借用数据）

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)

生成如下图

如何创建具有固定度数序列的随机二分图？

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

r

igraph

bipartite