如何生成每个节点具有定义的“平均”边数的随机有向循环图？ （R语言）

Question

我想生成随机有向循环图，同时定义节点数和每个节点的平均边数。 “平均边数”是指每个节点的度数通常是我定义的度数，降低或升高的可能性较小。

例如，我想要一个每个节点有 3 条边的 DCG，我将拥有 80% 节点的度数为 3， 15% 节点的度数为 2， 5% 节点的度数为 1 （注意：所有节点都应该有边，没有断开的节点）

我还想定义生成的 DCG 中的周期数。

我不知道是否有已经实现的东西可以做到这一点。

我尝试使用 igraph 和 erdos.renyi.game

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 个节点的测试循环，那就更好了。

Answer 1

我认为这个功能应该可以满足您的需要：

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)