生成一個邊緣均勻分佈的隨機圖

我試圖找到一個有效的算法來生成一個給定節點數的簡單連通圖。例如：生成一個邊緣均勻分佈的隨機圖

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

生成一個邊緣均勻分佈的隨機圖

回答

相關問題