网络科学与计算

第1 章网络科学概论 ????????????????????????????????????????????????????????????????????????? 1
1.1 网络科学?????????????????????????????????????????????????????????????????????????????? 1
1.1.1 网络科学的相关定义?????????????????????????????????????????????????????? 1
1.1.2 网络科学的发展历程?????????????????????????????????????????????????????? 1
1.2 网络科学的基本概念??????????????????????????????????????????????????????????????? 4
1.2.1 连通性???????????????????????????????????????????????????????????????????????? 4
1.2.2 度与稀疏性?????????????????????????????????????????????????????????????????? 5
1.2.3 度分布???????????????????????????????????????????????????????????????????????? 5
1.3 网络科学的性质????????????????????????????????????????????????????????????????????? 5
1.3.1 大小??????????????????????????????????????????????????????????????????????????? 6
1.3.2 密度??????????????????????????????????????????????????????????????????????????? 6
1.3.3 网络直径????????????????????????????????????????????????????????????????????? 6
1.4 网络科学的主要模型??????????????????????????????????????????????????????????????? 7
1.4.1 艾狄胥-雷尼模型??????????????????????????????????????????????????????????? 7
1.4.2 瓦茨-斯特罗加茨模型????????????????????????????????????????????????????? 7
1.5 网络科学的分支领域??????????????????????????????????????????????????????????????? 8
1.5.1 生物神经网络??????????????????????????????????????????????????????????????? 8
1.5.2 人工神经网络??????????????????????????????????????????????????????????????? 8
1.5.3 经济网络????????????????????????????????????????????????????????????????????10
1.6 网络科学的前沿方向??????????????????????????????????????????????????????????????10
1.6.1 时序网络????????????????????????????????????????????????????????????????????10
1.6.2 网络上的动力学过程?????????????????????????????????????????????????????11
1.6.3 自适应网络?????????????????????????????????????????????????????????????????11
1.6.4 高阶网络????????????????????????????????????????????????????????????????????12
1.7 本章小结?????????????????????????????????????????????????????????????????????????????12
思考题???????????????????????????????????????????????????????????????????????????????????????12
参考文献????????????????????????????????????????????????????????????????????????????????????12
第2 章图论 ????????????????????????????????????????????????????????????????????????????????????14
2.1 图的基本要素???????????????????????????????????????????????????????????????????????14
2.1.1 节点和边????????????????????????????????????????????????????????????????????14
2.1.2 度和度分布?????????????????????????????????????????????????????????????????15
2.2 图的表示?????????????????????????????????????????????????????????????????????????????16
2.2.1 邻接矩阵????????????????????????????????????????????????????????????????????16
2.2.2 邻接表???????????????????????????????????????????????????????????????????????17
2.2.3 关联矩阵表示法???????????????????????????????????????????????????????????17
2.2.4 边列表???????????????????????????????????????????????????????????????????????17
2.3 图的类型?????????????????????????????????????????????????????????????????????????????18
2.4 图的连通性??????????????????????????????????????????????????????????????????????????19
2.5 特殊图????????????????????????????????????????????????????????????????????????????????21
2.5.1 完全图???????????????????????????????????????????????????????????????????????21
2.5.2 平面图???????????????????????????????????????????????????????????????????????22
2.5.3 二分图???????????????????????????????????????????????????????????????????????22
2.5.4 树?????????????????????????????????????????????????????????????????????????????23
2.5.5 桥?????????????????????????????????????????????????????????????????????????????23
2.5.6 特殊子图????????????????????????????????????????????????????????????????????23
2.6 图的应用分析???????????????????????????????????????????????????????????????????????25
2.6.1 图/树的遍历?????????????????????????????????????????????????????????????????25
2.6.2 最短路径算法??????????????????????????????????????????????????????????????26
2.6.3 最小生成树?????????????????????????????????????????????????????????????????28
2.6.4 网络流算法?????????????????????????????????????????????????????????????????28
2.7 本章小结?????????????????????????????????????????????????????????????????????????????31
思考题???????????????????????????????????????????????????????????????????????????????????????31
参考文献????????????????????????????????????????????????????????????????????????????????????31
第3 章网络模型 ??????????????????????????????????????????????????????????????????????????????33
3.1 规则网络与随机网络??????????????????????????????????????????????????????????????33
3.1.1 规则网络????????????????????????????????????????????????????????????????????33
3.1.2 随机网络????????????????????????????????????????????????????????????????????33
3.1.3 对比分析????????????????????????????????????????????????????????????????????34
3.2 小世界网络??????????????????????????????????????????????????????????????????????????35
3.2.1 小世界网络?????????????????????????????????????????????????????????????????35
3.2.2 应用分析????????????????????????????????????????????????????????????????????35
3.3 无标度网络??????????????????????????????????????????????????????????????????????????36
3.3.1 无标度网络?????????????????????????????????????????????????????????????????36
3.3.2 应用分析????????????????????????????????????????????????????????????????????36
3.4 本章小结?????????????????????????????????????????????????????????????????????????????39
思考题???????????????????????????????????????????????????????????????????????????????????????39
参考文献????????????????????????????????????????????????????????????????????????????????????39
第4 章网络度分布及其度量 ???????????????????????????????????????????????????????????????41
4.1 节点度????????????????????????????????????????????????????????????????????????????????41
4.1.1 度与平均度?????????????????????????????????????????????????????????????????41
4.1.2 出度与入度?????????????????????????????????????????????????????????????????41
4.2 度分布????????????????????????????????????????????????????????????????????????????????42
4.2.1 度分布的概念??????????????????????????????????????????????????????????????42
4.2.2 钟形曲线到长尾分布?????????????????????????????????????????????????????43
4.2.3 幂律分布????????????????????????????????????????????????????????????????????44
4.3 度相关性及其度量?????????????????????????????????????????????????????????????????46
4.3.1 高阶度分布的引入????????????????????????????????????????????????????????46
4.3.2 联合概率分布??????????????????????????????????????????????????????????????47
4.3.3 条件概率和余平均度?????????????????????????????????????????????????????48
4.3.4 同配系数????????????????????????????????????????????????????????????????????49
4.4 应用分析?????????????????????????????????????????????????????????????????????????????50
4.4.1 蛋白组演化网络???????????????????????????????????????????????????????????50
4.4.2 预测流感病毒发生????????????????????????????????????????????????????????50
4.4.3 区域创新系统??????????????????????????????????????????????????????????????50
4.5 本章小结?????????????????????????????????????????????????????????????????????????????51
思考题???????????????????????????????????????????????????????????????????????????????????????51
参考文献????????????????????????????????????????????????????????????????????????????????????51
第5 章网络相似性度量 ?????????????????????