巴拉巴西网络科学

good

因为这一得天独厚的便利,童年时代的巴拉巴西得以自由徜徉在博物馆的图书室和各类收藏品中,甚至能够查阅只有极少数历史学家才能够查阅的文件。 P5

由于在这一领域做出了卓越的贡献,巴拉巴西更成为诺贝尔奖获奖呼声最高的候选者之一。 P6

他的实验结果令人非常惊讶:基本上,互联网是由少数链接数多的页面串连起来的,80%以上页面的链接数不到4个。 P7

作为一名警惕的提问者,他接着把好奇心投入到关于“成功”的问题之上——那些挂在现代艺术博物馆里、看起来脏兮兮不起眼的照片,为什么会被认为是杰作?为什么音乐剧《天上人间》而非《猫》,会成为历史上最杰出的音乐剧?去那些学费昂贵的学校就读到底值不值得?为什么每个领域都只有一小撮人能够成为超级巨星?这些问题成了一切的源起。 P9

网络科学的二十年,是波澜壮阔、跌宕起伏、争议不断的二十年。 P11

这期间,我和巴拉巴西一起合作发表了三篇学术论文,领略了网络科学领军人物开阔的科研视野、炽热的工作热情、高超的写作技巧和平易的人格魅力。 P12

每个章节都有一幅有故事的精美图片作为开篇引言,有趣的案例配有在线视频来阐述,优美细腻的写作方式让这本教科书如小说般引人入胜。 P13

这些网络的随机性包含了有序和无序之间的内在张力,而这正是网络科学的主题。 P14

不过,受此种效应的影响,我们可能会忽略一个最耐人寻味的问题:网络领域是如何成长得这么快的?我把这一章视为我的科学发现旅程,原因其实很简单:我并没有打算对上述问题提供一个无偏见的回答,而是希望从一个参与者的角度去回忆网络科学的兴起。 P16

失败1:第二篇论文(1995年)学得越多,我越觉得自己对真实网络知之甚少。 P17

在博士后岗位上工作了8个月后,我接受了美国圣母大学(University of Notre Dame)提供的教职,这使我在IBM余下的4个月内可以专注地完成我的第二篇关于网络的论文。 P18

我最终放弃了将其发表在期刊上的想法。 P19

我很失望,并于1996年4月25日将该论文再次投稿到《物理评论快报》——结果并没有好多少,论文经过漫长的评审过程之后再次被拒收。 P20

回过头来看,这并不是一封非常有说服力的邮件,没有人回复也就不足为奇了。 P22

1998年年初,我打算再试一次。 P23

普尔和科亨所采用的模型,与同一时期的图论学家埃尔德什和雷尼提出的模型一样。 P24

而一旦链接密度达到临界阈值,网络中会涌现出一个巨连通分支,该连通分支大到几乎可以将其视为整个网络。 P25

发现(1999年)论文提交后不久,我赴西班牙和葡萄牙进行了为期两周的长途旅行,旅行的最后一站是一个在波尔图大学召开的研讨会。 P26

我需要一个安静的地方来仔细思考。 P27

这就意味着,在葡萄牙的剩余2天加上回美国后的7天里,我就得把论文写好。 P28

虽然出乎意料,但这是对我过去5年在网络科学领域经历的诸多挫折的最好回报。 P29

她对比了随机失效和网络攻击(删除枢纽节点)对网络连通性的影响。 P30

这篇论文受到了我们那个(未获资助的)DARPA申请书中的想法启发[12]。 P31

学术界由此开始意识到度分布在网络研究中的核心地位。 P32

网络科学提醒我们注意科研合作和导师制度在科学中的重要作用。 P33

因此,隆巴尔迪尝试把它们组合成手工绘制的关系图,以便他能更专注于自己的工作。 P37

这并不是下一部“世界末日”电影里的场景,而是2003年8月14日前后美国东北部的真实情景:一场大面积停电波及了美国东北部8个州、约4500万人,以及安大略湖区的1000万人。 P39

级联失效的影响大小取决于最初失效节点在网络中的位置及其容量。 P40

例如:复杂的高速公路系统。 P41

2009年,这张卡由总部位于伦敦的汇丰银行(HSBC)在阿联酋签发。 P42

/ 图0-3 网络科学的出现虽然关于网络的研究有着悠久的历史——起源于图论和社会学,网络科学的新篇章却是在21世纪的第一个10年间才出现的。 P43

到了20世纪末,大量涌现的网络地图加快了网络科学的出现。 P44

因此,我们可以采用同样的数学工具来探索这些网络及其所描述的系统。 P45

不过,我们仍然缺少更大动物的神经连接数据。 P46

另外,网络科学从工程学中借鉴了包括控制论和信息论在内的概念,用于理解网络的控制原理;还从统计学那里借鉴了从不完整和有噪声的数据集中抽取信息的方法。 P47

然而,要想完全理解细胞的运转方式和疾病的起源,列出人类所有的基因还不够:我们还需要一幅描绘基因、蛋白质、代谢体及其他细胞组成部分之间相互作用的地图。 P48

为实现该目标,人们在从多个方面努力:投资数百万美元用于绘制细胞网络,开发工具和数据库用于存储、管理、分析病人数据和基因数据。 P50

如今,这个例子被军事学院的教官和学生学习,用于阐述网络模型在决策和业务协调中的重要作用。 P51

基于网络的框架带来了根本性的改变,将传染病的可预测性提升到一个新高度。 P52

为了提高公司内部的信息流动,公司管理部门求助于使用网络科学进行组织管理的Maven 7公司。 P55

创始于2005年的网络科学旗舰会议“NetSci”是其中一个非常成功的网络科学会议,每年的NetSci会议汇集了全球网络科学领域的学者和从业人员。 P56

到了20世纪80年代,贝努瓦·曼德尔布罗特(Benoit Mandelbrot)发表了关于分形的著作[23],托马斯·威滕(Thomas Witten)和莱恩·桑德尔(Len Sander)提出了受限扩散凝聚模型[24],复杂系统领域的研究焦点随之转移到了模式形成方面。 P57

发表70年后,该论文累计获得了高达5000多次引用。 P58

公众对网络科学也是青睐有加。 P59

/ 扫描二维码下载“湛庐阅读”App,回复书名,获取关于网络科学的纪录片。 P61

此图由谷歌的n元词组工具生成,刻画了每年使用“进化”“量子”“网络”的书籍比例。 P62

随着时间推移,该网络跨越了学科边界,开始作为一个独立的生命而存在。 P66

图论起源于1735年的哥尼斯堡(K?nigsberg)。 P69

(c)欧拉构造了一个有4个节点(A、B、C、D)和7个链接的图,每个节点对应着一块陆地,7个链接则对应着7座桥。 P70

换句话说,我们需要一幅刻画各组成部分之间连接关系的地图。 P71

虽然这些网络的节点和链接性质不同,但它们可以用同样的图来表示,由4个节点和4个链接构成,如(d)所示。 P72

还有一些网络同时包含有向的链接和无向的链接。 P73

对于有向网络,平均度是平均入度和平均出度的均值(见公式1.5)。 P74

从而,节点i的度为: 例如,在万维网中,网页的出度kout表示该网页指向的网页数目,其入度kin表示指向它的网页数目。 P76

(b)4个节点中有一个度为1的节点(k1=1),因此p1=1/4;有两个度为2的节点(k3=k4=2),因此p2=1/2;有一个度为3的节点(k2=3),因此p3=1/4。 P77

/ 图1-4 一个真实网络的度分布真实网络中,节点的度差异很大。 P78

注意,底部所示的几个蛋白质有自环,它们的度为2。 P79

/ 图1-5 邻接矩阵(a)邻接矩阵元素的标记方式。 P80

图中还展示了一些可以从邻接矩阵中得到的网络性质,例如链接总数L和平均度/。 P81

完全图的平均度为/=N-1。 P82

图中的每个点对应着邻接矩阵中的一个非零元素,表示存在一个蛋白质相互作用。 P83

本书中,我们主要关注无权网络,但会在合适的时候讨论权重对网络性质的影响(边栏1.3)。 P84

这一现象在经济学中被称为网络外部性(network externality)。 P85

与之类似,第二个映射网络对应着节点集合V上的一个网络(图1-9)。 P86

(c)人类疾病网络的第二个映射是疾病网络:节点是疾病,如果两种疾病和同样的基因相关——由同样的基因突变造成,则它们在该映射网络中彼此相连。 P87

每个节点表示一种原料,节点颜色表示食物的类别,节点大小表示原料的流行程度。 P89

同一对节点之间可能有多条长度相同的最短路径(图1-12b)。 P92

虽然该方法很简洁,但对于大的网络,更高效的方法是边栏1.5描述的广度优先搜索算法。 P93

在随后的迭代中,逐渐增加标记数,直到所有节点都被标记完为止。 P94

计算复杂度和N、L是线性关系,因为每个节点需要进入和离开队列各一次,而每个链接需要被检测一次。 P95

然而,不同连通分支的节点之间不存在路径。 P96

注意,集聚系数的取值介于0和1之间(图1-16a):/ 图1-16 集聚系数(a)度为ki的中心节点i在三种不同连接情况下的局部集聚系数Ci。 P97

公式1.16是在无向网络上集聚系数的定义,集聚系数的定义同样可以扩展到有向网络和加权网络上[13],[14],[15],[16]。 P98

注意,很多真实网络可以同时具备这些基本性质中的多个。 P99

首先,我们使用本节介绍的基本方法来测量蛋白质相互作用网络的特性。 P100

(a)蛋白质相互作用网络的距离分布pd反映了随机选择的两个节点之间距离为d(最短路径的长度)的概率。 P101

换句话说,1=(1,1,…,1)T,这里的T表示矩阵转置。 P102

邻接表是一个大小为L×2的矩阵,每行对应一个链接,记录该链接的起始节点和终止节点。 P103

(2)将该二分网络分别映射到紫色节点和绿色节点上,并分别写出两个映射网络的邻接矩阵;(3)分别计算紫色节点和绿色节点的平均度;(4)对于(3)中得到的两个映射网络,分别计算其节点的平均度。 P104

实际上,公式1.15中的Li是节点i参与的三角形个数:节点i的邻居节点之间的每个链接对应着节点i参与的一个闭合三角形(图1-17)。 P105

埃尔德什数理论是这样的:埃尔德什本人的埃尔德什数是0,与他合作的人的埃尔德什数是1。 P108

此时,你提醒其中一位客人玛丽,告诉她那瓶没有标签的深绿色瓶子里的红葡萄酒是罕见的酒中佳品,比那瓶带着精致红色标签的酒要好得多。 P111

可以肯定的是,当所有客人都彼此认识之后,每个人都会去倒那瓶好葡萄酒。 P112

在这一章中,我们将会看到,这个聚会问题对应着网络科学中的一个经典模型——随机网络模型。 P113

(2)选择一对节点,产生一个0到1之间的随机数。 P114

他的名字被用于命名布达佩斯的阿尔弗雷德·雷尼数学研究院——匈牙利数学的温床。 P115

因此,给定参数N和p时,判定出所生成随机网络的期望链接数是有价值的。 P116

一般而言,二项分布用于描述有两个可能结果的N次独立实验中某个结果出现的次数。 P117

根据公式2.2,我们可以得到随机网络的平均度 也就是说,对于节点数为N的随机网络而言,其平均度/是节点对间存在链接的概率p和一个节点最多可能拥有的链接数(N-1)的乘积。 P118

这一节中,我们将推导出随机网络的度分布pk并讨论其性质。 P119

由于二者在描述同一个分布,它们有着相同的性质,只不过表述这些性质的参数不同:二项分布取决于p和N,而泊松分布只有一个参数/。 P120

/ 图2-5 度分布与网络大小无关平均度/=50,大小分别为N=102、N=103、N=104的三个随机网络的度分布。 P121

对于平均度/≈1 000的随机网络,其标准差为σk=31.62。 P122

要弄清楚前述结论和现实之间这些巨大差异产生的原因,我们需要对比真实网络的度分布和随机网络的度分布。 P123

2.6 随机网络的演化本章开始时介绍的鸡尾酒会刻画了这样一个动态过程:从N个孤立节点开始,链接逐个放置在随机相遇的客人之间。 P124

然而,如图2-7a所示,情况并非如此:当/比较小时,NG/N一直为0,意味着没有大的连通分支出现;一旦/超过临界值,NG/N开始迅速增加,标志着一个大的连通分支在快速形成,我们称该连通分支为巨连通分支。 P125

(b)~(e)示例随机网络及其在4种状态下的性质。 P126

实际上,此时最大连通分支的大小为NG~N2/3。 P127

这种状态发生时,网络的平均度取决于N(进阶阅读2.E): 注意,在刚进入连通状态时,网络仍然是相对稀疏的。 P128

当z<-3/2时,图中只有孤立节点和边;当z的取值超过-3/2时,图中开始出现3阶树;当z<-4/3时,4阶树出现了;当z=-1时,各阶的树都出现了,同时出现的还有各阶的环;4阶完全图在z=-2/3时出现,并且随着z的取值进一步增加,更高阶数的完全图开始出现。 P129

也就是说,如果一个普通人有超过23个相识的人,随机社会则仅由一个巨连通分支构成,没有孤立的人存在。 P130

如果说生活在同一个城市里的两个人彼此之间只相隔少数几个相识关系,你可能不会感到吃惊。 P131

因此,距离不可能取任意大的值。 P132

不过,公式2.19的预测并不完美:在下一章我们将看到,对于很多真实网络,公式2.19需要调整。 P133

三维(3D):对于立方体格子,有dmax~/~N1/3。 P134

公式2.20的估计可能比人们经常提到的“六度”更接近真实值(边栏2.7)。 P135

从中可以看出,有些信只经过了一个中间人,有些信则经过了多达10个中间人。 P136

测量结果表明,万维网的平均路径长度和万维网大小之间的关系为[21]: 1999年时,万维网大约有8亿个网页[22],根据上述公式可以计算出当时万维网的平均路径长度为/≈18.69。 P137

对于随机网络中的一个节点i,要计算其集聚系数Ci,我们需要估计出该节点的ki个邻居之间的链接数Li。 P138

注意,网络的平均集聚系数/也服从公式2.21。 P139

为了计算/和/,我们将有向网络视为无向网络。 P140

(b)每条链接以概率p重连到一个随机选择的节点。 P141

同样,在随机社会中,对一个美国学生而言,他的某个同学和中国工厂的某个工人成为他朋友的概率几乎相当。 P142

边栏2.11随机网络一览定义:N个节点,每对节点之间的连接概率是p。 P143

为此,我们可以使用随机网络模型作为指南:如果该性质在随机网络中存在,则意味着它可以由随机性解释。 P144

然而,在他们关于随机网络的8篇系列论文[2-9]中,这是唯一一次提到随机网络理论潜在应用价值的地方。 P145

(4)假如连接概率p=10-3固定不变,计算出只有一个连通分支存在时的网络大小Ncr。 P146

(2)计算网络的度分布。 P147

(1)如果红色节点和蓝色节点之间的距离为2,我们则称红色社区和蓝色社区是彼此交互的。 P148

该区域的面积大小可以使用度分布pk的累积分布P(k)表示为1-P(kmax),从而网络中最大节点满足: / 图2-17 最小度和最大度网络的期望最大度kmax满足度大于kmax的节点数不超过1的条件,kmax通常被称为度分布的自然上界。 P150

根据公式2.26和公式2.27,可以计算出kmax=1 185。 P151

由于u是不属于GC的节点比例,因此对于任何p和N,巨连通分支的大小可以通过求解方程 而得出,即NG=N(1-u)。 P152

虚线和紫色曲线的交点对应着公式2.32的解。 P153

当s较大时,指数项占主导地位,根据公式2.35可以预测,此时大的分支不存在。 P154

(d)N=104时,不同/对应的ps。 P155

N较大时的数值模拟结果也支持这些预测(图2-20)。 P156

[33](b)随机网络的平均分支大小。 P157

2.16 进阶阅读2.E 全连通状态为了确定大部分节点成为巨连通分支一部分时的/,我们计算出一个随机选择的节点和巨连通分支之间没有链接的概率,这里利用了NG≈N。 P158

对水进行冷却,到达零度时,水分子突然就停止了扩散运动,形成有序的晶体结构——冰。 P159

进一步降低T,m会收敛到1。 P160

修正项增加了网络直径,解释了这样一个事实:在d接近网络直径dmax时,节点数目的增加要比/d慢。 P161

这幅图展示的是在迈阿密艺术博物馆展出的一件作品,是这位艺术家在展现复杂网络方面的一个例子。 P165

万维网是目前为止人类建造出的最大网络,其所包含的网页数目估计超过了1万亿(N≈1012),比人脑中的神经元数目(N≈1011)还要多。 P168

/ 扫描二维码下载“湛庐阅读”App,回复书名,了解无标度性质是如何被发现的。 P169

本章所讨论的解析和实证结果,是本书剩余部分关于网络建模的基础。 P170

这是关于幂律分布的第一个有记载的报道[3]。 P171

例如,在图3-1中,我们有γin≈2.1和γout≈2.45。 P172

需要的时候,我们可以单独定义p0,用来表示没有链接的节点所占的比例。 P173

相比之下,连续形式中具有物理意义的只有p(k)的积分。 P174

我们发现:(1)当k比较小时,幂律分布在泊松分布之上。 P175

图中每个节点的大小和它的度成正比。 P176

对于无标度网络,根据公式3.12和公式3.16,可以得出自然截断为: 因此,网络越大,其最大枢纽节点的度就越大。 P177

如果度分布服从指数函数分布,根据公式3.17可以得出,在λ=1时网络的最大度应为kmax≈14。 P178

(b)随机网络看起来有点像全国高速公路网,节点是城市,链接表示主要的高速公路。 P179

在该极限情况下,公式3.20预测,/的值取决于n和γ的相互影响:(1)如果n-γ+1≤0,则公式3.20等号右边的第一项/会随着kmax的增加趋近于0。 P180

而对于幂律分布而言,其二阶矩是发散的,一个随机选择的节点的度可以和/相差非常大。 P181

此外,表中还列出了使用进阶阅读3.A中所讨论的方法估计出的度指数γ。 P182

由于演员网络的/和σ非常大,本图中省略了该网络。 P183

相比之下,如果我们要在波士顿和布达佩斯的路由器之间建立一个互联网链接,则需要在北美和欧洲之间铺设一条电缆,而这是非常昂贵的。 P184

从中可以看出,随机网络模型并不能很好地解释观察到的pk。 P185

一些网络的节点是分子,而另一些网络的节点是计算机。 P186

测量度指数在双对数坐标下,我们可以通过用直线去拟合pk,从而快速估计出幂律度分布的度指数。 P187

上图展示了几种碳的同素异形体(由碳元素组成但网络组织结构不同的材料)。 P188

所有节点相距都很近,因为这些节点都与同一个中心枢纽节点相连。 P189

总结来说,公式3.22表明:枢纽节点越明显,就越能有效地缩短节点间的距离。 P190

而对于大型网络(N=106)而言,pd和/会随着γ显著变化。 P191

然而,和预期相反的是,我们在一项试图将六度概念复制到在线世界的实验中发现:和最终未能到达目标的路径中的节点相比,那些最终到达目标的路径中的节点更不愿意和枢纽节点联系。 P192

这意味着当N足够大时,最大枢纽节点的度一定会超过网络节点总数。 P193

然而,并非所有的度序列都是可图化的:例如,如果度之和为奇数,则该序列不是可图化的(图3-14b)。 P194

例如,公式3.22表明,节点间的平均距离会收敛于从随机网络中推导出的小世界公式。 P195

因此,这类网络通常被称为具有预定义度序列的随机网络。 P196

我们首先计算函数 如图3-16b所示。 P197

(1)度为ki的节点和度为kj的节点之间有一条链接的概率为: 注意,一条链接具有两个“端”,具有L个链接的网络有2L个“端”。 P198

我们随机选择一个源节点(S1)和两个目标节点,其中第一个目标节点(T1)和源节点直接相连,而第二个目标节点(T2)与源节点不直接相连。 P199

每对节点相连的概率为: 图中给出了节点对(1,3)相连的概率以及节点对(3,4)相连的概率。 P200

最终生成的网络,其度分布为: 隐参数模型提供了一种非常简单的用于生成无标度网络的方式。 P201

● 一些重要的网络特性,包括聚集特性(第8章)和度相关性(第6章),在随机化过程中将会消失。 P202

如果网络是无标度的,则公式3.22才是正确的公式。 P203

综上所述,随机网络由于缺少枢纽节点而高估了节点间的距离。 P204

度分布服从幂律分布(公式3.1)的无标度网络是这一类别下最著名的例子。 P205

距离 3.10 课后习题习题1 枢纽节点对于表3-1列出的无向网络,计算其期望的最大度kmax。 P206

具体过程参考3.9节。 P207

实际上,很大的x值非常罕见,其出现的概率几乎为零。 P208

为了突出其交叉特性,我们对公式3.30取对数,得到: 当x/1/λ时,等式右边第二项起主要作用,意味着分布将服从指数为γ的幂律分布。 P209

一般而言,服从对数正态分布的变量是许多正的独立随机变量的乘积。 P210

在网络中,xmin通常对应着最小度kmin或者是能够保证最佳拟合的最小度。 P212

Nk可以通过直接测量得到,也可以从网络模型中计算得到。 P214

因此,我们通常会使用双对数坐标来绘制无标度网络的度分布。 P215

平缓区的出现会影响我们对于度指数γ的估计。 P216

掌握合适的工具可以帮助我们更好地探索真实网络的性质(边栏3.10)。 P217

可以看出,度分布对于所有的度都服从幂律分布。 P218

最重要的困难是,度指数所代表的标度并非在度分布的整个取值范围内都有效。 P219

(4)对kmin到kmax范围内的所有Kmin,重复步骤(1)~(3)。 P220

(c)M=10 000个生成数据集上得到的p(Dsynthetic),灰色线对应的是从引文网络中得到的Dreal值。 P223

一般而言,如果p>1%,模型可以被接受。 P224

子图:ksat=12时,D关于kcut的变化曲线,D在kcut=5 691处取值最小。 P227

在真实系统中,有很多原因会造成这种局部偏离,而这种偏离对系统的整体行为影响甚微。 P228

第一种是在(Kmin,∞)区域上用纯幂律分布拟合,第二种是用具有低度饱和和指数截断的幂律分布对整个数据集进行拟合。 P229

这位作曲家是这样解释音乐和网络之间的关系的:“6个不同长度和音程的枢纽节点分布在第二乐章和第三乐章。 P234

枢纽节点的存在以及与之紧密相关的无标度拓扑,向我们提出了两个基本问题:(1)万维网和细胞之间差异如此之大,为什么却具有相似的无标度网络结构呢?(2)为什么埃尔德什-雷尼的随机网络模型不能产生真实网络中出现的枢纽节点和幂律分布呢?第一个问题特别令人费解,这些性质、起源和范畴完全不同的系统都具有无标度特性:(1)细胞网络中的节点是蛋白质或代谢物,而万维网中的节点是储存信息的文档。 P237

为了弄清楚为什么如此不同的系统会最终形成类似的结构,我们首先需要理解无标度特性的产生机制,这正是本章的主题。 P238

如图所示,论文数量的增长带动了科学合作网络和引文网络的增长。 P239

/ 图4-2 偏好连接简史我们来考虑几个例子:● 在万维网数以万亿计的网页中,我们可能只知道其中很少的一部分。 P240

总之,随机网络和真实网络之间有两个重要的不同之处:1.生长真实网络是一个生长过程的结果,因此其节点数N会持续增加。 P241

[9]1.生长每个时间步,我们向网络中添加一个拥有m(≤m0)条链接的新节点,该节点会和网络中已经存在的m个节点相连。 P242

紫色表示线性分箱的pk,绿色表示对数分箱的pk。 P243

/:第一个节点只能和自己相连,形成一个自环。 P244

节点vi按照如下概率被选择: 也就是说,来自新节点vt的链接以概率ki/(2t-1)连接到节点vi,此时新链接对节点vt的度也做出了贡献。 P245

幂律分布和枢纽节点源于这两个机制引起的“富者愈富”现象。 P246

因此,在任意时刻,较早加入的节点会有更大的度。 P248

随着时间推移,每个节点获得链接的数目会越来越少。 P249

其中 因此,度分布服从度指数为γ=3的幂律分布,这和数值模拟的结果相吻合(图4-4和图4-7)。 P250

紫色直线的斜率为-3,对应着解析解预测的度指数γ=3。 P251

细胞细胞是40亿年进化的产物。 P252

具体而言,模型A从m0个节点开始,按照如下步骤演化:1.生长在每个时间步,我们添加一个拥有m条链接的新节点,使之与网络中已经存在的m个节点相连。 P253

实际上,当所有节点获得链接的概率相同时,我们缺少了“富者愈富”的过程,因此没有明显的“胜者”。 P254

在线性-对数坐标系下可以清晰地看出,该模型生成的网络具有指数度分布pk,这和公式4.18所预测的一致。 P256

假设节点i的度在这两个时间间隔内发生了变化,度的变化量记为?ki=ki(t+?t)-ki(t)。 P257

如果存在线性偏好连接,即Π(ki)=ki,我们有π(k)~k2。 P258

与假设1一致,我们在每个数据集中都发现了Π(k)与k的依赖关系。 P259

同时,亚线性偏好连接还会影响网络的最大度kmax。 P260

因此,只有当Π(k)严格线性依赖于节点的度k时,所得到的网络才具有纯粹的幂律度分布。 P261

当α→1时,指数截断的作用消失,度分布pk在很大的范围内服从幂律分布。 P262

在这个例子中,新节点选择了链接的右侧端点。 P263

公式4.27中,概率qk和k是线性关系。 P264

步骤(1)中选择到某个特定节点的概率是1/N。 P265

新节点i选择节点进行连接时,其成本函数[22]为: 成本函数需要考察网络中已经存在的每个节点j。 P266

因此,h0=0,h3=2。 P267

当δ<(1/2)1/2时,对于任意新节点都有δdij<1;根据公式4.28,新节点连接到中心节点的成本Ci=δdij+0,总是小于新节点连接到其他任何节点的成本f(i, j)=δdij+1。 P269

这次争论持续了两年,涉及7篇论文,是有记录以来最激烈的学术争论之一。 P270

对于巴拉巴西-阿尔伯特网络而言,当m>1并且N较大时,网络直径为[33],[34]: 因此,网络直径的增长要比lnN慢。 P271

因此,巴拉巴西-阿尔伯特网络中的集聚系数比随机网络中的集聚系数要高。 P272

巴拉巴西-阿尔伯特模型引发了一个基本问题:生长和偏好连接的组合是网络具有无标度特性的原因吗?关于这个问题,本节给出了一个充分且必要的论断。 P273

(1)在网络大小达到102,103,104的中间步骤,测量网络的度分布。 P275

请推导出模型A的度分布——公式4.18。 P276

接下来,我们把公式4.32应用于前面所述的(1)和(2)两种情况:(1)原来度为k、后来因获得一条新链接而变成度为(k+1)的节点数量为: (2)原来度为(k-1)、后来因获得一条新链接而变成度为k的节点数量为: 合并公式4.33和公式4.34,可得到增加新节点后度为k的节点的期望数量: 该公式适用于所有度k>m的节点。 P277

据此,我们可以把公式4.35和公式4.36的左侧写为:(N+1)pk(t+1)-Npk(t)→Npk(∞)+pk(∞)-Npk(∞)=pk(∞)=pk(N+1)pm(t+1)-Npm(t)→pm因此,速率方程4.35和4.36的形式为: 注意,通过变量替换k→k+1,公式4.37可以重写为: 使用递推方法可以求得度分布。 P278

● 公式4.11和4.41的前置因子和公式4.9的前置因子不同。 P279

严格来说,公式4.22所描述的稳定度分布只在α≤1时存在。 P280

由于0<α≤1,有 因此,当时间趋于无穷大时 这个常数的精确值我们稍后计算。 P281

当α→1时,度分布关于k的函数为k-3,和巴拉巴西-阿尔伯特模型一样。 P285

我们的目标是计算模型中三角形的期望数量,这个量和集聚系数密切相关(1.10节)。 P286

在MoMA首次展览立体主义和抽象艺术运动时,这幅作品出现在展览目录的封面上。 P292

然而,第三个进入市场的谷歌不仅很快成为领先的搜索引擎,还以令人难以置信的速度得到大量其他网站的链接,从而在2000年成为万维网中最大的枢纽节点[1]。 P294

该地区的核心位置树立着两座雕塑,以向其过往致敬,这两座雕塑分别是穿过纽扣的针和犹太裁缝。 P295

每个新节点按照广义偏好连接——公式5.1来选择与哪些节点相连。 P296

图中展示了在时刻ti=1 000, 3 000, 5 000时加入网络的节点的度随时间变化的情况。 P297

因此,适应性较高的节点,度增长较快。 P298

2.均匀分布的适应性更值得关注的是,节点适应性各不相同时该模型的表现。 P299

(b)在m=2、N=106、适应性η服从区间[0,1]上的均匀分布时,比安科尼-巴拉巴西模型所生成网络的实测度分布。 P300

巴拉巴西网络科学Network Science 计算机与互联网电子书 第2张

例如,在判断一个关于相扑运动的网页的适应性时:一小部分人觉得相扑很迷人,大多数人表示无所谓,甚至有些人觉得相扑很奇怪。 P301

虽然大部分节点(网页)的度在数据采集期间保持不变,还是有约6.5%的节点的度展现出了充分的变化,可以根据公式5.9来确定其幂指数。 P302

为了测量节点的适应性,首先需要精确刻画节点度的增长规律。 P303

我们使用公式5.13拟合一个期刊上每篇论文的引用记录,从而得到这个期刊的论文适应性分布(图5-5)。 P304

[11]总而言之,比安科尼-巴拉巴西模型提供的框架使我们可以据此确定每个节点的适应性,以及适应性分布ρ(η)的形状。 P305

根据公式5.15,人类基因组论文的最终影响力为13 105,而无标度论文的最终影响力为26 183。 P306

在玻色气体中,这对应着增加了一个新的能级ε6(虚线所示)和一个处于能级ε1的粒子——ε1为灰色节点1所在的能级。 P307

虽然最大适应性的节点不可避免地将成为最大度的枢纽节点,但在这一形态中的任何时候,度分布都服从幂律,表明所生成的网络具有无标度的拓扑。 P309

这一现象被称为玻色-爱因斯坦凝聚,由爱因斯坦在1924年首先提出。 P310

具体而言,对于给定的deg(ε),如果公式5.22没有非负解,玻色-爱因斯坦凝聚就会出现——粒子聚集在最低能级上。 P311

每个粒子对应网络中的一条链接,粒子处于该链接所指向节点的能级。 P312

(2)该模型断言度分布为幂律分布,而在真实系统中,我们观测到的度分布和严格的幂律分布之间存在系统性偏离,例如低度饱和和高度截断(边栏3.8)。 P313

曲线π(k)是使用第4.7节中所描述的方法测量得到的。 P314

高度节点(k/A)的度分布仍然服从幂律,因为初始吸引力对这些节点的连接概率改变很小。 P315

在巴拉巴西-阿尔伯特模型中,假如我们在每次新增一个节点后随机挑选n个节点对用于增加内部链接,则最终得到的网络的度指数为[22]: 因此,对任意n和m的组合,我们有γ≥3。 P316

根据r的取值不同,我们观察到三种不同的形态[25-30]:(1)无标度形态当r<1时,删除的节点数少于新增的节点数,因此网络持续增长。 P317

在这个模型中,网络按照公式5.23生长,同时以速率r删除节点[30]。 P318

这反映了“弱者愈弱”的现象,即拥有较少链接的公司更有可能失去链接。 P319

将公式5.30中的加速增长引入巴拉巴西-阿尔伯特模型中,所得网络的度指数为: 因此,加速增长使度指数超过γ=3,网络变得更同质化。 P320

在v→-∞的极端情况下,每个新节点都选择和最老的节点相连,形成中心辐射拓扑(图5-14a)。 P321

即使当v的取值不太大时,我们也可以观察到衰老的影响:当v逐渐接近1时,度指数发散(图5-14e)。 P322

本章讨论的例子使我们得出一个关键结论:想要理解网络的结构,首先需要掌握其动态演化过程。 P324

(5)高度截断许多真实网络中存在的节点删除和链接删除,可能导致度分布出现指数形式的高度截断。 P325

理解这些网络模型的性质需要借助于埃尔德什和雷尼建立的组合图论。 P326

每种建模方式在网络理论中都发挥着重要作用。 P327

(1)计算度指数及其与参数a的关系。 P328

要完成计算,我们还需要根据公式5.37确定C的值。 P330

为了得到累积分布函数(一个随机节点i的度小于或等于k的概率),我们有: 其中最后一个等式在t很大时近似成立。 P331

他们的婚礼(以及离婚)引发了不计其数的媒体报道,使八卦杂志卖出了数百万份。 P339

/ 图6-2 枢纽节点彼此不相连酵母的蛋白质相互作用网络。 P340

因此,度为k=56和k′=13的两个枢纽节点之间存在链接的概率是pk,k′=0.16,比一个度为2的节点连接到一个度为1的节点的概率p1,2=0.000 4高400倍。 P341

(d)(e)(f)度相关性矩阵eij,分别对应同配网络(d)、中性网络(e)和异配网络(f)。 P342

事实上,图a中的网络有大量链接存在于枢纽节点之间,也有大量链接存在于小度节点之间。 P343

eij包含了度相关性的所有信息,我们可以将其可视化,图6-3d、e、f展示了同配网络、中性网络和异配网络的eij。 P344

6.3 计算度相关性虽然eij包含了一个特定网络中度相关性的全部信息,我们却很难对其进行解读。 P345

● 中性网络对于中性网络,公式6.3~6.5断言 这允许我们将knn(k)改写为 因此,在中性网络中,一个节点的邻居的平均度独立于该节点的度k,只取决于网络的全局特征/和/。 P346

(a)科学合作网络knn(k)随k递增,表明网络的同配性。 P347

每个子图的水平线对应公式6.9的判断,绿色虚线是对公式6.10的拟合。 P348

事实上,拟合电网网络可得μ=0.04±0.05,这个值可以近似为零(图6-6b)。 P349

度相关性系数背后的假设是knn(k)以斜率r线性相关于k。 P350

如公式6.14所示,为了使网络保持中性,这两个节点之间需要有大约三条链接。 P352

换言之,网络中枢纽节点之间的链接数少于公式6.14的期望,因此这类网络将表现出异配性,我们称这一现象为结构性异配。 P353

(a)(b)如果生成的无标度网络具有图a中的幂律度分布,且没有自环和多重链接,则这个网络表现出结构性异配,如图b中的knn(k)所示。 P354

(e)(f)如果我们移除所有k≥ks/100的节点,从而设置高位截断(upper cutoff),如公式6.15所示,网络将变成图f所示的中性网络。 P355

多重链接的保度随机化(R-M):随机化过程中允许多重链接存在。 P356

随机化后,度相关性消失,因此互联网是同配的,但结构截断让大度节点没有这一趋势。 P357

绿色虚线为公式6.10的最优拟合,拟合区域如底部箭头所示。 P359

例如,图a给出了/相关性,即两个相邻节点的入度的相关性。 P360

● 生物网络蛋白质相互作用网络和代谢网络的μ都是负值,表明这些网络是异配网络。 P361

这种同配性或许也可以用来解释明星婚姻(图6-1)。 P362

演化网络的度相关性为了理解生长网络上度相关性的出现或消失,我们从初始吸引模型开始分析(5.5节)。 P363

总而言之,公式6.17~6.20表明初始吸引模型生成了比较复杂的度相关性,从异配性到弱同配性都有可能。 P364

橙色记号表示/,因为/也是递减的,所以观察到的异配性大体上是结构性异配。 P365

(b)对于一个无标度网络,N=1 000,L=2 500,γ=3.0,利用该算法生成网络的knn(k)。 P366

● 第1步:选择链接随机选择两条链接,记4个端点为a、b、c、d,且这4个端点的度满足ka≥kb≥kc≥kd● 第2步:重连删除选择的链接并重连,建立新的节点对。 P367

p=1的情况即为图6-13所示,产生了最大的度相关性。 P369

● 异配网络异配网络的相变点推迟了,这是因为枢纽节点倾向于连接小度节点。 P370

如图所示,当我们从异配网络转向同配网络,峰逐渐移向左侧,表明平均路径长度减短,同时直径dmax增长。 P371

上图中紫色节点分别展示了两个小网络中的最小点覆盖的示例。 P372

自由派博客之间的链接以蓝色表示,保守派博客之间的链接以红色表示。 P373

虽然已有很多工作尝试表征度相关性,但我们对于这一现象的理解仍未臻完善。 P375

假设N/1。 P376

(2)在一个小网络上,这两个概率的比值是多少?大网络呢?(3)如果使用埃尔德什-雷尼G(N, p)模型,(1)和(2)所讨论的物理量将会是怎样的?基于(1)~(3)的结果,讨论使用G(N, L)模型代替G(N, p)模型生成节点较少的随机网络时所带来的影响。 P377

右侧子图在双线性坐标下检验公式6.21的正确性,即“knn(k)与k呈线性关系”这一假设的正确性。 P378

因此,相关性系数r不能刻画大型网络的相关性。 P379

另外,我们也可以对这些有向网络计算有向相关性系数(边栏6.8)。 P380

若k>1,那么当μ>0时,括号项取正值,则r>0;同样,当μ<0时,括号项取负值,则r<0。 P381

形式上,我们有[14]: 其中α和β可分别表示入度(in)和出度(out),/指随机选一条链接其起点度为j的概率,/指随机选一条链接其终点度为k的概率。 P382

引文网络的相关性可以忽略,另外,手机通话网络的4个相关性系数表现出强同配性,代谢网络则表现出强异配性。 P383

我们首先定义 其中Ek,k′是度k节点和度k′节点之间链接数(k≠k′)或链接数的2倍(k=k′),且有 是Ek,k′可能取得的最大值。 P384

两组节点之间的链接总数不能超过:(a)k=3组可用的链接总数,即kNk=9。 P385

也就是说,任何时候只要度分布的截断低于这一限制,则一定满足条件rk,k′<1。 P386

美国、欧洲和印度很明显有着更密集的内部链接,同样明显的还有那些缺失链接的区域,例如缺少互联网接入的非洲。 P390

然而,很多自然和社会系统有一种出色的能力:即使它们的一些组成部分失效了,它们仍然能够维持基本功能。 P393

事实上,细胞的鲁棒性内嵌在一个复杂的、包含了调节机制、信息传导和新陈代谢的网络里;社会体系的自我复原力也和它背后错综复杂的,包含了社交关系、职业关系和通信关系的网络密不可分;如果不对那维系着每一个物种的食物链进行仔细分析,我们也无法理解生态系统作为一个整体的生命力。 P394

感谢吉奥尔吉·波什福伊(Gy?rgy Pósfai)提供图片。 P395

虽然移除第一个节点只对网络完整性产生有限的影响,但移除第二个节点就让2个小簇脱离网络其余部分。 P396

/ 图7-4 渗流渗流理论里一个经典的问题——在方形网格上以概率p随机放置石子。 P397

● 关联长度:ξ属于同一簇的两颗石子之间的平均距离,它遵循: 因此,当p<pc时,同一簇石子之间的距离是有限的。 P398

● 和临界值pc不同,临界指数不依赖于网格类型,只依赖于网格的维度。 P399

这个规模可以被概率P∞刻画,这一概率即是随机选取一个节点,这个节点属于巨大连通分支的概率。 P400

序参量P∞(一个节点属于巨连通分支的概率)对f的依赖关系说明了这一点(图7-5):当f<fc时,P∞>0;但当f≥fc时,P∞=0。 P401

网络中的最大连通分支用黑色表示。 P402

渗流理论告诉我门,一旦被移除的节点的数量达到一个阈值fc时,互联网会分解成许多不相连的子网络(图7-5)。 P403

模拟中使用的是路由器层面的互联网拓扑结构,如表3-1所示。 P404

正如短片表现的,即使移除了相当大一部分的节点,网络也并没有被裂解。 P405

莫洛伊-里德准则(公式7.4)利用了这个属性,使我们可以计算网络分解时的临界点。 P406

我们用公式7.7来计算随机网络分解的阈值。 P407

然而,当γ<3时,我们有fc→1。 P408

让我们回到图3-6中的机场比喻,如果随机选择一个机场,然后关闭它,我们关闭的很可能是众多小机场中的某一个。 P409

表7-1 在随机故障和蓄意攻击下的网络分解阈值/ 该表显示了在随机节点故障(第二列)和攻击(第四列)下,10个参照网络上的fc的估计值。 P410

如图所示,网络在同一个临界值fc≈0.5上被裂解,不同的是这两条曲线的形状。 P411

移除单一枢纽节点是不可能分解一个网络的,因为网络中剩余的枢纽节点仍然可以将网络连接在一起。 P412

故障是随机选择节点,顺序与节点的度无关。 P413

● 在随机故障中,临界值fc随γ的增加而单调减小。 P414

移除可以是随机移除(绿色),或者按照节点的度降序移除(紫色)。 P415

因此,即使它的一些节点发生故障,还有其他路径将剩下的节点连接起来。 P416

因此,多米诺效应也许是能说明本节主题级联故障的最简单的例子。 P417

当电网中某个组件超过了运行限制时,它就会自动从网络中断开以自我保护。 P418

● 信息的级联传播从电子邮件到社交网站,现代通信系统使信息可以沿着社交网络的链接进行级联式的传播。 P419

不同国家的指数列在了表7-2中。 P420

地震的振幅在横坐标上用s的对数表示,s是检测到的地震波的振幅。 P421

表7-2 真实网络中的雪崩指数/ 各种级联的幂律分布(公式7.14)的雪崩指数,包括各个国家在停电中的电量损失[18]、Twitter上的信息传播[19]、地震的规模[20]。 P422

拥堵机场构成的簇表明,航班延误并非彼此独立,而是呈现出航空网络上的级联现象。 P423

参与的形式可能是发生故障(比如电网、地震)或者选择传播某一条信息(比如Twitter)。 P424

最初所有节点都处于状态0,用绿色圆圈表示。 P425

分支模型故障传播模型的复杂性使其很难用于分析级联的标度。 P426

/ 图7-21 分支模型(a)此图用分支过程来表述图7-20a、b所示的故障传播。 P427

随机游走理论对这个问题已有不少研究,指出返回时间服从指数为3/2的幂律分布[32]。 P428

7.7 构筑鲁棒性能否提高一个网络的鲁棒性?在这一节中,我们将讨论影响鲁棒性的因素,从而设计能同时抵御随机故障和攻击的网络。 P429

同时,以/度量的成本也升高了。 P430

也就是说,只有一个节点的度为kmax,其他所有节点的度都为kmin。 P431

左侧子图展示了N=300时网络的拓扑结构,右侧子图是N=10 000时的故障/攻击曲线。 P432

例如,限于监管、资金和法律的阻碍,在电网中建设新的输电线可能需要20年。 P433

这样的指数分布的pk通常出现在网络生长时没有偏好连接机制的情况下(4.6节)。 P434

(b)~(d)这三幅图描述的是,意大利电网及其发电和用电的具体情况。 P435

[40]我们通过分析从电网故障中收集和报告的以下量化数据来讨论鲁棒性和可靠性之间的关系:(1)未能供给的能量;(2)总共损失的电力;(3)平均中断的供电时间,即每年中断供电的分钟数。 P436

韧性如果一个系统可以改变自身的运行模式来适应内部和外部的错误,且仍能执行其功能,那么这个系统就具有韧性。 P437

然而,对网络鲁棒性的解析依赖于渗流理论。 P438

度分布的函数形式、一阶矩、二阶矩请参照表3-2,讨论所得的结果对网络鲁棒性的影响。 P440

假设每个节点上都有一个桶,每个桶至多可以承载和该节点的度一样多的沙粒。 P441

在pc附近,描述平均连通分支规模的临界指数符合下面的公式[48]: 我们可能对γp在γ<3时是负数感到惊讶。 P442

在3<γ<4的区域内,这也是成立的,尽管这一阶段的渗流相变发生在阈值fc介于0和1之间时。 P443

对于一个度分布为pk的网络,当不存在度相关性时,我们有: 这表明节点i可以从N-1个节点中以概率1/(N-1)任意选择一个连接,这个过程重复ki次。 P444

如果随机移除占比f的节点,会产生两个后果:● 它改变了一些节点的度,这是因为之前与被移除节点相连的节点失去了它们的链接[k→k’≤k]。 P445

之所以能够这样做,是因为两次都是在图中紫色三角形区域中求和。 P446

fc的估计值对应网络巨连通分支的占比首次低于其原始规模的1%的时候。 P453

在不存在度相关性时,我们假定被移除的枢纽节点的链接是随机连到网络中其他节点的。 P454

一般情况下,余下网络的度分布为: 注意,我们在进阶阅读7.C中已经推导出了这个度分布7.32。 P455

这种网络的拓扑结构可以同时优化网络面对攻击和故障时的鲁棒性[37]。 P456

在这种情况下,所有的枢纽节点都被移除。 P457

在这种情况下,决定中央枢纽节点的度kmax的最优值的方程如下[37]: 这里的A如公式7.67所定义。 P458

[1]这也是本章的主题。 P463

他们发明了一种算法来识别这个国家的社区结构。 P466

社交网络研究人员在几十年前就已注意到,很容易在社交网络中找到社区[3-7]。 P467

圆圈和方块表示俱乐部一分为二后出现的两部分。 P468

每个节点的颜色表示其主要从属的生化分类。 P469

社区存在的根源是谁与谁相连,不能仅用度分布来解释。 P470

因此,如果网络中有两个不相连的分支,则每个社区只能存在于一个分支内。 P471

图中还有一些强社区,你能再找到至少两个吗?(c)弱社区公式8.2中定义的弱社区是一个子图,其节点的总内部度高于总外部度。 P473

并行计算也遇到了类似的问题,如何把大型计算任务划分成子任务并分配给各个芯片。 P474

在这种情况下,公式8.4变成: 表明图二划分的数目随着网络大小呈指数级增长。 P475

图中比较了贝尔数和指数函数,可能的划分数量的增长速度高于指数级增长。 P476

例如,如果运行时间正比于N的算法在N=100个元素上耗时1秒,那么N3算法在同一台计算机上耗时约3小时。 P477

总而言之,我们的社区概念来源于这样一种预期:每个社区都对应一个局部紧密连接的子图。 P478

对于每对节点i和j,根据公式8.7计算其拓扑重叠。 P479

劳沃斯算法使用平均簇相似度定义两个社区之间的相似度,其为分处两个社区的所有节点对i和j的xij的平均值(图8-10d)。 P480

(3)计算新的社区与其他所有社区的相似度。 P481

该算法包括步骤。 P482

事实上,社区之间的每一条最短路径都需要经过这些链接。 P483

真实网络的层次结构层次聚类提出了两个基础问题。 P484

注意对角线上的节点也是相连的,只不过链接没有画出。 P485

/ 图8-14 层次网络的标度图8-14表示了层次网络的三个特征量。 P486

事实上,小度节点的C较大是因为它们处于密集的社区中。 P487

虽然对于小网络,我们可以读图判断哪种分割最优地刻画了潜在的社区结构,但对于大型网络却完全做不到。 P488

若Mc为零,那么这Nc个节点之间的连接是随机的,可以由度分布完全解释。 P489

模块度较低的另一种划分则明显与真实社区有所差异(图8-16b)。 P490

(a)最优划分模块度最大的划分,M=0.41与两个社区吻合。 P491

检查所有这样的两个社区,找到ΔM最大的一对,合并它们。 P492

因为算法需要N-1次社区合并,其复杂度为O[(L+N)N],在稀疏图上为O(N2)。 P493

若A和B是完全不相连的社区,那么最大化M后,它们依旧分属不同社区。 P494

考虑一个网络有nc个子图,链接密度kc≈2L/nc。 P495

这一划分的模块度为M=0.867。 P496

因此,并没有一个明确的模块度最大值。 P497

[36]尽管社会学家和对社区工程感兴趣的人对嵌套社区结构认识已久[47],目前我们讨论的算法也要求每个节点属于单一社区。 P498

(c)k=3的团构成的社区此图描述的是绿色社区添加了最后一个三角形之后,算法的暂时结果。 P499

/ 图8-21 重叠社区南佛罗里达词联想网络中包含单词bright的社区。 P500

(a)次临界社区3-团(三角形)渗流阈值为pc(3)=0.16,则p=0.13小于该阈值。 P501

因此,要解释网络的重叠社区结构,我们必须将其与原网络度随机化后的社区结构相比较。 P502

综合起来,对于图8-23e所示的网络,公式8.17给出了图8-23d中所示的相似度矩阵。 P503

任何熟悉这部小说的读者都可以确认,这些社区准确地表达了每个人物的身份。 P504

与之类似,我们可以像8.4节讨论的模块度函数一样推导出链接聚类的评价函数[52]。 P505

(a)节点颜色表示在公式8.18所定义的混合参数μ=0.40时劳沃斯算法给出的划分。 P507

余下的μki个半链接随机连接到其他社区的节点。 P508

图8-27展示了在GN和LFR基准网络上使用In检验每种算法性能的结果。 P509

因此,我们列出的计算复杂度只关于N。 P510

8.7 刻画社区特征网络科学研究的驱动力是量化探索网络的基础原理,这些基础原理决定了网络是如何生成和组织的。 P511

在蛋白质相互作用(图a)和科学合作网络(图b)上,所有算法都给出近似重尾的社区大小分布,因此这些结果多多少少相互一致。 P513

这里只显示距离图a中黑色圆圈高亮的用户6步或6步以内的节点。 P514

[50]增长随着一个节点与某个社区的成员之间的链接增多,该节点加入该社区的概率也随之增大[73]。 P517

然而,算法的易用性和对其结果的解释要求我们关注算法基于的假设。 P518

其中模块度由下式定义: 所有节点都必须属于社区吗?社区识别算法要求所有节点都属于社区。 P519

每个社区以不同颜色表示。 P520

红色链接表示午夜前后有很多通话,白色或缺失链接表示用户在午夜时段很少通话或者完全不通话。 P521

将这个环划分成nc个连续的簇,每个簇的大小为Nc=N/nc。 P523

(2)证明只有当nc<2L时,最大模块度才能给出符合直观的正确社区划分,其中: (3)讨论上述不等式不成立的情况。 P524

复制后的中心节点仍然称为枢纽节点,复制后的外围节点仍然称为外围节点(图8-35)。 P525

我们同时展示了每个网络保度随机化之后的C(k)(绿色记号),并观测到了以下现象:● k较小时,所有网络的C(k)都比随机化网络的C(k)高一个量级。 P528

综合起来,图8-36表明大多数真实网络有非同小可的层次模块度。 P529

保度随机化抹平了局部密度的差异,因此社区和底层的层次结构都会消失。 P531

因此,我们的半链接连接到模块内的另一个半链接的可能性为/。 P532

因此这些算法并不一定是最快的,也不一定是最准确的。 P533

步骤I通过局部改变来优化模块度。 P534

本例中B是一个不连通节点。 P535

换言之,我们希望以最少个数的符号来描述轨迹。 P536

寻找映射方程的最小值以找到最优编码: 简而言之,公式8.45的第一项给出了描述社区间移动所需的平均比特数,其中q是随机游走者在某一步切换社区的概率。 P537

计算复杂度Infomap算法的计算复杂度取决于最小化映射方程L的程序。 P538

网络中5个k=3的团全部被高亮显示。 P539

因此,簇的大小会呈指数级衰减。 P540

第二天,在离开酒店后,他前往广东当地一家医院就诊,并在数日后因“非典”去世[1]。 P550

我们还需要理解病原体是如何在人群中进行传播的,从而反过来决定我们如何管理可用的治疗手段和相应的疫苗。 P551

这里的移动网络是指通过人群流动将不同空间位置之间连接起来形成的网络(详见9.4节)。 P552

最简单的划分方式假设每个个体都处于以下三种阶段之一:● 易感染(S):尚未接触病原体的健康个体(图9-3)。 P553

图中展示了几种研究较多的病原体,例如人体免疫缺陷(艾滋病)病毒、流感病毒和丙型肝炎病毒。 P554

单向箭头表示一旦一个个体被感染,它将一直处于已感染阶段,不可康复。 P555

● 易感染个体占比为原来的1/e(约36%)所需的特征时间(characteristic time)为: 在这里,τ是病原体在人群中传播速度的倒数。 P557

已感染个体在接受治疗后以速率μ变成易感染状态。 P558

不同的是,最终并不是所有人都会被感染,而是常数值i(∞)<1的人口比例被感染(图9-5b)。 P559

R0越高,传播过程越快。 P560

他们不会再被感染,也不会再感染别人,因此不应再计入任何阶段。 P561

这三种模型的差异主要在于对传染病后期过程的刻画:SI模型中所有个体最终都将被感染;SIS模型中流行病最终将会到达“地方病”平衡点(已感染人口长期处于有限占比),或者逐渐消亡;SIR模型中所有个体最终都会康复。 P562

9.3 网络上的流行病模型便利的航空旅行每天让数以百万计的乘客在各大洲之间穿行。 P563

由此产生的破坏引发了一系列宗教、社会和经济动荡,对欧洲历史具有巨大的影响。 P564

但此外,也存在着一些关键的差异:● 公式9.3中的平均度/被替换为每个节点真实的度。 P565

事实上,在任意时间t,我们可以将公式9.17写成ik=g(t)+kf(t)。 P566

图中展示了平均度/=2的埃尔德什-雷尼网络中度为1、10、20的节点中的已感染节点占比。 P567

一旦一个枢纽节点被感染,它就成了一个超级传播者,把病原体传播到网络的其余部分。 P568

τ和λc的推导过程见进阶阅读9.B。 P569

绿色曲线表示随机网络,紫色曲线表示无标度网络。 P570

这是关于网络上的流行病的第二个基本结论。 P571

结果表明,只有在γ>4时,无标度网络上的流行病传播才会收敛到传统流行病模型的结果。 P572

这一发现在之后英国、美国和南非的数据中也得到了验证[17]。 P573

数字表示同样结构的子图的个数:有63对情侣与这个网络的其他部分不相连。 P574

这一带权网络中的节点是N=3 100个最大的机场,还有L=17 182条表示直飞航线的链接,涵盖了全世界99%的航空运输。 P575

采集射频识别信号的场合决定了利用标签获得的结构。 P576

为了使研究更有效,研究人员同时还应该扩大范围,获得更多种类的数据,例如使用基于移动手机的检测[36]。 P577

其余的网络,例如共同位置网络,虽然它们的度分布并不能用简单的幂律拟合,但依然表现出了显著的度异质性——/较高。 P578

忽略交互的时间性可能导致具有误导性的结论[39-41]。 P579

因此接触模式在时间轴上具有非均匀的阵发特性(图9-18d、e)。 P580

然而,真实情况下的衰减会慢很多,衰减时间为τ≈21天,这与我们使用幂律间隔分布理论的预测相吻合[43]。 P581

事实上,如第8章所讨论的,强链接倾向于出现在社区内部,而弱链接倾向于出现在社区之间[50]。 P582

(a)已感染节点占比随时间变化的函数。 P583

思想、行为等个体间的文化传播进一步凸显了社区的重要作用[54]。 P584

社区颜色代表所关注的主题标签(模因)最早在这个社区内出现的时间:首先使用该主题标签的社区是浅色,较晚使用的社区是深色。 P585

肥胖可以通过个体的体重指数(BMI)来判断,取决于基因、饮食、锻炼等多种因素。 P586

每个节点代表一个个体:蓝色表示男性,红色表示女性。 P587

为了说明这一效果,让我们考虑从总人口中随机选择g比例的个体免疫的情况[8]。 P588

与之类似,避孕套降低了性传播病原体的传播率。 P589

令公式9.27中的λ=1可得gc=0.76。 P590

越多枢纽节点得到免疫(/越小),λc越大,越可能让这一疾病消亡。 P591

例如,我们要求第0组中的每个人指出一个可能会相互传播病原体的朋友。 P592

一般而言,若病原体在异质网络中传播,则随机免疫是低效的:需要找到并免疫接近100%的易感染节点才能让随机免疫策略完全起效,而这在大多数场景下是不可能的。 P593

其发展基础来自20世纪80年代的传染病模型框架[72]和2003年非典型性肺炎大暴发。 P594

基于网络科学的流行病实时预测的首个成功案例,并且得益于全球疾病传播和移动(Global Epidemic and Mobility,简称GLEAM)计算模型[80](图9-26,在线资源9.5),这一随机框架将全世界范围的高精度人口数据和移动数据作为输入,采用了基于网络的计算模型:/ 图9-26 建模2009年H1N1甲型流感传播(a)H1N1甲型流感病毒在2009年暴发期早期的传播。 P595

[82]/ 在线资源9.5 GLEAM介绍流行病预测软件包GLEAM的视频。 P596

剩下的国家中,观测的高峰期和预测的高峰期最多相差两星期。 P597

因此在实施航空禁令之前,我们必须确认限制旅行确实有助于控制疫情。 P598

在减少90%旅行的情况下,最长的延迟不超过20天。 P599

有效距离在汽车和飞机发明之前,病原体以步行速度,或最多以马车的速度进行传播。 P600

/ 图9-31 有效距离始发于中国香港的疫情传播。 P601

到达时间是指2009年3月17日疫情暴发后,每个国家的第一个确诊病例的日期。 P602

观察到的这一传播模式给我们提出了一个问题:一个典型的病原体在全球传播的速度是怎样的呢?速度取决于3个关键参数:(1)基本再生数R0。 P603

由于全世界范围内的移动模式是唯一的且与模型无关,因此不同模型的预测结果也几乎一致——与其各自选取的流行病学参数无关。 P604

与之相反,若随机选择节点进行监控,则需要监控41%的节点才能达到同样的正确率[93]。 P605

而由于大多数接触网络都是异质网络,这是一个相当令人沮丧的结论。 P607

维斯皮那尼和他的研究组开发了可用于实时预测病原体传播的计算框架GLEAM。 P608

一个度为k的节点有多少个肥胖的二阶邻居?若肥胖比例上升到70%,(1)和(2)的答案分别是多少?习题3 免疫从表3-1中选择4个网络(有向网络的度分布按照无向和不相关网络类似计算pk=/),考虑其上的流行病传播过程。 P609

将公式9.33中的ki替换成/,可以得到连续性方程9.3中的第一项。 P610

如9.3节所述,要计算ik首先需要计算Θk。 P611

由于上式括号中的ik和rk在t较小时远远小于1,因此可以忽略。 P613

对于SI和SIR模型,若一个节点被感染,则它至少有一个邻居处于已感染或已康复状态。 P614

在9.3节中,我们得到了临界传播率 和 免疫枢纽节点即为免疫所有度大于k0的节点。 P616

这种映射为我们预测模型的行为提供了一套分析工具。 P618

相应地,该链接被删除的概率为e-β/μ。 P619

这场运动的核心可以通过所有权网络来刻画,该网络由艺术家、律师、激进分子和记者联盟提供,描绘了伊斯坦布尔政商两界精英背后复杂的财务关系。 P629

在选择本书的主题和表述方式时,我力求提供一种定量的、容易理解的方式,使读者能够在愉悦的阅读体验中了解网络科学。 P631

为此,我们收集了10个经常在网络科学的文献中被使用的网络,来讲述和验证本书介绍的许多网络性质。 P632

课后作业在那次较长的课程中,我从每个章节后面列出的问题中选择一部分作为课后作业,测验学生对课程内容掌握的熟练程度以及解决问题的能力。 P633

根据学生们标记后的列表,我们便可以构造出学生之间的社会网络,每个节点还可以标记上学生性别和选课情况。 P635

(4)课程结束时,要求学生们介绍各自的课程设计结果。 P636

这样的询问和答疑,可以帮助学生评估他们各自的选择是否合适,帮助他们更清晰地理解自己的一些想法,帮助他们找到具有共同兴趣的课程设计搭档。 P638

撰写这本书几乎占用了我2011年至2015年之间的所有闲暇时间。 P641

他为每个章节设计了章首页,他设计的很多视觉元素贯穿全书。 P642

文字工作:录入和编辑我是一个传统的作家,在写作时不使用计算机,而是用铅笔来完成。 P643

作为我实验室里的一名研究人员,罗伯塔和我一起讲授了2014年秋季的网络科学课程,在教学过程中,她帮助我指出并修正了课件中的许多拼写错误。 P644

在出版过程中,罗欣·芒内利(Róisín Munnelly)也提供了大量帮助。 P645

作者巴拉巴西第一个证明了,我们不是生活在随机世界里,真实网络是无标度的。 P649

◎ 《爆发》一书揭开了人类行为背后隐藏的模式“爆发”,提出人类日常行为模式不是随机的,而是具有“爆发性”的。 P650

good

标签