r - 如何在 igraph 中生成非循环随机图？

我想在 R igraph 中生成随机无环图。

我主要对无向图感兴趣。

无环无向图是森林，即连接组件是树的图。

我知道函数 sample_pa 根据 Barabasi-Albert 模型为 m=1 无标度无环图生成。如果我们可以强制 igraph 为更高的 m 值生成非循环图，我很感兴趣？

这在数学上是不可能的。节点上的树n有n-1边缘，而森林的边缘更少。对于更高的 in 值，m会有sample_pa更多的边缘，因此会有循环。

或者我们可以根据 igraph R 中的其他算法生成无环图吗

查看 igraph 中的随机图生成器。其中有几个会输出树。例如，检查sample_growing.citation = TRUE

但是，这些都不会对树进行统一采样。据推测，您不仅想生成任何树，还想了解它们来自的分布。

最近我为 igraph 贡献了一个统一的树采样器，以及一个统一的生成树采样器，但它还没有在 R 接口中。您可以使用Mathematica 界面（当然也可以使用 C 语言）进行尝试。

Table[IGTreeGame[10], 6]

grid = IGSquareLattice[{10, 10}];
HighlightGraph[grid, IGRandomSpanningTree[grid], GraphHighlightStyle -> "DehighlightHide"]

但是从有向图中，总是可以获得无向版本。

但不是非循环的。

1通过用所需数量的s随机填充邻接矩阵的上部，很容易生成随机有向无环图。

当您将其转换为无向时，它通常不会是非循环的。

例如，这不是无向的：

事实上，任何简单的无向图都可以定向，因此有向图将是无环的。无向无环图和有向无环图之间几乎没有关系。