生成一个边缘均匀分布的随机图

我试图找到一个有效的算法来生成一个给定节点数的简单连通图。例如：生成一个边缘均匀分布的随机图

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.

来源

2013-11-25 Fihop

您可能想要首先创建最小生成树以确保连接。之后，随机生成两个节点（尚未连接）并连接它们。重复，直到你有S的边缘。

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

来源

2013-11-25 05:41:44 ElKamina

它可能是一个有点出人意料，但如果你选择（随机）log(n)边缘（其中n - 边数），那么你可以几乎确保您的图表连接（a reference）。如果边数远低于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)

让我知道如果你需要更多的指导。（Btw。现在我正在处理完全相同的问题！让我知道是否需要生成一些更复杂的图:-)）

来源

2013-11-25 14:17:31

要在此答案更迂腐一点，边界是“ln（n）/ n”，并且保持在大的“n”极限。 “随机性”是从所有边的集合中均匀选择的随机边，有很多方法可以生成随机图，但是这个过程通常被称为Erd̈os-Renyi。这是一个引人入胜的话题，对此有大量的研究。物理学家称之为渗流理论，其他领域有其他名称。 – Hooked

@Hooked谢谢！确实非常迷人！ –

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

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

有两个版本在许多图形基准测试套件实现，例如

BFS基准与RMAT发生器一个子目录 - http://www.cs.cmu.edu/~pbbs/benchmarks/breadthFirstSearch.tar
克罗内克图形发生器（c和MATLAB代码包括） - http://www.graph500.org/sites/default/files/files/graph500-2.1.4.tar.bz2

来源

2013-11-25 14:49:01 Leeor

生成一个边缘均匀分布的随机图

回答

相关问题