1.2　隨機圖模型

在現實世界中，不確定現象是普遍存在的。例如，漂浮在液面上的微小粒子不斷地進行著雜亂無章的運動，粒子在任一時刻的位置是不確定的;又如公共汽車站等車的人數在任一時刻也是不確定的，因為隨時都可能有乘客的到來和離去。這類不確定現象，表面看來無法把握，其實，在其不確定的背后，往往隱藏著某種確定的概率規律，因此，以概率和數理統計為基礎的隨機模型就成為解決此類問題最有效的工具之一。

如果網絡的節點不是按確定的規則連線，譬如按純粹的隨機方式連線，所得到的網絡就稱為隨機網絡。1960年現代數學大師、匈牙利數學家Erds和Reni建立了隨機圖理論，研究復雜網絡中隨機拓撲模型（ER），自此ER模型一直是研究復雜網絡的基本模型。

隨機網絡的第一個模型:給定網絡節點總數N，網絡中任意兩個節點以概率p連線，生成的網絡全體記為G（N，p），構成一個概率空間。由于網絡中連線數目是一個隨機變量X，取值可以從0到N（N-1）/2，有m條連線的網絡數目為，其中一個具有m條連線的特定網絡出現的概率為P（G_m）=p^m（1-p）^{[N（N-1）/2]-m}。因此，該模型可生成的不同網絡的總數為2^N（N-1）/2，它們服從二項分布。網絡中平均連線數目為pN（N-1）/2。

隨機網絡的第二個模型:給定網絡節點總數N和連線總數m，而這些連線是從總共N（N-1）/2條可能的連線中隨機選取的，生成的網絡全體記為G（N，p），構成一個概率空間。這樣可以生成不同網絡的總數為，它們出現的概率相同，服從均勻分布。網絡中兩個節點連線的概率為p=2m/[N（N-1）]。