生成边均匀分布的随机图

Question

我试图找到一种有效的算法来生成一个给定节点数的简单连通图。类似于：

Input:
    N - size of generated graph
Output:
    simple connected graph G(v,e) with N vertices and S edges, The number of edges should be uniform distribution.

Answer 1

一种非常常见的随机图生成html" target="_blank">算法（在许多学术著作中使用）基于RMat方法，或Kronecker图形式的泛化。这是一个简单的迭代过程，使用很少的参数，易于扩展。

这里有一个非常好的解释（包括为什么它比其他方法更好）-http://www.graphanalysis.org/SIAM-PP08/Leskovic.pdf

在许多图形基准测试套件中都实现了这两个版本，例如。

>

带有rMat生成器的子目录的BFS基准-http://www.cs.cmu.edu/~pbbs/benchmarks/breadthFirstSearch.tar

Kronecker图形生成器（包括c和matlab代码）——http://www.graph500.org/sites/default/files/files/graph500-2.1.4.tar.bz2

Answer 2

这可能有点令人惊讶，但如果你（随机）选择log（n）边（其中n-最大边数），那么你几乎可以确定你的图形是连接的（一个参考）。如果边的数量远低于log（n），则几乎可以确定图形已断开连接。

如何生成图形：

GenerateGraph(N,S):
    if (log(N)/N) > S) return null // or you can take another action
    V <- {0,...,N-1}
    E <- {}
    possible_edges <- {{v,u}: v,u in V} // all possible edges
    while (size(E) < S):
        e <- get_random_edge(possible_edges)
        E.add(e)
        possible_edges.remove(e)
    G=(V,E)
    if (G is connected)
        return G
    else
        return GenerateGraph(N,S)

如果你需要更多的指导，请告诉我。（顺便说一句。现在我正在处理完全相同的问题！如果你需要生成一些更复杂的图形，请告诉我：-））

Answer 3

您可能希望首先创建一个最小生成树以确保连通性。之后，随机生成两个节点（尚未连接）并连接它们。重复以上步骤，直到你有足够的边缘。

对于最小生成树，最简单的方法是从一个随机节点作为树开始。对于每个剩余的节点（随机排序），将其连接到树中的任何节点。您选择树中的节点（要连接到）的方式定义了边/节点的分布。