隨機圖包含兩個最基本的隨機圖模型：第一種隨機圖模型是對給定的n個頂點的空圖，任選兩個頂點，兩個頂點連邊的機率為p 所得到的一個圖；而第二種隨機圖模型是隨機選擇具有M條邊和n 個頂點的一個圖。
基本介紹
- 中文名：隨機圖模型
- 外文名：Random graph model
- 研究範圍：複雜網路
- 提出者：Gilbert E N、Erdos P和Renyi A
- 又名：ER圖模型
- 套用學科：計算機科學與技術、數學等
研究背景,研究簡介,幾何隨機圖模型,層次隨機圖模型,
研究背景
近十多年來，隨著對複雜網路研究熱潮的興起，隨機圖成為一種重要的複雜網路模型，常常稱作隨機網路或隨機圖。人們對複雜網路的魯棒性、傳播動力學等的研究，常常會用到隨機圖，即需要生成隨機圖模型。Erdos P和Renyi A最早研究隨機圖時，他們對隨機圖的本質做了大量的研究。
在複雜網路研究中，生成隨機圖的加邊的機率小於其閾值時生成圖是不連通的（如圖所示，在一堆人中隨機抽取2人相互成為朋友，當抽取的機率小於某個閾值pc時，這堆人不可能通過朋友的朋友相互認識而彼此完全認識），這對進一步研究產生了一定的困難，也不便於用隨機圖模仿現實中的網路，而現實世界的絕大多數網路都是連通的，如網際網路、電力網、交通網等。
研究簡介
隨機圖的2個模型中，第一種隨機圖模型是由Gilbert E N首先提出的，而第二種隨機圖模型是由Erdos P和Renyi A 提出的，人們在不至於混淆的前提下，提及隨機圖是這兩種模型中的一種。由於第二種隨機圖模型是由Erdos P和Renyi A 提出，隨機圖又被稱為ER圖。自從隨機圖建立以來，對隨機圖的研究就從未停止過，隨著對隨機圖研究的深入，隨機圖的理論和套用得到極大的發展，如隨機圖的連通性、隨機圖的著色及色數等等。
幾何隨機圖模型
假設n個節點按照某種機率密度分布在d維區域R中。節點之間的連線機率取決於節點之間的空間距離(歐式距離), 當兩個節點之間的空間距離小於固定值r時, 節點之間存在一條連線, 用G (n, r)表示。
幾何隨機圖模型中的相關參數:平均節點度、節點的度函式、節點度期望
1)節點度:該節點的鄰居數。
2)節點平均度:
3)節點的度分布:網路中存在度為K的節點的機率P(K)隨節點度K的變化規律, 由節點的度函式來描述。
4)度函式P(k):一個隨機選取的節點有k個鄰居的機率, 反映節點的度分布。
5)節點度期望:
, 如果各個節點的度函式相同, E {D} =nP，當n>>P時, 可近似用E {D}來表示Dmean。
層次隨機圖模型
複雜網路在很多情況下都具有層次結構。由Claustet 等人在2008 年提出的層次隨機圖模型，對來自不同領域且具有層次結構的食物鏈網、恐怖攻擊網和梅毒螺旋體的代謝網路分別進行了鏈路預測。該層次結構模型目前還廣泛套用於探究複雜網路的拓撲特性。
網路層次隨機圖就是層次組織模型，其概念為：
a）網路G是具有n 個節點的簡單無向圖；
b）樹狀圖D 是二叉樹，它具有n 片葉子對應於G 中的n 個節點，且它有n －1 個內部節點r 對應於來自D 中形成的節點對；
c）給出G 中的兩個節點i、j和邊連線的機率Pij，其中r 是節點i、j在D 的最近共同祖先。機率Pr∈[0，1]，為每個內部節點r 的機率值，且每個內部節點r 獨立於Pr。那么邊的連線強度Pij=Pr，即兩個節點的連線機率等於距離它們最近的共同祖先節點所賦予的機率。所以，樹狀圖D 和機率集合{Pr}共同定義了層次隨機圖（D，{Pr}）。
