2.2 随机网络模型
网络科学旨在建立能够重现真实网络性质的模型。我们遇到的大多数真实网络没有晶格所具有的那种令人愉悦的规则结构，或者蜘蛛网所具有的那种可预测的放射型结构。相反，真实网络乍一看好像是随机连接而成的（图1-4）。随机网络理论通过构建和刻画真正随机的网络来解释这种表面上的随机性。
从建模的角度来看，网络是一个相对简单的对象，仅由节点和链接组成。然而，真正的挑战在于，在哪些节点间放置链接才能重现真实系统的复杂性。在这一点上，随机网络背后的哲学思想很简单：在节点之间随机放置链接。因此，随机网络定义如下（边栏2.1）：
边栏2.1
定义随机网络
随机网络有两种定义方式：
G（N，L）模型
N个节点通过L条随机放置的链接彼此相连。埃尔德什和雷尼在他们关于随机网络的系列论文[2-9]中采用的是这种定义方式。
G（N，p）模型
N个节点中，每对节点之间以概率p彼此相连。该模型是由埃德加·N.吉尔伯特（Edgar N. Gilbert）提出的。[10]
G（N，p）模型固定了两个节点的连接概率p，G（N，L）模型则固定了总链接数L。G（N，L）模型中，节点平均度可以简单地算出，即
=2L/N。G（N，p）模型中，网络其他特征则更容易计算。本书将主要探讨G（N，p）模型，不仅是因为该模型便于计算网络的一些关键特征，还因为在真实网络中，链接数很少保持固定不变。
随机网络由N个节点组成，每对节点相互连接的概率为p。
构建随机网络的步骤如下：
（1）从N个孤立节点开始。
（2）选择一对节点，产生一个0到1之间的随机数。如果该随机数小于p，在这对节点之间放置一条链接；否则，该节点对保持不连接。
（3）对所有N（N-1）/2个节点对，重复步骤（2）。
上述过程得到的网络被称为随机图或随机网络。两位数学家——保罗·埃尔德什和阿尔弗雷德·雷尼在理解随机网络的性质方面发挥了重要作用。为了纪念他们，随机网络被命名为埃尔德什－雷尼网络（边栏2.2）。
边栏2.2
随机网络简史
阿纳托尔·拉波波特是一个移民到美国的俄罗斯人，也是第一个研究随机网络的人。拉波波特最初想成为一名钢琴演奏家，在他意识到一名成功的钢琴演奏家需要有丰厚的财力支持后，拉波波特的兴趣转到了数学上。在他专注于数学和生物学的时候，数学家和生物学家之间几乎没什么交流。在其1995年和雷·索洛莫诺夫合作的论文中[11]，拉波波特指出，逐渐增加网络的平均度，网络连接性会出现一个突然的变化，从彼此不连通的节点组变成一幅具有一个巨大连通分支的图。
保罗·埃尔德什和阿尔弗雷德·雷尼（图2-2）在随机网络方面做出的基础性工作使随机网络的研究达到鼎盛。1959年到1968年间发表的8篇论文中[2-9]，他们在图论中融入了概率论和组合数学，建立了数学领域的一个新分支——随机图论[2]。
图2-2 （a）保罗·埃尔德什（1913—1996）
匈牙利数学家，因其卓越的科学产出和古怪的个性而闻名。实际上，埃尔德什发表的论文数比数学史上任何其他数学家都要多。他和500多个数学家合作撰写过论文，促成了埃尔德什数概念的产生。他传奇般的个性和深远的影响带来了两部传记[12]，[13]和一部纪录片[14]（在线资源2.1）。
（b）阿尔弗雷德·雷尼（1921—1970）
匈牙利数学家，对组合数学、图论和数论都有重要贡献。他的影响超出了数学领域：雷尼熵广泛应用于混沌理论，他参与建立的随机网络理论是网络科学的核心。他的名字被用于命名布达佩斯的阿尔弗雷德·雷尼数学研究院——匈牙利数学的温床。
在线资源2.1 《N是一个数：保罗·埃尔德什的肖像》
1993年发行的保罗·埃尔德什的传记纪录片，由乔治·保罗·西泽瑞（George Paul Csicsery）导演。这部纪录片讲述了埃尔德什的生活及其在科学领域的影响[14]。
扫描二维码下载“湛庐阅读” App，回复书名，观看保罗·埃尔德什的传记纪录片。
在埃尔德什和雷尼发表他们第一篇随机网络论文的同一年，埃德加·N.吉尔伯特[10]也独立提出了他的随机网络模型。不过，由于埃尔德什和雷尼的研究工作影响巨大，他们二人被认为是随机图论的奠基人。
“数学家是一种把咖啡变成定理的装置。”
——阿尔弗雷德·雷尼
（人们通常认为是埃尔德什所说）