第2章p2p網路協議和拓撲結構 1

2.1常見網路模型

隨即網路的研究是基於圖理論的。該理論創始於20世紀40年代，最早的經典隨機圖型是由erdos和renyi(er)共同提出的er模型。在隨機圖中，變得出現成為概率事件，他將含有n個節點，但具有任意邊的圖作為概率空間，研究當n∞時圖的性質。

隨即圖和經典圖之間最大的區別在於引入了隨機的方法，似的圖的空間變得更大，其數學性質也發生巨大的變化。

構造隨即網路的過程通常稱為演化：從n個鼓勵頂點出發，通過隨機加邊來形成圖隨。即圖理論的主要目標確定在何種連線概率，隨即圖將產生哪些特定的性質。

在隨機圖理論中還定義連通性，度分布，，聚集係數等在各種網路模型中廣為使用的概念。

隨即網路是一種能反映多種隨機因素變數的網路技術。隨機網路中的節點可以表示網路的狀態，而連線各節點之間的箭圖可以理解為狀態之間的傳遞關係。當狀態之間的轉移具有概率性質，而且狀態之間的傳遞關係也服從一定的概率分布時，網路的執行過程就具有隨機性質。

對於隨即網路，包含了從空圖到完全圖的所有可能情況。經典的隨機網路是這樣構造的：給定n個節點，沒有邊，任意兩節點之間都嘗試以某個概率p連線，這樣所構成的網路就叫隨即網路，也就是說隨即網路中的節點與變的關係是不確定的。

數學家已定對隨即網路進行了深入細緻的研究，研究結果表明隨機網路頂點的度值平均值為=p(n-1)≈pn,平均集係數c=p=/n≤1，平均路徑長度l∝.由此，可以總結出隨即網路的特點是：節點之間的平絕路經長度比較短，平均集聚係數比較低，度數服從泊松分布，如圖2-1所示。

儘管對於同樣規模的網路，隨機網路具有短的平均路徑長度。但是，許多實際網路多具有很高的平均集聚係數，而隨機網路卻是乙個區域性集團化很差的網路，平均集聚係數很低。所以，隨機不是實際網路的乙個很好刻畫。

雖然億er隨即圖理論為為基礎的隨機網路作為是網路的模型存在明顯的缺陷，但在20世紀後的40年代中，er隨機圖理論一直是研究複雜網路拓撲的基礎理論，其中的一些基本思想在目前的複雜網路理論研究中任然很重要。