隨機圖

在數學中，隨機圖是指由隨機過程產生的圖。隨機圖的理論處於圖論和概率論的交叉地帶，主要研究各種經典隨機圖的性質。隨機圖的實際應用主要在複雜網絡中所有建模領域中。第一批關於隨機圖的結果是保羅·埃爾德什和阿爾弗雷德·雷尼在1959年至1966年的一系列論文中提出的ER隨機圖。。在其他語義中，任何圖模型都可以被稱為隨機圖。

定義與模型

隨機圖的「隨機」二字體現在邊的分佈上。一個隨機圖實際上是將給定的頂點之間隨機地連上邊。假設將一些紐扣散落在地上，並且不斷隨機地將兩個紐扣之間系上一條線，這樣就得到一個隨機圖的例子。邊的產生可以依賴於不同的隨機方式，這樣就產生了不同的隨機圖模型。最常被討論的模型是Edgar Gilbert提出的 G(n,p)模型：p為邊概率，即G中任意兩個頂點之間相連的概率。在這種模型下，一個特定的圖出現的概率為$p^{m}(1-p)^{N-m}$，其中$N={\tbinom {n}{2}}$.

與G(n,p)模型緊密相關的模型是埃爾德什和雷尼共同研究的ER模型，表示為G(n,M)：擁有M個邊的圖出現概率是相同的。當0 ≤ M ≤ N, G(n,M) 總共有${\tbinom {N}{M}}$種可能的確定圖，每種圖出現的概率是$1/{\tbinom {N}{M}}$。若將隨機圖的生成過程描述為一個隨機過程：開始時有n個頂點且互相沒有邊連接，每次迭代都從缺失的邊集合中均勻的選擇一條新邊；那麼ER模型可以被看作是隨機圖生成過程中迭代M次時的一個快照。

另一種隨機圖模型叫做內積模型，是GilbertG(n,p)模型的推廣形式。內積模型的機制是對每一個頂點指定一個實係數的向量，而兩個頂點之間是否連接的概率則是它們的向量的內積的函數。

定義更廣泛的隨機圖模型的方法是定義所謂的網絡概率矩陣。這個矩陣的係數就是邊概率，因此詳細刻畫了隨機圖的模型。網絡概率矩陣模型可以推廣到有向圖和帶有權重的圖。

隨機正則圖是隨機圖中特殊的一類，它的性質可能會與一般的隨機圖不同。

性質

隨着邊概率的不同，隨機圖可能會呈現不同的屬性。對於最典型的ER模型，埃爾德什與雷尼研究了當頂點數目 n 趨向於正無窮大時，ER隨機圖的性質與概率 p 之間的關係。他們發現，當 p 的值越過某些門檻時，ER隨機圖的性質會發生突然的改變。ER隨機圖的許多性質都是突然湧現的，比如說，當 p 的值小於某個特殊值之前，隨機圖具有某個性質的可能性等於0，但當 p 的值大於這個特殊值以後，隨機圖具有這個性質的可能性會突然變成1。

舉例來說，當概率 p 大於某個臨界值 p_c(n) 後，生成的隨機圖幾乎必然是連通的（概率等於1）。也就是說，對於散落在地上的 n 個紐扣，如果你以這樣的概率 p 將兩個紐扣之間系上線，那麼你拿起一顆紐扣時就幾乎能帶起所有的紐扣了。

隨機樹

主條目：隨機樹

隨機樹是隨機圖的一類。如同隨機圖一樣，隨機樹是一個經由隨機過程建立的樹或有向樹。隨機數的類型包括隨機最小生成樹、隨機二叉樹、隨機二叉查找樹和隨機森林等。

當頂點數n較大時，頂點數目為k的隨機樹的分佈接近於泊松分佈。

隨機樹的一種生成方法是利用隨機置換。首先生成一個 $\scriptstyle {\frac {n}{2}}(n-1)$ 階隨機置換函數，將 $\scriptstyle {\frac {n}{2}}(n-1)$ 個可能連起來的邊標上 1 至 $\scriptstyle {\frac {n}{2}}(n-1)$ 的序號。然後按照從小到大的序號排列為原本沒有邊的圖一一添加邊。添加第 $\scriptstyle k$ 條邊時，如果發現添加後會導致圖中出現一個圈，那麼就放棄添加這條邊，而開始添加第 $\scriptstyle k+1$ 條邊。最後得到的就是一個隨機樹。

參見

• 玻色-愛因斯坦凝聚
• 腔體法
• 複雜網絡
• 小世界網絡
• 無尺度網絡
• ER隨機圖