生成具有预先指定的度分布而没有任何自环的无向网络

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)

我可以得到这样的图，但其中包含了自循环。

有没有办法得到一个没有自循环的图？

Answer 1

使用Bioconductor (see here)的图形包很容易做到这一点

#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

Answer 2

Erdős–Gallai theorem回答了这样一个图是否可以构造的问题。

​

​

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

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