隨機網絡：網絡是靜態均勻的

以往圖論研究的都是規則網絡，20世紀50年代末，匈牙利的兩位數學家埃爾德什和雷尼第一次指出真正的網絡圖，如社會關系網絡等都不是漂亮規整的，而是無比復雜的。鑒于這些網絡圖的高度復雜性，兩位數學家認為這些網絡都是隨機的。1960年埃爾德什和雷尼發表了一篇經典論文，用相對簡單的隨機圖來描述網絡，建立了著名的隨機圖理論，簡稱ER隨機圖理論，應用于網絡時則稱為隨機網絡模型。他們想出了一種新的構造網絡的方法，用這種方法，兩個節點之間連邊與否不再是確定的事情，而是根據一個概率決定。數學家把因此生成的網絡叫隨機網絡（Random networks）。

該論文首次探討了“圖形成網絡是如何形成的”這一重要的問題。在探討網絡圖或網絡中的節點的連接數量的時候，他們使用隨機性來解決圖論問題的特色就顯現了出來。規則網絡圖的特別之處就在于每個節點都有恰好同等數量的連接。在二維的垂直交叉直線構成的網絡格中，每個節點正好都有4個連接；在六角形的網絡中，每個節點都正好和另外3個節點相連。而在隨機網絡中，根本不存在這樣的規則性。隨機網絡中的每個節點隨機地與少數其他節點連接。隨機網絡在節點之間有較低的聚集度。同時，隨機網絡在網絡的任何兩個節點間也有較低的分離度。隨機連接更可能令網絡中遠距離的部分彼此靠近。隨機網絡模型的前提是平均主義：我們完全隨機地安排連接，因此所有的節點都有等同的機會獲得連接。

因此，隨機圖論預言，如果我們隨機安排社會連接，那么所得到的社會就是非常民主的，所有人都處于中間狀態，我們的網絡是一個非常一致的結構。隨機網絡的特征是，大多數節點擁有的連接數是一樣的，并沒有一個高度連接的節點存在。

在埃爾德什和雷尼的隨機圖理論里平均值占主導地位，該理論預言大多數人認識的人數量相當，大多數網站的訪問量也大體相同。“由于自然界是閉著眼睛向外‘拋灑’連接，從長遠來看，不會有特別走運或特別不走運的節點”巴拉巴西評論道，“該理論將復雜性與隨機性看作一回事”。

以一個平均值就能表征出整個群體特性的分布，我們稱之為泊松分布。隨機網絡的節點的度服從泊松分布，因而比較“均勻”，即大部分節點的度相差不多，而且具有較小的平均最短路徑長度和較小的群集系數。它們成功地揭示了隨機網絡的許多重要性質都是隨著網絡規模的增大而突然涌現的，ER理論對于網絡科學理論的影響長達40年之久，埃爾德什被譽為20世紀的歐拉，并于1984年獲得沃爾夫獎。用圖論的語言和符號精確簡潔地描述各種網絡，為數學家和物理學家等提供了描述網絡的共同語言和研究平臺，至今仍然是網絡科學研究的有力方法之一，這是網絡模型發展史上的第二個里程碑。

埃爾德什和雷尼的隨機圖理論自1960年問世以來，就主宰了有關網絡的科學思考。但真實的網絡世界經驗告訴我們，我們生活的世界遠沒有那么隨機，在復雜系統背后，一定還存在某種秩序。隨機網絡模型的建立是在兩個簡單的，但同時也容易被人忽視的假設基礎之上。首先，從一系列節點出發，一旦有了所有的節點，假設節點的總數就確定了，而且在網絡的生命周期內不會改變，即網絡是靜態的。其次，所有的節點都是一樣的，由于看不出節點之間的差別，我們只是隨機地將它們連接起來，網絡是均勻的。我們知道在現實生活中，網絡是不斷擴張的，會不斷接收新的節點。但在網絡研究的40年時間里，沒人對這些假設提出疑問。隨機網絡成了網絡模型的主導，人們普遍相信真實的復雜網絡從根本上來講都是隨機的。但小世界網絡和中心節點的發現改變了人們對隨機網絡的認識。