提问人：SupBro 提问时间：10/27/2023 最后编辑：SzabolcsSupBro 更新时间：10/29/2023 访问量：40
如何生成一个随机有向循环图，每个节点都有定义的“平均”边数？（在 R 语言中）
How to generate a random directed cyclic graph with a defined "average" number of edges for each node? (in R language)
问：
我想生成随机有向循环图，同时定义每个节点的节点数和平均边数。 我所说的“平均边数”是指每个节点的度数通常是我定义的度数，其降低或升高的可能性较低。
例如，我想要一个每个节点有 3 条边的 DCG 80% 的节点具有 3 度， 15% 度数为 2 的节点， 度数为 1 的 5% 节点 （注意：所有节点都应该有边，没有断开连接的节点）
我还想定义生成的 DCG 中的循环数。
我不知道是否有已经实现的东西可以做到这一点。
我尝试使用带有 erdos.renyi.game 的 igraph
library(igraph)
nodes = 20
edges = 40
g <- erdos.renyi.game(nodes, edges, type = "gnm",
directed = TRUE, loops = FALSE)
is.dag(g) ##FALSE --> it's a Directed Cyclic Graph
x = degree(g)
mean(x)
table(x)
names(sort(-table(x)))[1]
hist(x)
plot(g)
有 20 个节点和 40 条边、有向边且没有自环，我得到了一个 DCG，但我有 2 个问题：
首先，我无法定义每个节点的边数，在这里我尝试拥有两倍于节点数的边数，希望每个节点平均获得 2 条边，但我最终得到随机度数，范围高达 8 度的节点
其次，我无法定义周期数或定义周期的节点数，因此，如果我有两个节点相互指向，则计为 DCG。如果我可以定义涉及 2 个以上节点的测试周期，那就更好了。
答：
0赞
Allan Cameron
10/27/2023
#1
我认为这个功能应该可以满足您的需求。从本质上讲，它创建一个随机边缘列表，其中包含至少一次每个节点。edgelist 中的边数是通过将节点数和所需的平均边数相乘来确定的。
在采样过程中，可能会偶然发生一些自循环。这些通过重新采样进行替换，直到没有自环路残留。
generate_cyclic <- function(nodes, ave_edges) {
ave_edges <- ave_edges/2
from <- c(nodes, sample(nodes, floor(length(nodes) * (ave_edges - 1)), TRUE))
to <- c(sample(nodes, floor(length(nodes) * (ave_edges - 1)), TRUE), nodes)
while(any(from == to)) {
i <- which(from == to)
from[i] <- sample(nodes, length(i), TRUE)
}
igraph::graph_from_edgelist(cbind(from, to))
}
测试，我们得到
library(igraph)
g <- generate_cyclic(LETTERS[1:20], ave_edges = 3)
is.dag(g)
#> [1] FALSE
x = degree(g)
mean(x)
#> [1] 3
hist(x)
plot(g)
评论
igraph::sample_fitness()