生成预先指定度数分布的无向网络，不包含任何自环。

Question

我希望生成一个包含100个节点的无向网络，其中一半节点的度数为10，另一半节点的度数为3。请问是否可以构建这样一个没有自环的网络？

以下是指定的代码：

library(graph)
degrees=c(rep(3,50),rep(10,50))
names(degrees)=paste("node",seq_along(degrees)) #nodes must be names
x=randomNodeGraph(degrees)

我可以获得这样的图，但是其中包含自环。

有没有办法获得没有自环的图？

- upabove

Answer 1

使用Bioconductor的图形包(请点击这里)，很容易完成这个操作。

#install graph from Bioconductor
source("http://bioconductor.org/biocLite.R")
biocLite("graph")

#load graph and make the specified graph
library(graph)
degrees=c(rep(3,50),rep(10,50))
names(degrees)=paste("node",seq_along(degrees)) #nodes must be names
x=randomNodeGraph(degrees)

#verify graph
edges=edgeMatrix(x)
edgecount=table(as.vector(edges))
table(edgecount)
#edgecount
# 3 10 
#50 50

- Jeremy Coyle

---

是否也可以用两列格式代替邻接矩阵来表示这个图形？ - upabove

t(edges) 能得到你想要的吗？ - Jeremy Coyle

您提出的图是有向图，总度数由入度和出度组成。我想要一个图，如果节点1连接到节点5，则节点5到节点1也保持同样的连接。这是否可行？ - upabove

ugraph(x) 是底层无向图。 - Jeremy Coyle

文档没有说明如何禁用自环。 - upabove

Answer 2

Erdős–Gallai定理回答了这个问题，即是否可能构造出这样的图。

它基于您图形的非递减度序列，而在您的情况下为：

ds <- c( rep( 10, 50 ), rep(3,50) )

你可以通过以下方式计算不等式的右侧：

rhs <- (1:100 * 0:99) + c( rev(cumsum(rev(apply( data.frame(ds, 1:100) , 1, min ))))[-1], 0 )

左边由

lhs <- cumsum( ds )

最后：

all( lhs <= rhs )
[1] TRUE

- Beasterfield