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

定義與模型

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

G(n,p)模型緊密相關的模型是埃爾德什雷尼共同研究的ER模型,表示為G(n,M):擁有M個邊的圖出現概率是相同的。當0 ≤ MN, 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]

參見

參考來源

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.