隨機圖
在數學中,隨機圖是指由隨機過程產生的圖[1]。隨機圖的理論處於圖論和概率論的交叉地帶,主要研究各種經典隨機圖的性質。隨機圖的實際應用主要在複雜網絡中所有建模領域中。第一批關於隨機圖的結果是保羅·埃爾德什和阿爾弗雷德·雷尼在1959年至1966年的一系列論文中提出的ER隨機圖。[2]。在其他語義中,任何圖模型都可以被稱為隨機圖。
定義與模型
編輯隨機圖的「隨機」二字體現在邊的分佈上。一個隨機圖實際上是將給定的頂點之間隨機地連上邊。假設將一些紐扣散落在地上,並且不斷隨機地將兩個紐扣之間系上一條線,這樣就得到一個隨機圖的例子[3]。邊的產生可以依賴於不同的隨機方式,這樣就產生了不同的隨機圖模型。最常被討論的模型是Edgar Gilbert提出的 G(n,p)模型:p為邊概率,即G中任意兩個頂點之間相連的概率。在這種模型下,一個特定的圖出現的概率為 ,其中 [4].
與G(n,p)模型緊密相關的模型是埃爾德什和雷尼共同研究的ER模型,表示為G(n,M):擁有M個邊的圖出現概率是相同的。當0 ≤ M ≤ N, G(n,M) 總共有 種可能的確定圖,每種圖出現的概率是 [5]。若將隨機圖的生成過程描述為一個隨機過程:開始時有n個頂點且互相沒有邊連接,每次迭代都從缺失的邊集合中均勻的選擇一條新邊;那麼ER模型可以被看作是隨機圖生成過程中迭代M次時的一個快照。
另一種隨機圖模型叫做內積模型,是GilbertG(n,p)模型的推廣形式。內積模型的機制是對每一個頂點指定一個實係數的向量,而兩個頂點之間是否連接的概率則是它們的向量的內積的函數。
定義更廣泛的隨機圖模型的方法是定義所謂的網絡概率矩陣。這個矩陣的係數就是邊概率,因此詳細刻畫了隨機圖的模型。網絡概率矩陣模型可以推廣到有向圖和帶有權重的圖。
隨機正則圖是隨機圖中特殊的一類,它的性質可能會與一般的隨機圖不同。
性質
編輯隨着邊概率的不同,隨機圖可能會呈現不同的屬性。對於最典型的ER模型,埃爾德什與雷尼研究了當頂點數目 n 趨向於正無窮大時,ER隨機圖的性質與概率 p 之間的關係。他們發現,當 p 的值越過某些門檻時,ER隨機圖的性質會發生突然的改變[3]。ER隨機圖的許多性質都是突然湧現的,比如說,當 p 的值小於某個特殊值之前,隨機圖具有某個性質的可能性等於0,但當 p 的值大於這個特殊值以後,隨機圖具有這個性質的可能性會突然變成1。
舉例來說,當概率 p 大於某個臨界值 pc(n) 後,生成的隨機圖幾乎必然是連通的(概率等於1)。也就是說,對於散落在地上的 n 個紐扣,如果你以這樣的概率 p 將兩個紐扣之間系上線,那麼你拿起一顆紐扣時就幾乎能帶起所有的紐扣了[3]。
隨機樹
編輯隨機樹是隨機圖的一類。如同隨機圖一樣,隨機樹是一個經由隨機過程建立的樹或有向樹。隨機數的類型包括隨機最小生成樹、隨機二叉樹、隨機二叉查找樹和隨機森林等。
當頂點數n較大時,頂點數目為k的隨機樹的分佈接近於泊松分佈。
隨機樹的一種生成方法是利用隨機置換。首先生成一個 階隨機置換函數,將 個可能連起來的邊標上 1 至 的序號。然後按照從小到大的序號排列為原本沒有邊的圖一一添加邊。添加第 條邊時,如果發現添加後會導致圖中出現一個圈,那麼就放棄添加這條邊,而開始添加第 條邊。最後得到的就是一個隨機樹[6]。
參見
編輯參考來源
編輯- ^ Béla Bollobás, Random Graphs, 2nd Edition, 2001, Cambridge University Press
- ^ 第一篇論文發表於1959年,標題為「On Random Graphs I」(《論隨機圖 I》),Publ. Math. Debrecen 6, p290.
- ^ 3.0 3.1 3.2 汪小帆,李翔,陳關榮. 《复杂网络理论及其应用》. 清華大學出版社. 2006. ISBN 9787302125051 (中文).
- ^ Béla Bollobás, Probabilistic Combinatorics and Its Applications, 1991, Providence, RI: American Mathematical Society.
- ^ Béla Bollobás, Random Graphs, 1985, Academic Press Inc., London Ltd.
- ^ Alexandr Kazda. The Random Tree Process. Center for Discrete Mathematics and Theoretical Computer Science. [2011-04-24]. (原始內容存檔於2016-03-04).