使用Erdős-Rényi模型檢查圖是否是隨機的？

Question

給出一些圖，我想確定它是隨機產生的可能性。有人告訴我，與Erdős-Rényi模型的比較是獲取這些信息的好方法，但我無法弄清楚如何做到這一點。

有什麼建議嗎？

Answer 1

最簡單的方法可能是將預期的鏈接數與您在給定圖中觀察到的數量進行比較。一個稍微聰明的方法是檢查度分佈。 Erdős-Rényi圖將具有二項分佈，而現實世界的網絡通常是冪律。

如果您有什麼其他類型的模型用於生成圖表，您可能會更容易測試。

Answer 2

您將無法說出是否隨機生成單個圖。如果生成算法是隨機的，那麼您必須檢查邊緣分佈的隨機性。但是您需要使用該算法生成的許多實例。更好地檢查數學，密碼學和信息論中隨機性的概念。 [或者你想從rfc 1750開始]

Erdős-Rényi模型基本上規定，你取n個節點，每個可能的邊有概率p存在[G（n，p）模型]。因此，通過p，您可以生成期望的邊數和偏離該期望值。如果圖表的顯着比例在這個期望的標準偏差之內，那麼您可能不會說您的算法是隨機的，但您至少有一個特徵未被發現，即預期的邊緣數量。

但是，如果沒有很多狀態（圖表，中間圖形生成步驟或類似的），你將會丟失在那裏。說，我給你一個數字：4.是否隨機產生？

Answer 3

你可以在www.statnet.org看看R的ERGM包（www.r-project.org）。儘管您可能無法100％確定地發現您的觀測網絡是由隨機過程產生的，但您可以評估它是由隨機或非隨機夥伴選擇過程產生的可能性。 ERGM有一個稱爲gof的功能，它代表擬合優度，並將觀察到的網絡與模擬隨機網絡進行比較，並查看網絡統計數據，如：測地距離分佈，沿邊共享夥伴分佈，程度分佈和黑社會人口普查分佈。這可以讓你做出明智的決定，不管你是否認爲你的網絡是隨機的。