logo标签列表

使用均匀分布的边生成一个随机图形。

algorithmrandomgraph
4

我正在寻找一种高效的算法，用于生成一个给定节点数的简单连通图。类似这样：

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.
3个回答
1

这可能有点令人惊讶，但如果您选择（随机选择）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)

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

1
为了对这个答案更加严谨，界限是ln(n)/n，并在大n的极限下保持不变。 "随机性"是从所有边的集合中均匀选择的随机边，有许多方法可以制作随机图，但这个过程通常被称为Erd ̈os-Renyi。 这是一个迷人的主题，有大量的研究成果。 物理学家称之为渗透理论，其他领域则有其他名称。 - Hooked
1
你可能需要先创建一个最小生成树以确保连通性。然后，随机生成两个尚未连接的节点并将它们连接起来。重复此过程直到你有S条边。
对于最小生成树，最简单的方法是从一个随机节点开始构建树。对于每个剩余的节点（随机排序），将其连接到树中的任何节点。你选择树内节点的方式（进行连接）定义了每个节点的边分布。
0

一个非常常见的随机图生成算法（在许多学术作品中使用）基于RMat方法，或者是Kronecker图形式的推广。这是一个简单的迭代过程，使用非常少的参数，并且易于扩展。

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

许多图形基准套件都实现了这两种版本，例如：

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接