复杂网络导论
Jan 10, 2026·
·
31 min read
Dison Tsui
——————————————————————————————————————————————
复杂网络系统笔记
——————————————————————————————————————————————
Tsui Dik Sang
2024 年 9 月 8 日——2026 年 2 月 9 日
写在笔记之前
作为一门导论课，仍然是非常满满当当的的，仅凭一个学期根本不可能吃透，不过考前的速通也还是有点效果的！
Tsui Dik Sang
2025 年 6 月 30 日
2
目录
第一章 基础 6
1.1 基础概念 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.1 定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.1.1 基本定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.2 按边的分类 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.2.1 连通与路径 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.3 图的运算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.3.1 子图 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.3.2 图的并 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.3.3 图的交 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.3.4 图的差 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.3.5 收缩图 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.4 图的表示 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.4.1 邻接矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.4.2 关联矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.1.4.3 可达矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2 拓扑结构与静态特征 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.1 静态特征 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.1.1 表征距离 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.1.2 表征集聚程度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.1.3 度：重要程度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.2
无向网络的静态特征
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2.2.1 度-度相关性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2.2.2 介数和核度：缺损重要程度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2.2.3 网络密度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
第二章 机制模型 16
2.1 网络机制模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.1 规则网络 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.1.1 全局耦合网络 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.1.2 最近邻耦合网络 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.1.3 星型网络 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.2 随机网络 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.2.1 连接 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.2.2 基础参数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1.3 小世界网络模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3
复杂网络基础理论笔记 目录 Tsui Dik Sang
2.1.3.1 WS 模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.1.3.2 NW 模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.1.3.3 参数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.1.4 无标度网络 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1.4.1 Price 模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1.4.2 BA 模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1.5 层次网络 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 传播动力学 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.1 流行病模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.1.1 SI 模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.1.2 SIS 模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.1.3 SIRS 模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.1.4 SEIR 模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.1.5 在均匀网络中的传播 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.1.6 非均匀网络中的传播 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.1.7 社团上的传播：对应层次网络 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.2 舆论传播 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.2.1 基于 SIR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.2.2 Cowan 模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.2.3 Cobb-Douglas 模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.3 拥塞控制 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.3.1 数据包传递模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.3.2 路由策略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.3.3 拥塞控制策略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
第三章 搜索 25
3.1 搜索 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.1.1 广度优先搜索 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.1.2 随机行走搜索 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.1.2.1
基本假设
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.1.2.2 理论分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.1.2.3 在不同网络中的验证 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.1.3 最大度搜索算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.1.3.1 基本前提建模 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.1.3.2 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.1.4 社会网络的分散式搜索 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.1.4.1 Kleinberg 模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.1.5 Internet 中的搜索 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.1.5.1 P2P 网络 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.1.5.2 广播方式的 Gnutella 搜索 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.1.5.3 PageRank 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2 挖掘 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2.1 重要节点指标 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2.1.1 网络整体性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2.1.2 基于节点删除 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2.2 合理性评判指标 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4
复杂网络基础理论笔记 目录 Tsui Dik Sang
3.2.3 常用挖掘方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.3.1 基于节点关联性的方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.3.2 基于最短路径法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.3.3 基于模拟流的方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.3.4 节点收缩法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2.3.5 过载函数法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2.3.6 权值降低法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2.4 社团结构挖掘 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2.4.1 基本定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2.4.2 模块化 Q 函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2.4.3 经典检验网络 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.4.4 社团划分结果评价 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
第四章 笔记结束 35
5
第一章 基础
1.1 基础概念
1.1.1 定义
速速过定义！图包含两个要素
1.1.1.1 基本定义
定义 1.1.1 (图). 定义为一个三元组
G(V, E, ψ) (1.1)
其中 V 为节点集，E 为边集，ψ 为关联函数, 可以理解为一个边到节点的映射。
给一个示例来说说具体的如何表示
G(V, E, ψ)
V = {v
1
, v
2
, v
3
, v
4
}
E = {e
1
, e
2
, e
3
, e
4
, e
5
}
ψ(e
1
) = {v
1
, v
2
}
· · ·
ψ(e
5
) = {v
3
, v
4
}
(1.2)
还有二元组表示，则 E 集合就直接用两个节点表示一个边。
下面将会有很多纷繁复杂的定义，意义不大，都是为了后面章节阐述的时候省下一点笔墨
1.1.2 按边的分类
定义 1.1.2 (图的分类). -
• 无向图：边没有方向
• 有向图：边有方向
• 简单图：无向图且没有自环和重边
• 加权图：边有权值
• 完全图：任意两个节点间都有边相
6
复杂网络基础理论笔记 第一章 基础 Tsui Dik Sang
• 零图：没有边的图
• 平凡图：只有一个节点的图
•
1.1.2.1 连通与路径
定义 1.1.3 (简单路径/行迹). 在图 G = (V, E, ψ) 中，若节点序列 v
1
, v
2
, · · · , v
k
和边序列 e
1
, e
2
, · · · , e
k−1
满足找到一条路径
其所遍历的边互不相同，则称该路径为简单路径/行迹。
定义 1.1.4 (基本路径). 如果路径经历的节点互不相同，则称该路径为基本路径。
推论 1.1.1 (简单路径与基本路径的关系). 图 G 中的每一条基本路径都是简单路径，但反之不然。
定义 1.1.5 (割点). 设 G = (V, E, ψ) 为一个连通图，若去掉节点 v ∈ V 及其所有关联边后，所得的图不连通或者分支数有所
增加，则称 v 为 G 的一个割点。
1.1.3 图的运算
1.1.3.1 子图
关于图之间的关系，又有
定义 1.1.6 (子图). 设 G = (V, E, ψ) 为一个图，G
′
= (V
′
, E
′
, ψ
′
) 为另一个图，如果 V
′
⊆ V, E
′
⊆ E 且 ψ
′
与 ψ 在 E
′
上相
同，则称 G
′
为 G 的一个子图。
定义 1.1.7 (生成子图). 设 G = (V, E, ψ) 为一个图，V
′
⊆ V ，则由 V
′
中的节点及其间的边所构成的子图称为由 V
′
生成的
子图，记为 G[V
′
]。
定义 1.1.8 (真子图). 设 G = (V, E, ψ) 为一个图，G
′
= (V
′
, E
′
, ψ
′
) 为另一个图，如果 G
′
为 G 的子图且 V
′
̸= V 或 E
′
̸= E，
则称 G
′
为 G 的一个真子图。
1.1.3.2 图的并
定义 1.1.9 (图的并). 设 G
1
= (V
1
, E
1
, ψ
1
) 和 G
2
= (V
2
, E
2
, ψ
2
) 为两个图，则它们的并
G = G
1
∪ G
2
(1.3)
7
复杂网络基础理论笔记 第一章 基础 Tsui Dik Sang
定义为 G = (V, E, ψ)，其中
V = V
1
∪ V
2
E = E
1
∪ E
2
(1.4)
ψ 在 E
1
上与 ψ
1
相同，在 E
2
上与 ψ
2
相同。
定义 1.1.10 (直和 (并的一种特殊情况)). 若 G
1
和 G
2
无公共边，则称 G
1
∪ G
2
为 G
1
和 G
2
的直和，记为
G = G
1
+ G
2
(1.5)
1.1.3.3 图的交
定义 1.1.11 (图的交). 设 G
1
= (V
1
, E
1
, ψ
1
) 和 G
2
= (V
2
, E
2
, ψ
2
) 为两个图，则它们的交
G = G
1
∩ G
2
(1.6)
定义为 G = (V, E, ψ)，其中
V = V
1
∩ V
2
E = E
1
∩ E
2
(1.7)
ψ 在 E 上与 ψ
1
和 ψ
2
相同。
1.1.3.4 图的差
定义 1.1.12 (图的差). 设 G
1
= (V
1
, E
1
, ψ
1
) 和 G
2
= (V
2
, E
2
, ψ
2
) 为两个图，则它们的差
G = G
1
− G
2
(1.8)
定义为 G = (V, E, ψ)，其中
V = V
1
− V
2
E = E
1
− E
2
(1.9)
ψ 在 E 上与 ψ
1
相同。
定义 1.1.13 (环和). 定义环和为从 G
1
和 G
2
的并中去掉它们的交，即
G = G
1
⊕ G
2
= (G
1
∪ G
2
) − (G
1
∩ G
2
) (1.10)
1.1.3.5 收缩图
定义 1.1.14 (收缩图). 把图 G = (V, E, ψ) 的点集 V 的一个真子集 V
′
中的所有节点合并成一个节点 v
′
，并将 V
′
中所有节
点的边都变为 v
′
的边，得到的图称为 G 关于 V
′
的收缩图，记为 G ∗ V
′
。
1.1.4 图的表示
1.1.4.1 邻接矩阵
8
复杂网络基础理论笔记 第一章 基础 Tsui Dik Sang
定义 1.1.15 (邻接矩阵). 表征的是点和点的关系，因此如果点数有 N，临界矩阵 A
N×N
，其中
a
ij
=
1, 若v
i
与v
j
之间有边相连
0, 否则
(1.11)
对于有权图，则将 1 替换为权值即可，然后如果是相似权含义下，两点无连接权值为 0，在相异权含义下，两点无连接权值为无
穷大。
1
1.1.4.2 关联矩阵
定义 1.1.16 (关联矩阵). 表征的是边和点的关系，因此如果点数有 N，边数有 M，关联矩阵 B
N×M
，其中
b
ij
=
1, 若点v
i
与边e
j
关联
0, 否则
(1.12)
显然有一堆推论，最显然的是
推论 1.1.2 (每列元素之和). 关联矩阵 B 的每一列元素之和等于 2。
1.1.4.3 可达矩阵
这是有向图特有的表示方法
定义 1.1.17 (可达矩阵). 设 G = (V, E, ψ) 为一个有向图，V = {v
1
, v
2
, · · · , v
N
}，则定义其可达矩阵 R
N×N
，其中
r
ij
=
1, 若从节点v
i
出发能到达节点v
j
0, 否则
(1.13)
本质上是一个特殊的邻接矩阵。
1.2 拓扑结构与静态特征
1.2.1
静态特征
1.2.1.1 表征距离
定义 1.2.1 (直径).
D = max
i,j
d(v
i
, v
j
) (1.14)
可以理解为反应的是一个最大范围，恰如圆的范围，非常合理，接着是一个平均值，
1
相似权含义：权值越大表示联系越紧密；相异权含义：权值越小表示联系越紧密。
9
复杂网络基础理论笔记 第一章 基础 Tsui Dik Sang
定义 1.2.2 (平均距离).
L =
1
N
2
N
i=1
N
j=1
d(v
i
, v
j
) (1.15)
然后由 d
ij
= d
ji
以及 d
ii
= 0，可以化简为
推论 1.2.1 (平均距离的简化).
L =
2
N(N − 1)
N
i=1
N
j=i+1
d(v
i
, v
j
) (1.16)
对于节点个数中等的话可以先整一个表格列出来，然后套入上面的内容
接着尝试将其与邻接矩阵联系起来定义一个是否联通的量
2
定义 1.2.3 (联通量).
d
(l)
ij
=
1, 若从节点v
i
出发经过l条边能到达节点v
j
0, 否则
(1.17)
容易知道，d
(1)
ij
= a
ij
，然后还可以证明得到
推论 1.2.2 (联通量与邻接矩阵的关系).
d
(l)
ij
= (1 − δ
ij
− d
(l−1)
ij
) · U(a
(l)
ij
) (1.18)
其中 U(x) 为单位阶跃函数，δ
ij
只有在 i = j 时取 1，否则取 0。
然后可以推出一个废话公式
推论 1.2.3 (距离与联通量的关系).
d
ij
=
D
l=1
l · d
(l)
ij
(1.19)
1.2.1.2 表征集聚程度
可以将最大能连的边作为参考来考量集散程度
定义 1.2.4 (集聚系数). 设节点 v
i
的度为 k
i
，依据者 k 个节点之间可能存在的最大边数——则 v
i
的集聚系数定义为
C
i
=
2E
i
k
i
(k
i
− 1)
(1.20)
其中 E
i
为 v
i
的邻居节点之间实际存在的边数。
求一个平均就是平均集聚系数
2
课本上并没有说这个量叫什么
10
复杂网络基础理论笔记 第一章 基础 Tsui Dik Sang
推论 1.2.4 (平均集聚系数).
C =
1
N
N
i=1
C
i
(1.21)
实际上也可以用三角形连接的数量表示
推论 1.2.5 (集聚系数的另一种表示).
C
i
=
N
i∆
N
iΛ
(1.22)
可以证明上面的式子和最开始的定义是等价的
同样的可以根据邻接矩阵进行计算，这是批量计算做题非常有用的
3
推论 1.2.6 (集聚系数的邻接矩阵表示).
C
i
=
a
(3)
ii
a
(2)
ii
(a
(2)
ii
− 1)
(1.23)
其中 a
(3)
ii
表示邻接矩阵的三次方的第 i 行第 i 列元素，其他类似。
1.2.1.3 度：重要程度
定义 1.2.5 (度). 设节点 v
i
的度为 k
i
，则定义节点 v
i
的度为与其相连的边的数目。
推论 1.2.7 (平均度).
⟨k⟩ =
1
N
N
i=1
k
i
=
2E
N
(1.24)
度的分布具有研究价值
定义 1.2.6 (度分布). 设节点 v
i
的度为 k
i
，则定义图 G 的度分布为
P (k) =
N
k
N
(1.25)
其中 N
k
为度为 k 的节点数目。
常见的有以下几种
• 规则网络
• 完全随机网络
• 无标度网络：只有幂律分布是唯一一种
更多的看课本吧，作为了解
3
然而实际上并非啊，算平方和立方的计算量还是相当的大的
11
复杂网络基础理论笔记 第一章 基础 Tsui Dik Sang
定义 1.2.7 (累积度分布). 设节点 v
i
的度为 k
i
，则定义图 G 的累积度分布为
P
cum
(k) =
∞
k
′
=k
P (k
′
) (1.26)
可以理解对应概率统计里面的分布函数
1.2.2 无向网络的静态特征
定义 1.2.8 (联合度分布). 从无向网络中随机选择一条边，边的两个端点的度分别为 k 和 k
′
的概率记为 P (k, k
′
)，称为无向
网络的联合度分布。
容易从概率论的角度找到其一个统计计算方法
推论 1.2.8 (联合度分布的计算).
P (k
i
, k
j
) =
E
k
i
,k
j
E
(1.27)
其中 E
k
i
,k
j
为度分别为 k
i
和 k
j
的节点之间的边的数目，E 为网络中的总边数。
还可以由联合度分布推出度分布
4
1.2.2.1 度-度相关性
有两种方式来描述，首先第一种要引入定义
定义 1.2.9 (最近临平均度值). 对于节点 v
i
，其最近邻平均度定义为
k
nn,i
=
j
a
ij
k
j
/k
i
(1.28)
其中 k
nn,i
表示节点 v
i
的最近邻平均度，k
j
表示节点 v
j
的度，a
ij
为邻接矩阵元素，k
i
为节点 v
i
的度。
于是所有度值为 k 的节点的最近邻平均度平均值定义为
定义 1.2.10 (度为 k 的节点的最近邻平均度).
i|k
i
=k
k
nn,i
N · P (k)
(1.29)
推论 1.2.9 (正负相关性第一种判据). -
• 如果度为 k 的节点的最近邻平均度随着 k 的增大而增大，则称网络具有正的度-度相关性，称为同配网络；
• 如果度为 k 的节点的最近邻平均度随着 k 的增大而减小，则称网络具有负的度-度相关性，称为异配网络；
然后基于 Pearson 系数的方法从略
5
集聚系数分布也从略了。
4
从略，因为 ppt 上没有
5
同样的，因为 ppt 中没有
12
复杂网络基础理论笔记 第一章 基础 Tsui Dik Sang
1.2.2.2 介数和核度：缺损重要程度
也就是说有节点虽然度很小，但是去掉会对网络造成重大影响
6
定义 1.2.11 (节点介数). 设图 G = (V, E, ψ) 中节点 v
i
的介数定义为
B
i
=
s̸=i̸=t
N
st
(i)
N
st
(1.30)
其中
N
st
为节点
v
s
和
v
t
之间的最短路径数目，
N
st
(
i
)
为经过节点
v
i
的节点
v
s
和
v
t
之间的最短路径数目。
类似的有边介数
定义 1.2.12 (边介数). 设图 G = (V, E, ψ) 中边 e
ij
的介数定义为
B
ij
=
s̸=t
N
st
(i, j)
N
st
(1.31)
其中 N
st
为节点 v
s
和 v
t
之间的最短路径数目，N
st
(i, j) 为经过边 e
ij
的节点 v
s
和 v
t
之间的最短路径数目。
而对于核度的定义基于“去掉”的思想
定义 1.2.13 (图的 k-核). 设图 G = (V, E, ψ) 中节点 v
i
的度为 k
i
，则图 G 的 k-核定义为从图 G 中去掉所有度小于 k 的节
点及其关联边后所得到的子图，记为 G
k
。
注意！根据书上例题，核度就是这个点的度，关注点其实是 k-核，也就是他的子图，节点的核度以及网络的核度都是直接看其度
数以及 max 度数即可！
定义 1.2.14 (节点的核度). 如果一个节点属于 k-核但不属于 (k+1)-核，则称该节点的核度为 k，记为 c
i
。
定义 1.2.15 (网络的核度). 节点的核度的最大值称为网络的核度，记为 c
max
。
接着是中心度
定义 1.2.16 (度中心度/归一化度值).
C
D
(v
i
) =
k
i
N − 1
(1.32)
其中 C
D
(v
i
) 为节点 v
i
的度中心度，k
i
为节点 v
i
的度，N 为网络中的节点总数。
接下来，
定义 1.2.17. 假设网络 G
optimal
为一个理想网络，则将下式的最大值定义为 H
H =
N
i=1
[C
D
(u
max
) − C
D
(u
i
)] (1.33)
6
讨论这个的时候一定要回归现实，纯网络的抽象讨论在谈到重要性的时候其实意义不大
13
复杂网络基础理论笔记 第一章 基础 Tsui Dik Sang
其中 u
max
为 G
optimal
网络中度中心度最大的节点，u
i
为网络中的任意节点。
因而对于任意的网络 G
定义 1.2.18 (网络度中心性).
C
D
=
1
H
N
i=1
[C
D
(v
max
) − C
D
(v
i
)] (1.34)
其中 v
max
为网络 G 中度中心度最大的节点，v
i
为网络 G 中的任意节点。
实际上可以证明
推论 1.2.10 (G
optimal
的形式). G
optimal
为一个完全星型网络, 即与其相连的点除了与中心点相连外，其他点之间没有连接。
也容易得到此时的 H 最大为
H = N − 2 (1.35)
于是
推论 1.2.11 (网络度中心性的简化).
C
D
=
1
N − 2
N
i=1
[C
D
(v
max
) − C
D
(v
i
)] (1.36)
对于介数也可以定义中心度, 首先要确定最大可能的介数
7
定义 1.2.19 (介数中心度/归一化介数值).
C
B
(v
i
) =
2B
i
(N − 1)(N − 2)
(1.37)
其中 C
B
(v
i
) 为节点 v
i
的介数中心度，B
i
为节点 v
i
的介数，N 为网络中的节点总数。
且有
推论 1.2.12 (网络介数中心性的简化).
C
B
=
1
N − 2
N
i=1
[C
B
(v
max
) − C
B
(v
i
)] (1.38)
1.2.2.3 网络密度
从最直观的定义就是用边的” 紧密程度来定义”
定义 1.2.20 (网络密度). 设图 G = (V, E, ψ) 中节点数为 N，边数为 E，则图 G 的网络密度定义为
d(G) =
2E
N(N − 1)
(1.39)
但是这个方法无法比较不同规模网络，因此有人提出了绝对密度
7
目前也是糊里糊涂的，不管了
14
复杂网络基础理论笔记 第一章 基础 Tsui Dik Sang
定义 1.2.21 (绝对密度).
d(G) =
M
4SR
3
/3D
(1.40)
15
第二章 机制模型
2.1 网络机制模型
2.1.1 规则网络
定义 2.1.1 (规则网络). 它是指系统各元素之间的关系可以用一些规则的结构来表示，也就是说网络中任意两个节点之间的
联系遵循既定的规则，通常每个节点的近邻数目都相同
然后介绍一些特殊的规则网络
2.1.1.1 全局耦合网络
定义 2.1.2 (全局耦合网络). 它是指系统中每个节点都与其他所有节点相连的网络结构
这也就意味着每一个节点的度都是相同的
推论 2.1.1 (全局耦合网络的度分布). 其度分布为 δ 函数分布，即为一个单尖峰。
2.1.1.2 最近邻耦合网络
定义 2.1.3 (最近邻耦合网络). 它是指系统中每个节点仅与其最近邻的 K 个节点相连的网络结构 (K<N-1)
显然，其度分布也是一个单尖峰
2.1.1.3 星型网络
定义 2.1.4 (星型网络). 它是指系统中存在一个中心节点，该节点与其他所有节点相连，而其他节点仅与中心节点相连的网
络结构
之前提到过，不赘述
2.1.2 随机网络
2.1.2.1 连接
别听定义胡扯，就是乱选形成的网络，混沌！
所谓的 ER 模型和二项式模型，定义的是概率
16
复杂网络基础理论笔记 第二章 机制模型 Tsui Dik Sang
定义 2.1.5 (ER 模型). 给定 N 个节点，最多可以存在
N(N −1)
2
条边，如果需要 M 条边，那么就可以产生
C
M
N
(
N
−
1)/2
=
(N(N − 1)/2)!
M!(N(N − 1)/2 − M)!
(2.1)
种不同的网络结构，如果每一种都是等概率出现的，那么就构成了 ER 模型
定义 2.1.6 (二项式模型). 给定 N 个节点，每一对节点之间以概率 p 连接，不以概率 1-p 连接，那么就构成了二项式模型
莫名其妙的来了一个性质 Q，有如下的结论
定理 2.1.2 (性质 Q 的结论).
lim
N→∞
P
N,p
(Q) =
0,
p(N)
p
c
(N)
→ 0
1,
p(N)
p
c
(N)
→ ∞
(2.2)
1
2.1.2.2 基础参数
并且其度分布在 N 很大的时候服从泊松分布
定理 2.1.3 (随机网络的度分布). 在 N 很大的时候，随机网络的度分布服从泊松分布
P
(
k
) =
e
−⟨k⟩
⟨k⟩
k
k!
(2.3)
推论 2.1.4 (随机网络的直径). 对于大多数的 p，几乎所有的图都有同样的直径，这就意味着连接概率为 p 的 N 阶随机图的
直径的变化幅度非常小，
D =
ln N
ln(pN)
(2.4)
推论 2.1.5 (随机网络的平均距离).
L
rand
∝
ln N
ln⟨k⟩
(2.5)
然后还有集聚系数
2
2.1.3 小世界网络模型
这些理论建模都是来源于生活的。这里描述的是一个生活关系场景
对于身边的邻居同事大多数都认识，但是有少部分的异国他乡的朋友
如果用数学的网络的语言来描述的话就是
1
接下来的内容似乎有点
2
不记得这个定义可以看回 eq. (1.20)
17
复杂网络基础理论笔记 第二章 机制模型 Tsui Dik Sang
定义 2.1.7 (小世界网络). 尽管一些网络系统有很大的尺寸，同时具有高集聚程度、小平均距离的网络
根据构造方法的不同可以分成两种
2.1.3.1 WS 模型
• 从一个有 N 个节点的最近邻耦合网络开始，其初始所有点围成一个环，每一个节点与它左右相邻的
K
2
个节点相连，并且
满足
N ≫ K ≫ ln(N ) ≫ 1 (2.6)
• 以概率 p 重新连接每一条边，即以概率 p 断开该边，并将该边的另一端随机连接到网络中的另一个节点上，重复该过程直
到网络中所有的边都被考察过为止
• p=0 时，网络仍然是一个规则网络，p=1 时，网络变成一个随机网络，而 0<p<1 时，网络则表现出小世界特性
其实从直观上很容易理解这个构造方法，可以理解为在一个确定的规则网络中引入了一些不确定因素，而由于平均距离取
决于最近的边，因此只要引入少量的随机，就有可能瞬间缩短平均距离
2.1.3.2 NW 模型
基本一致，区别是将重连边的步骤改成随机加边
2.1.3.3 参数
包括复杂网络应该研究的一系列参数。
首先是度分布，两种方法构造的都可以基于原理去推导——不过，相当复杂，所以直接给统一的结论
定理 2.1.6 (小世界网络的度分布).
P (k) =
0, k <
K
2
min(k−K/2,N −1−K/2)
n=0
C
n
K/2
(1 − p)
n
p
K/2−n
·
[pK/2]
k−K/2−n
(k − K/2 − n)!
e
−pK/2
, k ≥
K
2
(2.7)
这描述的是随机选取的任意节点的度
关于平均距离，我们只知道我们随机引入的“捷径”会大幅度缩短平均距离，但是很遗憾的是目前并没有一个精确的解析表达式
3
，不过定性分析的话就是“系统尺度”以及“交叉长度”，在“交叉长度”更大的时候
L
与
N
成正比，否则与
ln
N
成正比
不用说，研究起来也是一门学科，目前也就只有一个经验式子
定理 2.1.7 (小世界网络的平均距离经验式).
C
′
(p) ≈
3(K − 2)
4(K − 1)
(2.8)
4
3
那么你觉得考试会考吗 [坏笑]
4
特征谱 ppt 没有，直接跳
18
复杂网络基础理论笔记 第二章 机制模型 Tsui Dik Sang
2.1.4 无标度网络
仍然是源于一个现象的模型，也就是 WWW，其实际上是由极少数拥有超多链接的节点和大部分拥有较少链接的节点组成
的网络结构。
2.1.4.1 Price 模型
通俗的理解就是马太效应，即“强者愈强，弱者愈弱”，节点多的更容易获得新的连接，从而形成“富人更富”的现象
定义 2.1.8 (Price 模型: 论文引用网络模型). 论文的引用概率与它以往的引用次数纯在严格的线性关系。
模型为一个 N 节点的有向图，不断有新的节点加入到网络中，每一个新加入的节点都有一定的出度，且节点一经产生
就保持不变, 平均出度为
m =
k
kP (k) (2.9)
其中 P (k) 为节点中出度为 k 的节点所占比例
不过这个模型有一个 bug，就是在初始的时候由于改节点没有任何连接，因此无法被引用，因此引入了自引用，从而得到
定理 2.1.8 (Price 模型的度分布).
P (k) ∼ k
−(2+
1
m
)
(2.10)
2.1.4.2 BA 模型
是对于 Price 模型的一个改进，Price 模型相比于之前 ER 模型和 WS 模型更符合实际网络的特性，有以下两点
• 考虑网络规模的增长
• 考虑了网络的优先连接机制
定义 2.1.9 (BA 模型: 无标度网络模型). -
• 初始时有 m
0
个节点的网络
• 每次加入一个新节点，并与网络中已有的 m 个节点相连，且新节点与已有节点 i 连接的概率与节点 i 的度 k
i
成正比，
即
Π(k
i
) =
k
i
j
k
j
(2.11)
然后后面的内容我又不想看了，从略先
2.1.5 层次网络
这关注的是复杂网络的另外一个特性：模块化
定义 2.1.10 (层次网络). 度很小的节点具有高的集聚系数且属于高度连接的小模块；相反，度很高的 hub 节点具有低的集聚
系数，其作用只是把不同的模块连接起来。也就是说，在具有层次模块性的网络中，很多内部关联密集的小规模节点组之间
19
复杂网络基础理论笔记 第二章 机制模型 Tsui Dik Sang
松散关联，从而形成更大规模的拓扑模块
公式并没有给多少，所以我可以认为这一章节 over。
2.2 传播动力学
2.2.1 流行病模型
前面啰啰嗦嗦一大堆，我们直入主题来介绍模型
2.2.1.1 SI
模型
参见系统建模与仿真笔记，这里简单介绍原理假设
定义 2.2.1 (SI 模型). 假设在一个封闭的人群中，个体分为两类：易感者 (Susceptible, S) 和感染者 (Infected, I)。易感者是
指那些尚未感染疾病但有可能被感染的人，而感染者是指那些已经感染疾病并且能够传播疾病的人。基本假设包括：
• 人群是封闭的，没有出生、死亡或迁移。
• 易感者和感染者之间的接触是随机的，且每个个体与其他个体接触的概率相等。
• 一旦易感者被感染，他们立即转变为感染者，并且不会恢复为易感状态。
• 传播过程是连续的，可以用微分方程来描述。
定理 2.2.1 (SI 模型的基本方程).
ds(t)
dt
= −λs(t)i(t)
di(t)
dt
= λs(t)i(t)
(2.12)
2.2.1.2 SIS 模型
定义 2.2.2 (SIS 模型). 假设在一个封闭的人群中，个体分为两类：易感者 (Susceptible, S) 和感染者 (Infected, I)。易感者是
指那些尚未感染疾病但有可能被感染的人，而感染者是指那些已经感染疾病并且能够传播疾病的人。基本假设包括：
• 人群是封闭的，没有出生、死亡或迁移。
• 易感者和感染者之间的接触是随机的，且每个个体与其他个体接触的概率相等。
• 一旦易感者被感染，他们立即转变为感染者，并且感染者在一段时间后可以恢复为易感状态。
• 传播过程是连续的，可以用微分方程来描述。
定理 2.2.2 (SIS 模型的基本方程).
ds(t)
dt
= −αs(t)i(t)
di(t)
dt
= αs(t)i(t) − βi(t)
dr(t)
dt
= βi(t)
(2.13)
20
复杂网络基础理论笔记 第二章 机制模型 Tsui Dik Sang
2.2.1.3 SIRS 模型
定义 2.2.3 (SIRS 模型). 假设在一个封闭的人群中，个体分为三类：易感者 (Susceptible, S)、感染者 (Infected, I) 和康复者
(Recovered, R)。易感者是指那些尚未感染疾病但有可能被感染的人，感染者是指那些已经感染疾病并且能够传播疾病的人，
而康复者是指那些已经从疾病中恢复并且暂时具有免疫力的人。基本假设包括：
• 人群是封闭的，没有出生、死亡或迁移。
• 易感者、感染者和康复者之间的接触是随机的，且每个个体与其他个体接触的概率相等。
• 一旦易感者被感染，他们立即转变为感染者，并且感染者在一段时间后可以恢复为康复状态。
• 康复者在一段时间后会失去免疫力，重新变为易感状态。
• 传播过程是连续的，可以用微分方程来描述。
定理 2.2.3 (SIRS 模型的基本方程).
ds(t)
dt
= γr(t) − αs(t)i(t)
di(t)
dt
= αs(t)i(t) − βi(t)
dr(t)
dt
= βi(t) − γr(t)
(2.14)
2.2.1.4 SEIR 模型
定义 2.2.4 (SEIR 模型). 假设在一个封闭的人群中，个体分为四类：易感者 (Susceptible, S)、暴露者 (Exposed, E)、感染者
(Infected, I) 和康复者 (Recovered, R)。易感者是指那些尚未感染疾病但有可能被感染的人，暴露者是指那些已经接触疾病
但尚未表现出症状的人，感染者是指那些已经感染疾病并且能够传播疾病的人，而康复者是指那些已经从疾病中恢复并且具
有免疫力的人。基本假设包括：
• 人群是封闭的，没有出生、死亡或迁移。
• 易感者、暴露者、感染者和康复者之间的接触是随机的，且每个个体与其他个体接触的概率相等。
• 一旦易感者被感染，他们首先转变为暴露者，经过一段潜伏期后转变为感染者。
• 感染者在一段时间后可以恢复为康复状态。
• 传播过程是连续的，可以用微分方程来描述。
定理 2.2.4 (SEIR 模型的基本方程).
ds(t)
dt
= −βs(t)i(t)
de(t)
dt
= βs(t)i(t) − αe(t)
di(t)
dt
= αe(t) − γi(t)
dr(t)
dt
= γi(t)
(2.15)
21
复杂网络基础理论笔记 第二章 机制模型 Tsui Dik Sang
2.2.1.5 在均匀网络中的传播
只介绍 SIS 和 SIR 模型，并且直接给结论
定理 2.2.5 (SIS 模型在均匀网络中的传播).
ρ =
0, λ < λ
c
1 −
λ
c
λ
, λ ⩾ λ
(2.16)
其中 λ
c
=
1
⟨k⟩
，ρ 为稳态感染密度
定理 2.2.6 (SIR 模型在均匀网络中的传播). 由于会痊愈，所以这里以最终感染人口作为衡量
r
∞
= 1 − e
−⟨k⟩λr
∞
(2.17)
r
∞
= 0, λ < λ
c
∝ (λ − λ
c
), λ ⩾ λ
c
(2.18)
其中 λ
c
=
1
⟨k⟩
，r
∞
为最终感染人口比例
2.2.1.6 非均匀网络中的传播
传播阈值有所不同
定理 2.2.7 (两种模型的传播阈值).
λ
c
=
⟨k⟩
⟨k
2
⟩
(2.19)
可以看到对于无限大度分布 P (k) ∝ k
−γ
(γ ≤ 3) 的无标度网络来说，⟨k
2
⟩ → ∞，因此 λ
c
→ 0，
推论 2.2.8 (无标度网络中的传播阈值). 也就是说无论传染率多么小，疾病都可以在网络中传播开来。
2.2.1.7 社团上的传播：对应层次网络
也是一堆公式，我暂时不想记了，记住一个通俗的结论
推论 2.2.9 (社团结构对传播的影响). 社团越紧凑，社团内传播越快，但社团间传播越慢。
λ
c
=
1
α
(2.20)
2.2.2 舆论传播
2.2.2.1 基于 SIR
其实舆论模型也可以用这种模式
引理 2.2.10 (基于 SIR 的舆论传播模型). 舆论传播的动力学行为也服从 SIR 模型，但其三种状态的含义与流行病模型略有
不同：
22
复杂网络基础理论笔记 第二章 机制模型 Tsui Dik Sang
• S（Susceptible）：不知道消息的人群。
• I（Infected）：知道消息并有能力继续传播消息的人群。
• R（Removed）：知道消息但已经失去传播能力或兴趣的人群。
假设网络上有 N 个节点，每个节点代表一个可传播消息的个体。传播过程如下：
1. 初始时，所有节点均为 S 态，某一时刻有一个节点获得新消息，变为 I 态。
2. 处于 I 态的节点会随机选择一个邻居，将消息传递给该邻居：
• 若该邻居为 S 态，则其变为 I 态，继续传播。
• 若该邻居已为 I 态或 R 态，则该 I 节点认为消息失去传播价值，转为 R 态。
3. 该过程持续，直到网络中不再存在 I 态节点，系统达到终态。
该模型刻画了舆论在有限网络中的传播与衰减过程。
2.2.2.2 Cowan 模型
定义 2.2.5. Cowan 模型用来描述知识在网络中的传播过程。设网络有 N 个节点，每个节点 i 拥有知识量 K
i
，节点 i 与其
邻居 j 之间的知识传播由如下动力学方程描述：
dK
i
dt
=
j∈N
i
β
ij
(K
j
− K
i
) (2.21)
其中，N
i
为节点 i 的邻居集合，β
ij
为知识传播速率。该模型假设知识在相连节点间以一定速率扩散，最终趋于均衡。
2.2.2.3 Cobb-Douglas 模型
5
2.2.3 拥塞控制
6
复杂网络中的拥塞控制主要研究数据包在网络中的产生、传输、路由与拥塞缓解机制。核心内容包括：
2.2.3.1 数据包传递模型
• 基于计算机网络的数据包产生率模型：模拟真实网络中数据包的产生、传输与拥塞，关注节点产生率、路径选择与边容量
的匹配。关键参数有产生概率 p、传输能力 f(n
i
)、临界产生率 p
c
。
• 随机行走模型：数据包传输路径随机选择，简化分析网络拓扑对效率的影响。
2.2.3.2 路由策略
• 基于全局信息的路由：利用全局拓扑（如介数）分配节点处理能力，优先避开高负荷节点。节点处理能力与介数成正比时，
通信容量为网络结构不变量。
• 基于局部信息的路由：仅用邻居信息，存在最优参数 α 最大化吞吐量。提升少数中枢节点能力可有效缓解拥塞。
5
一点都看不懂，之后感兴趣了再做
6
实在看不下去，我们就基于其作业题来复习，在之后的复习过程中如果想要基于更深入的内容进行学习再说
23
复杂网络基础理论笔记 第二章 机制模型 Tsui Dik Sang
2.2.3.3 拥塞控制策略
• EGM 方法：用有效距离平衡最短路径与节点拥堵，调整路由提升容量。
• 经济方法：节点产生率/传输率与度成正比，重点提升大节点能力。
• 改进 EGM 方法：引入节点度修正有效距离，进一步分散中枢节点压力。
24
第三章 搜索
3.1 搜索
3.1.1 广度优先搜索
基本和数据结构所学的大差不差。但是由于树只是一个特殊的图，所以还是有一点点区别，具体可以去查看书本 P207 的例
题
3.1.2 随机行走搜索
稍微有一点复杂，我们展开讲一下
3.1.2.1 基本假设
有三种
• 无限制的随机行走
• 不走回头路的随机行走
• 不重复访问的随机行走
很显然的可以看出随机行走的步数远大于广度优先搜索，但是由于每次只查询一步，大大减少了网络中消息流量。
然后根据走时候的概率分布依据又可以分为
• 权重行走：以正比于边的权重的概率选择它的最近邻节点，从而从节点 v
i
走到节点 v
j
的概率为
P
ω
i→j
=
ω
ij
s
i
(3.1)
其中 s
i
=
j∈N (i)
ω
ij
为节点 v
i
的强度
• 强度行走：以正比于节点的强度的概率选择它的最近邻节点，从而从节点 v
i
走到节点 v
j
的概率为
P
s
i→j
=
s
j
a
ij
k∈N (i)
s
k
(3.2)
3.1.2.2 理论分析
首先给出一些搜索策略好坏的评价指标
定义 3.1.1 (平均搜索步数). 对每一个选择的源节点 v
i
，应用该搜索策略得到源节点到其他所有 N-1 个节点的搜索步数之和
25
复杂网络基础理论笔记 第三章 搜索 Tsui Dik Sang
为 T
i
，因此任意两个节点之间的平均搜索步长为
T =
1
N(N − 1)
N
i=1
T
i
(3.3)
3.1.2.3 在不同网络中的验证
ppt 是直接给结论的，so，我也直接给
定理 3.1.1 (随机行走搜索在最近邻耦合网络中的平均搜索步数).
¯
T ≈
1
6
(N
2
k
− 1)[1 + µ ln K] ≈
N
2
(1 + µ ln K)
6K
2
(3.4)
其中 N
k
= N /K 为每个度数级别上的节点数，µ 为网络的平均度数
定理 3.1.2 (随机行走搜索在 ER 随机网络中的平均搜索步数).
¯
T ≈
N
⟨k⟩
≈
1
p
(3.5)
其中 ⟨k⟩ 为网络的平均度数，p 为网络的连接概率
定理 3.1.3 (随机行走搜索在 WS 小世界网络中的平均搜索步数). 只能说其是介于最近邻耦合网络和 ER 随机网络之间
3.1.3
最大度搜索算法
一个很显然的尝试是，邻居的熟人越多，他就越有可能认识目标节点。
3.1.3.1 基本前提建模
引理 3.1.4 (最大度搜索的基本前提). 在每个节点都认识自己的邻居并知道每个邻居的度
3.1.3.2 算法
• 步骤 1：初始时选取源节点 v
i
与目标节点 v
j
；
• 步骤 2：从节点 v
i
出发，判断自己的邻居节点中有无目标节点 v
j
：如无，则将其中度最大的邻居节点设为当前节点；如有，
则中止搜索；
• 步骤 3：可以多次访问同一个节点，但是同一条边只能被访问一次，如果与当前节点相连的所有的边都被访问过，则返回到
上一个节点；
• 步骤 4：重复步骤 2 和 3，直到当前节点为目标节点的任一个邻居节点，目标节点即被找到，搜索完成。
3.1.4 社会网络的分散式搜索
这似乎是专门用来应对小世界网络的，
26
复杂网络基础理论笔记 第三章 搜索 Tsui Dik Sang
3.1.4.1 Kleinberg 模型
这就是一个小世界网络模型的另外构造方式
定义 3.1.2. 每个节点通过有向边连接所有与该节点的网格离不超过某个常数 a ⩾ 1 的邻居节点，这些连接称为该节点的短
程连接。此外，还有 b 条有向边从该节点连接到网络中的其他 b 个节点，这些连接称为该节点的长程连接。Kleinberg 网格
模型假定节点 u 和 v 之间有长程连接的概率与他们之间网格距离 d(u, v) 的负幂成正比，即
p
u→v
=
[d(u, v)]
−α
w̸=u
[d(u, w)]
−α
(3.6)
然后下面给出这个网络的一系列结论
引理 3.1.5. 对于 α = 0 的二维网格 NW 小世界网络，存在一个与 a、b 相关但与 n 无关的常数 c
0
，使得对于任意的分散式
算法，平均传递步数都有下界 c
0
n
2/3
。
引理 3.1.6. 当 α = 2 且 a = b = 1 时，存在一种分散式算法和一个与 n 无关的常数 c
2
，使得该算法的平均传递步数有上界
c
2
(log
2
n)
2
。
引理 3.1.7. 对于 0 ≤ α < 2，存在一个与 a、b、α 相关但与 n 无关的常数 c
α
，使得对于任意的分散式算法，平均传递步数
都有下界 c
α
n
(2−α)/3
。
引理 3.1.8. 对于 α > 2，存在一个与 a、b、α 相关但与 n 无关的常数 c
α
，使得对于任意的分散式算法，平均传递步数都有
下界 c
α
n
(α−2)/(α−1)
。
接着就有了一些结论
推论 3.1.9. 在社会网络中，若个体判断相似性时采用的分层标准 S > 1，且相似指数 α > 0，则网络更容易实现快速分散式
搜索。这与现实中人们通常依据多重标准（如地理、职业、兴趣等）建立联系相符。
推论 3.1.10. 当分层标准 S 适中（如 S = 2 或 3）时，网络的平均传递步数最小，进一步增加 S 反而会使传递步数上升。因
此，快速搜索的分层标准数存在上界。
3.1.5 Internet 中的搜索
3.1.5.1 P2P 网络
引理 3.1.11 (P2P 技术的主要特点). -
• 非中心化
• 可扩展性
• 健壮性
27
复杂网络基础理论笔记 第三章 搜索 Tsui Dik Sang
• 高性价比
• 隐私保护
• 负载均衡
引理 3.1.12 (P2P 技术的主要类型). -
• 文件内容共享和下载
• 计算能力和存储共享
• 基于 P2P 技术的协同与服务共享平台
• 即时通讯工具
• P2P 通讯与信息共享
• 基于
P2P
技术的网络电视
3.1.5.2 广播方式的 Gnutella 搜索
(目前不太想看，之后再看)
3.1.5.3 PageRank 算法
这个是重中之重
1
定义 3.1.3 (PageRank 算法的核心思想). 网页的重要性由指向它的网页数量和这些网页自身的重要性共同决定。被高权重
网页链接到的网页，其 PageRank 值也会相应提高。
记住一个公式
定理 3.1.13 (PageRank).
R
i
= (1 − η) + η
N
j=1
A
ji
k
j
R
j
(3.7)
这是一个迭代式
后面的另外的算法先从略了.
3.2 挖掘
定义 3.2.1 (挖掘的意义). 对网络中节点的重要性进行评估
1
虽然不会考，但是需要知道思想
28
复杂网络基础理论笔记 第三章 搜索 Tsui Dik Sang
3.2.1 重要节点指标
3.2.1.1 网络整体性
通过” 放到” 节点的某些特性来评估重要性, 目前已学包括
• 中心性
• 声望
3.2.1.2
基于节点删除
通过度量节点对网络通性的破坏程度来反映网络节点的重要性
定义 3.2.2 (最大联通分支尺寸).
R =
N
RC
N
(3.8)
其中 N
RC
为网络最大联通分支的节点数，N 为网络的总节点数
定义 3.2.3 (平均距离). 之前已经定义过, 从略
然而如果非连通的话直接就是无穷, 无法衡量了. 所以使用
定义 3.2.4 (网络效率).
L
C
=
2
N(N − 1)
i̸=j∈G
1
d
ij
(3.9)
接着还有一个网络生成树
引理 3.2.1 (网络生成树). 设 G 是无向连通图，A 是由 G 的每条路径任意定方向后所得到的有向图关联矩阵，则有
τ(A) = det(AA
T
) (3.10)
其中 τ(A) 表示由 A 生成的有向图的生成树数目。
进一步可以得到归一化指标
定义 3.2.5 (网络生成树数目指标).
r
i
= 1 − τ (G − v
i
)/τ(G) (3.11)
3.2.2 合理性评判指标
中心化指标用于衡量网络中各节点的重要性或中心程度。一个合理的中心化指标应满足以下要求：
1. 对称性：中心化指标应与节点编号无关。即使节点重新编号，指标值也不应改变。
2. 一致性：无论将某节点视为整个图的节点，还是仅作为某个连通分支的节点，其中心化指标值应保持一致。
3. 孤立性最小：孤立节点（没有任何连接）的中心化指标应为所有节点中最小。
29
复杂网络基础理论笔记 第三章 搜索 Tsui Dik Sang
4. 链式结构递增性：在链式结构的网络中，节点的中心化指标应从边缘向中心递增，越靠近中心，中心化程度越高。
5. 极值性：在所有具有 N 个节点的连通网络中，链式结构网络的端点节点中心化指标最小，星型结构网络的中心节点中心化
指标最大。
6. 边移除不增性：移除某节点的一条边，至少不会增加该节点的中心化指标。
3.2.3 常用挖掘方法
3.2.3.1 基于节点关联性的方法
首先是根据节点度的, 就是度, 所以从略.
然后是基于子图的
定义 3.2.6 (子图中心性). 计算从一个节点开始到该节点结束的闭环路的数目，一个闭环代表网络中的一个子图
C
s
(v
i
) =
∞
k
=0
(µ
k
(v
i
))
k
!
(3.12)
其中 µ
k
(v
i
) 表示从节点 v
i
出发经过 k 步后又回到节点 v
i
的闭环路数目。
3.2.3.2 基于最短路径法
• 介数, 讲过了, 从略
• 特征向量,ppt 貌似没有
2
• 接近度
定义 3.2.7 (接近度). 用于刻画网络中的节点通过网络到达网络中其他节点的难易程度，其值定义为该节点到达所有其
他节点的距离之和的倒数
C
c
(v
i
) =
N
j=1
d
ij
−1
(3.13)
然后同样可以归一化
推论 3.2.2.
C
C
(v
i
) = (N − 1)C
c
(v
i
) (3.14)
• 节点删除法,ppt 上也没有哦
3.2.3.3 基于模拟流的方法
• 流介数使用的是自由流动的方式, 不再关注最短
定义 3.2.8 (流介数).
C
F
(v
i
) =
s̸=v
i
̸=t
g
st
(v
i
)
g
st
(3.15)
2
懂了吧?
30
复杂网络基础理论笔记 第三章 搜索 Tsui Dik Sang
其中 g
st
表示节点 v
s
和 v
t
之间的所有路径,g
st
(v
i
) 表示这些路径中经过节点 v
i
的路径数目。
• 还有一些参数,ppt 上没有,[坏笑]
3.2.3.4 节点收缩法
3
定义 3.2.9 (节点收缩法). 将待测节点和与其相连的所有节点收缩为一个节点，通过比较不同节点收缩后得到的网络凝集度
来衡量节点的重要性。该方法认为收缩后网络凝聚度越高的节点就越重要。若一个节点的连接度越大、所处的位置越关键，
则该节点收缩后网络凝集度越大，
然后通过比较收缩前后的网络凝集度来衡量节点的重要性, 举一个极端的例子就是星型网络的中心节点
接下来定义网络的凝集度
定义 3.2.10 (网络凝集度).
ϕ[G] =
n − 1
i̸=j
d
ij
(3.16)
其中 n 为网络的节点数，d
ij
为节点 v
i
和 v
j
之间的最短路径长度。
注意这里只是不能同点算，但是两点之间都要算两次！
于是就可以得到节点的重要性度量
定义 3.2.11 (节点重要性).
IMC(v
i
) = 1 −
ϕ[G]
ϕ[G ∗ v
i
]
(3.17)
其中 G ∗ v
i
表示将节点 v
i
及其邻居节点收缩为一个节点后得到的网络。
3.2.3.5 过载函数法
ppt 上没有, 从略
3.2.3.6 权值降低法
这是针对加权网络的, 当然也适用于无权网络, 首先要给出对于有权网络的重要性评估假设
定义 3.2.12 (加权网络节点重要性评估假设). • 网络中任意两个节点之间最多存在一条连边，边权处理采取权值越大，节
点间关系越疏远, 其中 ω
ij
∈ (1, ∞) 表示节点 v
i
和 v
j
之间边的权值
• 网络中的各个节点相互独立
,
一个节点的邻边的边权值倒数
(
点权
)
越大
,
与周围节点的联系越紧密
引理 3.2.3 (影响节点重要性的因素). -
• 节点的点权
3
这应该会是考试的重点, 作业题涉及了, 最好掌握
31
复杂网络基础理论笔记 第三章 搜索 Tsui Dik Sang
• 节点所处的位置
根据上面的假设可以知道
推论 3.2.4. 节点的点权越大，该节点与其他节点联系越紧密，则该节点越重要
推论 3.2.5. 节点位置越重要，通过该节点的最短路径越多，则该节点的存在对网络的连通性有重要贡献
4
3.2.4 社团结构挖掘
3.2.4.1 基本定义
定义 3.2.13 (社团结构). 目前有两种常见定义
• 基于网络节点的相对连接频数
• 以网络连通性为评判标准
根据频数有强社团和弱社团的定义
定义 3.2.14 (强社团). 子图中每个节点与子图内其他节点的连接数都大于与子图外节点的连接数
定义 3.2.15 (弱社团). 子图内所有节点与子图内其他节点的连接数之和大于与子图外节点的连接数之和
显然弱社团的定义更宽松一些。
接着基于连通性标准定义的社团称为派系。首先是一个严格的定义
定义 3.2.16 (派系). 子图内任意两个节点之间都有路径相连，而子图与外部节点之间没有路径相连
然后也有一个宽松的定义
定义 3.2.17 (n-派系). 子图内任意两个节点之间的最短路径长度不超过 n，而子图与外部节点之间的最短路径长度大于 n
3.2.4.2 模块化 Q 函数
这是用来描述社团划分的模块化水平
5
引理 3.2.6 (网络中社团内部连边所占比例).
i,j
a
ij
δ(σ
i
, σ
j
)
i,j
a
ij
=
1
2M
i,j
a
ij
δ(σ
i
, σ
j
) (3.18)
4
例题今晚再看, 先做完笔记先
5
通俗来讲评判的是一个划分是否合理，或者用数模中更通俗的话语，其实就是“聚类”，即社团本身已经分好，这个指标用于评判这个分法 (或者说就是聚类
方法) 是否合理
32
复杂网络基础理论笔记 第三章 搜索 Tsui Dik Sang
其中 σ
i
表示节点 v
i
所属的社团编号，δ(σ
i
, σ
j
) 为克罗内克函数，当 σ
i
= σ
j
时取 1，否则取 0，M 为网络中连边的总数。
接着不加证明的给出
定理 3.2.7 (模块化 Q 函数).
Q =
1
2M
i,j
a
ij
−
k
i
k
j
2M
δ(σ
i
, σ
j
)
(3.19)
推论 3.2.8 (模块化 Q 函数的意义). 如果社团内部节点间的边没有随机连接得到的边多，则 Q 函数的值为负数。相反，当 Q
函数的值接近 1 时，表明相应的社团结构划分得很好
3.2.4.3 经典检验网络
引理 3.2.9 (人造网络的检验意义). 人造网络结构可人为设定，分析前已知信息丰富，可用于检验社团划分方法的有效性和
正确率。
定义 3.2.18 (社团结构显著性指标). 设 z
in
为节点与社团内部其他节点连边数的期望值，z
out
为与社团外部节点连边数的期
望值。z
out
越小，社团结构越明显；z
out
越大，网络越混乱，社团结构越不明显。
推论 3.2.10. 当 z
out
< 8 时，网络具有明显社团特性。z
in
= z
out
= 8 可视为人造网络社团特征的阈值。
定理 3.2.11 (社团划分正确率与 z
out
关系). 当 z
out
在一定范围内变化时，网络划分正确率基本不受影响；超过临界值后，正
确率与 z
out
呈负相关。
推论 3.2.12. 能在 z
out
较大时仍能正确划分社团的算法，实际应用价值更高。
引理 3.2.13 (实际网络检验注意事项). 检验社团划分算法时，实际网络应满足：
• 构建数据方便易得
• 网络有实际意义，结果可解释
• 宜采用已广泛使用的实际网络，便于算法比较
定义 3.2.19 (Zachary 空手道俱乐部网络). Zachary 网络是检验社团发现算法的经典实际网络。该网络记录了美国某大学空
手道俱乐部成员间的社会关系。因收费问题分裂为两个小俱乐部，节点 1 和 33 分别代表主管和校长，正方形与圆形节点分
别代表分裂后各成员。
3.2.4.4 社团划分结果评价
• 正确率：这种方法一般用于社团结构已知的网络研究中
33
复杂网络基础理论笔记 第三章 搜索 Tsui Dik Sang
定义 3.2.20 (相似度).
S =
N
R
N
(3.20)
其中 N
R
为划分正确的节点数，N 为网络总节点数。
这种方法比较严格，但是应用广泛
6
• 共同信息比较法：将标准共同信息的衡量引入到社团结构的比较中来，比第一种方法更具判别力首先定义
定义 3.2.21 (混乱矩阵 M). 其中
– 行对应网络中真实的社团
– 列对应划分算法得到的社团
– 元素 m
ij
表示真实社团 i 中被划分到社团 j 中的节点数
于是基于信息理论
7
可以的得到两种社团结构的相似度为
推论 3.2.14 (社团结构相似度).
I(A, B) =
−2
C
A
i=1
C
B
j=1
m
ij
log
m
ij
N
m
i·
m
·j
C
A
i=1
m
i·
log
m
i·
N
+
C
B
j=1
m
·j
log
m
·j
N
(3.21)
其中 C
A
和 C
B
分别为社团结构 A 和 B 中的社团数，m
i·
=
j
m
ij
，m
·j
=
i
m
ij
。
• 还有其他的方法，从略
8
查看书本例题 7.5，手动算一下试试
6
ppt 上的原话
7
具体没有说
8
ppt 上又没有
34
第四章 笔记结束
至此，复杂网络基础理论的笔记基本结束
Tsui Dik Sang
2026.1.1
35
参考文献
[1] 郭世泽, 陆哲明. 复杂网络基础理论 [M]. 北京: 科学出版社, 2012.
36
Authors
Undergraduate in Information Engineering, School of System Science and Engineering, Sun Yat-sen University
Has rich practical experience in robotics, deep learning, etc., participated in multiple national-level competitions and won awards. Currently studying locomotion and manipulation related research, with strong interest in the application of reinforcement learning in robot control.