第一章 复杂网络基本概论 1
1.1什么是网络 3
1.1.1社会网络 4
1.1.2技术网络 8
1.1.3生物网络 11
1.2如何刻画网络 13
1.2.1平均距离与小世界效应 14
1.2.2度分布与无标度特性 16
1.2.3局部结构 18
1.2.4节点与链路的中心性 20
1.2.5群落结构 21
1.2.6关联性 24
1.2.7熵 25
1.2.8其他网络特征概览 26
1.3最基本的网络模型 27
1.3.1规则网络 28
1.3.2随机网络 30
1.3.3小世界网络 31
1.3.4无标度网络 33
1.4小结 35
第二章 链路预测的基本概念 41
2.1背景和意义 42
2.2问题描述 46
2.3数据集划分 47
2.3.1随机抽样 47
2.3.2逐项遍历 47
2.3.3 k-折叠交叉检验 48
2.3.4滚雪球抽样 48
2.3.5熟识者抽样 48
2.3.6随机游走抽样 49
2.3.7基于路径抽样 49
2.4评价指标 50
2.4.1 AUC 50
2.4.2精确度 55
2.4.3排序分 55
第三章 基于相似性的链路预测 57
3.1基于局部信息的相似性指标 58
3.1.1基于共同邻居的相似性指标 58
3.1.2偏好连接相似性 62
3.1.3局部朴素贝叶斯模型 62
3.2基于路径的相似性指标 63
3.2.1局部路径指标 63
3.2.2 Katz指标 64
3.2.3 LHN-Ⅱ指标 64
3.3基于随机游走的相似性指标 67
3.3.1全局随机游走 67
3.3.2局部随机游走 70
3.4其他相似性算法 71
3.4.1矩阵森林指数 71
3.4.2自洽转移相似性 71
3.5相似性算法计算示例 73
3.6链路预测效果比较分析 74
3.6.1实验数据 74
3.6.2预测结果比较 76
第四章 基于似然分析的链路预测 79
4.1层次结构模型 80
4.2随机分块模型 85
4.3闭路模型 88
4.4小结 91
第五章 加权网络的链路预测 95
5.1什么是加权网络 96
5.1.1加权网络的图表示 96
5.1.2刻画加权网络 97
5.1.3加权网络上的动力学 101
5.2加权网络的相似性与链路预测 103
5.2.1加权相似性指标 103
5.2.2预测效果 104
5.3链路预测中的弱连接效应 106
5.4加权网络的极大似然模型 115
第六章 有向网络的链路预测 123
6.1什么是有向网络 124
6.1.1有向网络的图表示 124
6.1.2刻画有向网络 126
6.1.3有向网络的模体 132
6.2基于局部结构的预测 135
6.3有向网络的势理论 139
第七章 二部分网络的链路预测 151
7.1什么是二部分网络 152
7.1.1二部分网络的结构特征 154
7.1.2二部分网络与其他网络的关系 158
7.1.3二部分网络的演化建模 161
7.2链路预测方法 163
7.2.1二部分网络的层次结构模型 163
7.2.2核函数方法 165
7.2.3内部边方法 168
第八章 链路预测的应用 171
8.1网络重构 172
8.2基于似然分析的网络演化模型评价方法 176
8.2.1演化模型的似然分析 177
8.2.2 Internet自主系统演化模型的比较 179
8.3节点的标签分类问题 183
8.3.1基于幽灵边的标签分类 184
8.3.2基于节点相似性的标签分类 188
8.3.3标签分类与链路预测 189
8.3.4标签分类的其他应用 191
8.4链路预测在蛋白质相互作用网中的应用 193
8.5链路预测在社交网络上的应用 197
8.5.1方向与互惠 198
8.5.2社交网络中的好友推荐 199
8.5.3预测异质的社交关系 203
8.5.4社交网络中的强关系与弱关系 205
8.5.5小结 207
8.6异常链路分析 208
8.6.1异常边 209
8.6.2异常边与网络连通性 209
8.6.3异常边与网络传输能力 210
第九章 结束语 213
参考文献 219
附录A概念、方法和算法 261
A.1 AUC计算中的n取值问题 261
A.2局部朴素贝叶斯模型 264
A.3网络上的随机游走 267
A.4矩阵求逆及其快速算法 270
A.4.1矩阵基本概念 270
A.4.2算法效率的度量方法 271
A.4.3矩阵求逆算法 271
A.4.4稀疏矩阵 275
A.5吉布斯抽样方法 276
A.5.1算法简介 276
A.5.2算法思想 277
A.5.3算法描述 277
附录B资料汇总 279
B.1相似性 279
B.2实验涉及的真实网络信息 281
附录C算法的程序实现 289
C.1网络的输入与构建 289
C.2数据集划分 290
C.3 AUC计算 292
C.4相似性的计算 293
C.5基于相似性的链路预测主函数 307
名词索引 315
人名索引 323