生成强连通、均匀分布的随机有向图

Question

我正在开发一个程序，使用蒙特卡罗模拟方法来找到进化图论的性质。其中一个主要功能是能够生成均匀分布的随机图，以便我们可以确定图的一般属性。对于连通无向图的情况，我已经实现了此答案中概述的解决方案。

然而，对于有向图，生成从Wilson算法获得的单向均匀生成树并不能保证图是强连通的，并且似乎添加额外的边以使生成树双向化会引入偏差。

我觉得我可能漏掉了一些明显的东西/误解了一些东西，但我的请求基本上是：是否有人能向我推荐一个高级方案，使我能够生成强连通、均匀分布的随机有向图？

- dl101

---

你测试过那个答案是否真的生成了均匀无向图吗？我有些怀疑。 - David Eisenstat

这些图是否没有标签？你认为哪两个图是相等的，例如它们只有标签不同？这对于“均匀分布”实际意义有很大影响。 - ead

Answer 1

我能想到的最简单的解决方案是随机生成均匀分布的有向图，然后拒绝任何不强连通的图。这将保持均匀分布并保证所需特性。虽然效率可能不是很高，但如果您进行一些测试，就可以确定。

- Edward Doolittle

---

生成均匀分布的有向图是那么容易吗？如果它们没有标签，怎么办？我们如何确保没有偏差？ - ead

如果未标记，则接受每个生成的带标签图，概率相等，即自同构数的倒数（例如，使用nauty计算）。由于几乎所有的有向图只有平凡的自同构，因此对于中等大小的图形，分布之间的差异可能是可以忽略不计的。 - David Eisenstat

@ead 生成均匀分布的有向图是唯一的真正问题，但并不难。应该考虑分布均匀的度量方式：在Erdos-Renyi模型中，我们从给定数量n个顶点开始，并以概率p（=0.5对于均匀情况）从顶点a到顶点b生成一条边。对于所有n ^ 2条可能的边进行操作。该算法的运行时间为O（n ^ 2），这也是您可以做到的最好的。由于几乎所有的有向图都是强连通的（Moon和Moser的论文），拒绝掉的比例很小。 - Edward Doolittle

几乎全部，是的，但如果密度被控制得足够稀疏（通过降低p或固定弧数），则不是几乎全部。不过@EdwardDoolittle可能已经知道这一点了。 - David Eisenstat

@DavidEisenstat 是的，这就是我所说的“应该考虑分布是否均匀”的意思。“几乎全部”适用于边缘概率为0.5的分布。在没有其他信息的情况下，我认为这就是海报的意思。 - Edward Doolittle

Answer 2

有人能够推荐一个高级方案，使我能够生成强连通、均匀分布的随机二分图吗？

我曾经遇到过类似的问题，需要生成测试数据的表达式树。我发现，如果你找出如何计算唯一树的数量，问题就变得容易了。我的意思是，我发现对于具有N个内部节点的完全二叉树，基于N的唯一树的数量是卡特兰数。然后对于具有N个总节点的带有一元分支的二叉树，基于N的唯一树的数量是莫茨金数。

然后我找到了整数序列在线百科全书®。因此，如果您知道一个可以唯一标识图形的值N，并且您知道相应的唯一图形计数，并将这些计数放入OEIS搜索中，您应该会得到一个页面，可以帮助您进行搜索。例如，对于完全二叉树，使用卡特兰数或莫兹金数。在此过程中，我发现生成它们的关键之一是递归关系。

或者，您可以在搜索中使用关键字，但这可能不会得到精确匹配。我只是通过数字序列而不是关键字找到了莫兹金数。

以下是强连通有向图的OEIS查询。

如果你知道给定N的计数，并且可以为给定N生成所有图形或可以将一个值与图形一一对应，则只需生成随机整数并获取/生成相应的图形。如果我正确理解了你的问题，这应该可以解决它。

我对这个问题的OEIS序列的最佳猜测是：

具有n个未标记节点的无环有向图数量。A003087 其中参考了Uniform random generation of large acyclic digraphs TL;DR

有关相关历史，请参见我的问题：Algorithm improvement for enumerating binary trees

- Guy Coder

---

@DaveGalvin 我不知道哪个序列是正确的，因为有些信息缺失，例如rooted、labeled、cyclic等。我希望发布悬赏的人能够明确哪个是正确的OEIS序列。如果他们这样做了，那么我会更努力地工作。 - Guy Coder