以随机算法均匀生成具有 n 个顶点、m 个边的图

Question

简单的问题，还没有找到简单的答案。我想要一个有 N 个顶点，M 个边，均匀随机的图。在合理的时间复杂度内（最坏情况下我会说是拟线性的）。是否存在这样的算法，如果存在，它是什么？

编辑：澄清：该图是无向的，没有多边或循环边。

Answer 1

应该很简单。只需生成 N 个顶点。然后 M 边。 Select 随机顶点作为源和目标。由于您没有其他要求（如自动机语言），因此这是均匀分布的。

V <- {1, ..., N}
E <- {}
for 1 to M do
    edge <- (random(V), random(V))
    E.push(edge)
return (V, E)

EDIT: Clarification: The graph is undirected, has no multi-edges or loops.

继续生成随机边，直到获得有效边：

V <- {1, ..., N}
E <- {}
for 1 to M do
    repeat
        source <- random(V)
        edge <- (source, random(V \ {source}))
    until E does not contain edge
    E.push(edge)
return (V, E)

对于目标，使用 random(V \ source) 排除循环。 E does not contain edge 不应该关心方向。 IE。它应该考虑

(a, b) = (b, a)

为了 contains 的效率，您应该在实施时使用一些散列结构。

问题是 repeat 循环。根据 random 的工作速度以及 M 与可能边缘数量的接近程度，可能需要一段时间。您可以使用 Floyd-Rivest algorithm (also see Algorithm to select a single, random combination of values?).

等技术加快速度

如果 M 与最大数量相比相当小，它应该运行快（在 N 和 M 中呈线性），因为你没有得到很多边缘碰撞。

Answer 2

要高效地生成随机图，您可以使用Erdős–Rényi model。这是图论中的经典方法。 Java 生成随机图的代码（使用 graphstream 库）类似于：

Graph g = new SingleGraph("Erdos-Renyi model");
// adding the first nodes
g.addNode("0");
g.addNode("1");
// creates the first edge
g.addEdge("0_1", "0", "1");
Integer i = 2;
while(i < numNodes) {
    Node source = g.addNode(i.toString());
    Node dest = g.getNode(random.nextInt(i)+"");
    g.addEdge(source.getId() + "_" + dest.getId(), source.getId(), dest.getId());
    i++;
 }

还有其他模型可以生成图形，例如 Barabási–Albert model。该模型生成一个图，其中一个节点连接得越多，它接收新链接的可能性就越大（描述富者愈富的现象）。 Java 使用 Barabási-Albert 模型生成随机图的代码是：

Graph g = new SingleGraph("Barabasi–Albert model");    
g.addNode("0");
g.addNode("1");
g.addEdge("0_1", "0", "1");
int sumDegree = 2;
Integer i = 2;
while(i < numNodes) {
    Node source = g.getNode(i.toString());
    if(source == null) {
          source = g.addNode(i.toString());
    }
    Node dest = g.getNode(random.nextInt(i)+"");
    double probability = dest.getDegree() * 1.0/sumDegree;
    double r = nextDouble();
    if(probability > r) {
       g.addEdge(source.getId() + "_" + dest.getId(), source.getId(), dest.getId());
        sumDegree = sumDegree + 2;
         i++;
       }
  }

另一种著名的方法是使用 Watts–Strogatz model 生成具有小世界属性的随机图。在这种情况下，大多数节点不是彼此的邻居。然而，任何给定节点的邻居很可能是彼此的邻居，并且大多数节点可以通过少量的跃点从每个其他节点到达。

如您所见，有几种生成随机图的可能性。根据需要的网络特性，应该使用特定的模型。

以随机算法均匀生成具有 n 个顶点、m 个边的图

Generate a graph with n veritces, m edges uniformly at random algorithm

random

algorithm

graph

probability