第1章 概述 1
1.1 为什么对网络产生兴趣 1
1.2 几个网络示例 2
1.3 网络的性质 5
1.4 本书结构 7
第Ⅰ部分 网络的实证研究 10
第2章 技术网络 10
2.1 Internet 10
2.2 电话网络 16
2.3 电力网络 18
2.4 交通网络 19
2.5 配送网络 19
第3章 社会网络 21
3.1 社会网络实证研究 21
3.2 采访与问卷 23
3.3 直接观察 27
3.4 来自于档案或第三方的数据 28
3.5 隶属网络 31
3.6 小世界实验 32
3.7 雪球式抽样、接触者追踪及随机游走 35
第4章 信息网络 38
4.1 万维网 38
4.2 引文网络 41
4.3 其他类型的信息网络 44
第5章 生物网络 48
5.1 生物化学网络 48
5.2 神经网络 58
5.3 生态网络 61
第Ⅱ部分 网络理论基础 66
第6章 网络的数学基础 66
6.1 网络及其表示方法 66
6.2 邻接矩阵 67
6.3 加权网络 68
6.4 有向网络 69
6.5 超图 75
6.6 二分网络 76
6.7 树 78
6.8 平面网络 80
6.9 度 82
6.10 路径 84
6.11 分支 88
6.12 独立路径、连通度和割集 91
6.13 图拉普拉斯矩阵 95
6.14 随机游走 99
习题 103
第7章 测度与参数 106
7.1 度中心性 106
7.2 特征向量中心性 106
7.3 Katz中心性 109
7.4 PageRank 110
7.5 核心顶点与权威顶点 113
7.6 接近度中心性 115
7.7 介数中心性 117
7.8 顶点群组 123
7.9 传递性 126
7.10 相互性 130
7.11 有符号边和结构平衡 131
7.12 相似性 135
7.13 同质性和同配混合 141
习题 149
第8章 网络的大规模结构 152
8.1 分支 152
8.2 最短路径和小世界效应 155
8.3 度分布 157
8.4 幂律和无标度网络 159
8.5 其他中心性测度的分布 168
8.6 聚类系数 169
8.7 同配混合 172
习题 173
第Ⅲ部分 计算机算法 176
第9章 算法基本概念 176
9.1 运行时间和计算复杂度 177
9.2 网络数据的存储 180
9.3 邻接矩阵 180
9.4 邻接表 182
9.5 树 185
9.6 网络的其他表示方法 190
9.7 堆 192
习题 195
第10章 网络基础算法 196
10.1 度和度分布的算法 196
10.2 聚类系数 197
10.3 最短路径和广度优先搜索 200
10.4 加权网络中的最短路径 209
10.5 最大流和最小割 211
习题 217
第11章 矩阵算法与图划分 219
11.1 主特征向量和特征向量中心性 219
11.2 将网络划分成簇 224
11.3 图划分 227
11.4 Kernighan-Lin算法 228
11.5 谱划分 231
11.6 社团发现 235
11.7 简单模块度最大化 236
11.8 谱模块度最大化 238
11.9 将网络划分为两个以上群组 240
11.10 其他模块度最大化方法 241
11.11 社团发现的其他算法 242
习题 247
第Ⅳ部分 网络模型 250
第12章 随机图 250
12.1 随机图 250
12.2 边数和度的均值 252
12.3 度分布 252
12.4 聚类系数 253
12.5 巨分支 253
12.6 小分支 257
12.7 路径长度 265
12.8 随机图的问题 267
习题 268
第13章 任意度分布的随机图 270
13.1 生成函数 270
13.2 配置模型 274
13.3 余度分布 281
13.4 聚类系数 283
13.5 度分布的生成函数 284
13.6 一个顶点的两跳邻居顶点数量 285
13.7 小分支的生成函数 288
13.8 巨分支 290
13.9 小分支的规模分布 293
13.10 幂律度分布 297
13.11 有向随机图 299
习题 305
第14章 网络生成模型 307
14.1 优先连接模型 307
14.2 Barabási-Albert模型 316
14.3 优先连接模型的其他性质 318
14.4 优先连接模型的扩展 325
14.5 顶点复制模型 339
14.6 网络优化模型 343
习题 348
第15章 其他网络模型 351
15.1 小世界模型 351
15.2 指数随机图模型 360
习题 374
第Ⅴ部分 网络过程 376
第16章 渗流和网络弹性 376
16.1 渗流 376
16.2 顶点的均匀随机删除 378
16.3 顶点的非均匀删除 388
16.4 实际网络中的渗流 392
16.5 渗流的计算机算法 393
习题 398
第17章 传染病的网络模型 400
17.1 疾病传播模型 400
17.2 SI模型 400
17.3 SIR模型 403
17.4 SIS模型 406
17.5 SIRS模型 407
17.6 传染病的网络模型 408
17.7 传染病网络模型的晚期特征 409
17.8 SIR模型的晚期特征 410
17.9 传染病网络模型的时间依赖特性 414
17.10 SI模型的时间依赖特性 414
17.11 SIR模型的时间依赖特性 423
17.12 SIS模型的时间依赖特性 428
习题 431
第18章 网络动力系统 433
18.1 动力系统 433
18.2 网络动力学 440
18.3 多变量动力学 446
习题 450
第19章 网络搜索 453
19.1 Web搜索 453
19.2 分布式数据库搜索 455
19.3 消息传递 457
习题 464
参考文献 466
索引 482