如何生成随机图？

Question

我希望能够在Java中生成随机、无向和连通的图。此外，我希望能够控制图中的最大顶点数。我不知道解决这个问题的最佳方法是什么，但以下是我能想到的几个：

(1)在0和n之间生成一个数字，并将其设为顶点数。然后，以某种方式将顶点随机链接在一起(可能生成每个顶点的随机数，并让它成为从所述顶点产生的边数)。从任意顶点(比如宽度优先搜索)开始遍历该图，并让我们的随机图G成为所有访问节点(这样，我们确保G是连通的)。

(2)生成一个随机平方矩阵( 0's和1's)，其边长介于0和n之间(以某种方式)，这将是图的邻接矩阵(矩阵的对角线应该是1的，也可以是0的)，从图中构造一个数据结构，从任何节点遍历图，得到一个连通的节点列表，并调用图G。

任何其他产生充分随机图的方法都是受欢迎的。注记：我不需要一个纯粹的随机图，也就是说，你生成的图不一定有任何特殊的数学性质(比如某种类型的均匀性)。我只需要大量的图表来测试其他的东西。

下面是我正在使用的Java Node类：

public class Node<T> {
    T data;
    ArrayList<Node> children= new ArrayList<Node>();
    ...}

下面是我使用的Graph类(您可以知道为什么我现在只对连通图感兴趣)：

public class Graph {
    Node mainNode;
    ArrayList<Node> V= new ArrayList<Node>();

    public Graph(Node node){
        mainNode= node;
    }
    ...}

举个例子，我现在就是这样为测试目的制作图表的：

//The following makes a "kite" graph G (with "a" as the main node).

/*     a-b
        |/|
        c-d
*/
Node<String> a= new Node("a");
Node<String> b= new Node("b");
Node<String> c= new Node("c");
Node<String> d= new Node("d");
a.addChild(b);
a.addChild(c);
b.addChild(a);
b.addChild(c);
b.addChild(d);
c.addChild(a);
c.addChild(b);
c.addChild(d);
d.addChild(c);
d.addChild(b);
Graph G1= new Graph(a);

Answer 1

不管你想用你的图做什么，我想它的密度也是一个重要的参数。否则，您只需使用随机大小生成一组小的团(完整的图)，然后将它们随机连接起来。

如果我是正确的，我建议您使用Erdős-Rényi模型：它很简单，与您最初提议的不远，并且允许您控制图形密度(所以，基本上是:链接的数量)。

下面是对这个模型的简短描述：

1. 定义概率值p(p越高，密度越大: 0=no链，1=fully连通图)；
2. 创建n个节点(作为对象，作为一个邻接矩阵，或任何适合您的东西)；
3. 每对节点都与一个(独立的)概率p相连，所以你必须用这个概率p来判断它们之间是否存在一条链路。例如，我想你可以粗略地画一个值q在0到1之间，并创建一个当且仅当Q< p的链接，然后对图中每对可能的节点做同样的事情。

用这个模型，如果你的p足够大，那么很可能你的图是连通的。详情请参阅维基百科)。在任何情况下，如果您有几个组件，也可以通过在不同组件的节点之间创建链接来强制它的连接性。首先，您必须通过执行宽度优先搜索(每个组件一个)来识别每个组件。然后，在两个不同的组件中选择节点对，在它们之间创建一个链接，并将两个组件视为合并。重复这个过程，直到剩下一个组件为止。

Answer 2

唯一棘手的部分是确保最终的图是连通的。要做到这一点，您可以使用不相交集数据结构。跟踪分量的数量，最初n.重复挑选随机顶点u和v的对，在图和不相交的集合结构中添加边(u，v)，当该结构告诉您u和v属于不同的组件时，减少组件计数。当组件计数达到1时停止(请注意，使用邻接矩阵可以简化图中边(u，v)已经存在的情况的管理:在这种情况下，adju将第二次设置为1，这没有任何效果)。

如果您发现这会创建过于密集(或过于稀疏)的图形，那么当端点已经是同一组件的一部分(或它们是不同组件的一部分)时，您可以使用另一个随机数来只添加边沿的k%。

Answer 3

本文提出了一种统一采样具有给定度序列的连通随机图的算法，并给出了一个有效的实现方法。它可以在几个库中使用，如Networkit或in。

具有指定度随机连通图的快速生成 Fabien Viger，Matthieu Latapy

在随机图上进行模拟时要小心:如果不是均匀采样，那么它们可能具有影响模拟的隐藏性质；或者，均匀采样图可能与代码在实践中遇到的图非常不同.