在圖中找到邊的概率

我有一個隨機圖G（n，p），其中n = 5000個頂點，邊的概率爲p = 0.004。我不知道圖中邊的期望數是多少，但我對概率論沒有多少了解。在圖中找到邊的概率

任何人都可以幫助我嗎？

非常感謝！

編輯： 如果PE爲可能的邊緣在圖中的號碼，我豈不要計算0.004 * PE上得到圖中邊的預期是多少？

2014-11-22 progNewbie

首先，問自己圖中可能出現的邊的最大數量。這是當每個頂點連接到每個其他頂點（nC2 = n *（n-1）/ 2）時，假設這是一個沒有自環的無向圖）。如果每個可能邊緣的可能性爲0.004，並且可能邊緣的數量爲n（n-1）/ 2，則期望的邊緣數量將是0.004 *（n（n-1）/ 2）。

來源

2014-11-22 21:07:18 Anne

非常感謝，現在我看到:-) – progNewbie 2014-11-22 22:04:02

啊不，我不明白:-D ...爲什麼它被兩分爲二？我是否有n-1種可能性來創建從一個頂點到另一個頂點的邊？ – progNewbie 2014-11-22 22:12:32

如果我按照自己的方式計算出它，我將擁有大約1200萬個邊緣。所以如果概率是0.004有一個邊緣，不應該是0.004 * 12 mio？ – progNewbie 2014-11-22 22:27:09

預期頂點的數量取決於節點數和邊緣概率，如E = p（n（n-1）/ 2）。

如果任何i被允許鏈接到任何j，i-> j和j-> i，那麼圖中可能的邊的總數爲n（n-1）。我是你的朋友，你是我的。如果圖是無向的（邊只意味着我們是朋友），則邊的總數減半：n（n-1）/ 2，因爲i-> j和j-> i是相同的。

與p的乘法給出了預期的邊數，因爲根據概率，每條可能的邊都變成了真實的。由於每個可能的邊緣實際發生，p = 1給出n（n-1）/ 2個邊緣。對於p < 1的圖形，如果要使用所選的p和n實際生成隨機圖形，實際邊數可能（明顯）不同。但是，如果要生成無限數量的隨機圖，預期的邊數將是最常見的觀察邊數。如果您想要生成隨機圖並瞭解網絡測量結果是如何從不同結構的隨機圖形中產生的，NetLogo是一種非常具有教育意義的工具。

來源

2016-04-05 16:50:39 nJGL

在圖中找到邊的概率

回答

相關問題