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

hwamh0ep 于 2023-11-14 发布在 R语言

关注(0)|答案(1)|浏览(213)

我想生成随机有向循环图，同时定义节点数和每个节点的平均边数。“平均边数”意味着每个节点的度通常是我定义的更低或更高的概率更低的度。
例如，我想要一个每个节点有3条边的DCG，我将有80%的节点度为3，15%的节点度为2，5%的节点度为1（注意：所有节点都应该有边，没有断开的节点）
我还想定义生成的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个以上节点的测试循环，那就更好了。

来源：https://stackoverflow.com/questions/77374019/how-to-generate-a-random-directed-cyclic-graph-with-a-defined-average-number-o

1条答案

按热度按时间

uurity8g1#

我认为这个函数应该做你需要的。本质上，它创建了一个随机的边缘列表，其中包含每个节点至少一次。边缘列表中的边缘数量由节点数量和所需的平均边缘数量相乘确定。
在采样过程中，可能会偶然出现一些自环，这些自环通过复位来替换，直到没有自环为止。

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)

型

的

赞(0）回复(0）举报 2023-11-14

我来回答

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

1条答案

相关问题

热门标签

最新问答