交通地理與網路科學/隨機圖

隨機圖

隨機圖是由一些隨機過程生成的圖。隨機圖理論是由 Erdős 和 Rényi 在 1950 年代的一系列論文中創立的。

在大多數隨機圖模型中，頂點的數量是固定的，它們之間的邊以某種隨機方式放置。最簡單的方法之一是固定邊的數量，並將它們均勻地隨機放置在所有可能的頂點對中。換句話說，我們生成一個具有 v 個頂點和 e 個邊的圖的機率分佈，它們都具有相同的機率。該模型通常稱為 G(v,e)，其中 v 表示頂點的數量，e 表示邊的數量。

雖然 G(v,e) 似乎是一個簡單的模型，但事實證明，獲得我們感興趣的一些重要屬性並不容易。因此，已經提出了另一個略有不同的模型，並且大多數數學工作都是在被稱為 G(v,p) 的模型上進行的，其中 v 表示頂點的數量，p 表示在每對頂點之間存在邊的機率。 換句話說，G(v,p) 模型中的圖是透過掃描 n 個頂點的每對頂點並以機率 p 在它們之間放置邊來構建的。

屬性

G(v,p) 中存在 e 個邊的機率為

$p^{e}(1-p)^{{\binom {v}{2}}-e}$

例如，考慮一個隨機圖 G(3,0.8)，該圖具有一個、兩個或三個邊的機率如下所示

隨機圖 G(3,0.8)

具有 e 個邊的圖的機率

$P(e)={\binom {\binom {v}{2}}{e}}p^{e}(1-p)^{{\binom {v}{2}}-e}$

具有 e 個邊的隨機圖數量（v 個頂點）

$N(e)={\binom {\binom {v}{2}}{e}}$

例如，有 15 個不同的隨機圖，它們有 4 個頂點和 2 個邊

具有 4 個頂點和 2 個邊的隨機圖

度數的期望值

${\binom {v}{2}}p$

期望度數值

$c=(v-1)p$

度數分佈

$p_{k}={\binom {v-1}{k}}p^{k}(1-p)^{v-1-k}$

在平均度數近似恆定的大型網路（例如社交網路）中，度數分佈變為泊松分佈

聚類係數

聚類係數衡量網路的傳遞性。它被定義為一個頂點的兩個網路鄰居也是彼此鄰居的機率。由於在 G(v,p) 中，每對頂點都以機率 p 相連，並且與其他任何事無關，因此聚類係數 C 為

$C=p={\frac {c}{v-1}}$

巨型連通分量

隨機圖研究的一個重要特徵是當頂點數量v變大時，圖是如何演化的。更具體地說，如果我們知道當v趨於無窮大時，圖中的大多數頂點都是連通的，那麼這意味著存在一個連通分量的增長速度與圖的增長速度相當。這個連通分量被稱為巨型連通分量。可以證明，當且僅當平均度大於1時，存在巨型連通分量。