复杂网络算法与应用

随着复杂网络研究的深入发展和研究领域的不断扩展，其应用日益广泛。近年来各类数学建模竞赛中，基于复杂网络的题目层出不穷，但目前大部分数学建模书籍中都没有涉及复杂网络的相关内容，而复杂网络方面的专著偏重于基础理论和方法，涉及算法程序实现的很少。
将基本理论和计算机算法实现相结合正是《复杂网络算法与应用》编写的初衷。《复杂网络算法与应用》共计9章，主要涉及复杂网络静态特征，各种网络模型，复杂网络上的传播模型和动力学分析，复杂网络上的同步研究，复杂网络中的搜索策略，复杂网络中的社团结构，网络层次分析法，网络博弈论。
基于Matlab给出了作者自主编写的函数和程序，并对书中出现的大部分例题配备了程序，便于学生从理论和求解两个角度入手学习复杂网络的相关理论，在学习中举一反三、事半功倍，节省学习时间。
《复杂网络算法与应用》可以作为复杂网络课程本科生和研究生的教材，也可以作为数学建模竞赛辅导书。

第1章 绪论
1.1 引言
1.1.1 Euler与Konigsberg七桥问题
1.1.2 ER随机图理论
1.1.3 社会领域的小世界实验
1.2 复杂网络的特性
1.3 数理统计基础
1.3.1 矩母函数、特征函数和概率母函数
1.3.2 一些抽样分布
1.3.3 统计推断方法
1.4 图论的基本理论
1.4.1 图论的基本概念
1.4.2 最小生成树问题
1.4.3 最短路问题
1.4.4 最大流问题
1.5 矩阵理论的相关定义和定理
习题1

第2章 复杂网络的统计描述
2.1 网络的基本静态几何特征
2.1.1 度与度分布
2.1.2 平均路径长度
2.1.3 聚类系数
2.1.4 实际网络的统计性质
2.2 无向网络的静态特征
2.2.1 联合度分布和度一度相关性
2.2.2 聚类系数分布和聚一度相关性
2.2.3 介数、核数和紧密度
2.2.4 中心性
2.2.5 连通度
2.3 赋权网络的静态特性
2.3.1 点权、单位权和权重分布差异性
2.3.2 权一度相关性和权一权相关性
2.3.3 距离分布和平均距离
2.3.4 赋权聚类系数
2.4 网络的其他静态特性
2.4.1 网络结构熵
2.4.2 特征谱
2.4.3 度秩函数
2.4.4 富人俱乐部特性
习题2

第3章 各种网络模型
3.1 规则网络
3.1.1 全局耦合网络
3.1.2 最近邻耦合网络
3.1.3 星形耦合网络
3.2 随机网络
3.2.1 随机网络模型
3.2.2 随机网络的性质
3.3 小世界网络
3.3.1 小世界网络模型
3.3.2 小世界网络的性质
3.4 无标度网络
3.4.1 BA无标度网络模型
3.4.2 BA无标度网络的度分布
3.4.3 BA无标度网络的平均路径长度和聚类系数
3.4.4 鲁棒性与脆弱性
3.4.5 适应度模型
3.5 局域世界演化网络模型
3.6 层次网络
3.6.1 模块与模体
3.6.2 层次网络概念
3.6.3 层次网络构造方法
3.7 确定性网络
3.7.1 确定性小世界网络
3.7.2 确定性无标度网络
3.8 自相似网络
3.8.1 复杂网络的自相似性
3.8.2 自相似复杂网络的构造方法
3.9 随机图产生器
3.10 结构产生器
3.11 基于连接度的产生器
3.11.1 AB模型
3.11.2 GLP模型
3.12 多局域世界模型
3.12.1 多局域世界模型的构造方法
3.12.2 多局域世界模型的度分布分析
3.12.3 改进的多局域世界模型
习题3

第4章 复杂网络上的传播模型和动力学分析
4.1 引言
4.2 复杂网络上的病毒传播
4.2.1 基于生物学的经典病毒传播模型
4.2.2 均匀网络中的病毒传播机制
4.2.3 非均匀网络中的病毒传播机制
4.2.4 有限规模无标度网络的传播阈值HJ
4.2.5 社团网络的病毒传播机制
4.2.6 关联网络的传播阈值
4.3 复杂网络上的免疫策略
4.3.1 随机免疫
4.3.2 目标免疫
4.3.3 熟人免疫
4.3.4 主动免疫
4.4 复杂网络上的舆论传播
4.4.1 刘宗华的一般网络舆论传播模型
4.4.2 Zanette的小世界网络舆论传播模型
4.4.3 Moren0的无标度网络舆论传播模型
4.4.4 汪小帆的可变聚类系数无标度网络舆论传播模型
4.4.5 舆论传播建模中应注意的问题
4.5 复杂网络的拥塞控制策略
4.5.1 拥塞现象及其产生原因
4.5.2 复杂网络中拥塞控制的路由策略
习题4

第5章 复杂网络中的同步
5.1 混沌
5.1.1 混沌的概念
5.1.2 混沌模型
5.1.3 混沌系统的刻画指标
5.2 混沌同步理论
5.2.1 混沌同步的定义
5.2.2 混沌同步的判定
5.2.3 混沌同步的方法
5.3 复杂网络的完全同步判据
5.3.1 复杂动态网络的完全同步
5.3.2 复杂动态网络完全同步的稳定性分析
5.3.3 连续时间线性耗散耦合网络的完全同步判据
5.3.4 小世界网络的完全同步
5.3.5 无标度网络的完全同步
5.4 复杂网络时滞系统的同步判据
5.4.1 连续时间时滞耗散耦合网络的完全同步判据
5.4.2 双重时滞复杂网络的同步分析
5.4.3 时滞复杂网络的自适应反馈同步
5.5 提高复杂网络同步能力的方法
5.5.1 降低网络的最大介数
5.5.2 降低网络的平均距离
5.5.3 无标度网络上去耦合的方法
5.5.4 通过全局优化算法优化网络的同步能力
习题5

第6章 复杂网络中的搜索
6.1 广度优先搜索策略
6.1.1 广度优先搜索
6.1.2 广度优先搜索改进
6.2 随机游走搜索策略
6.2.1 uRW搜索策略
6.2.2 NRRW搜索策略
6.2.3 SARW搜索策略
6.2.4 三种随机游走搜索策略仿真与分析
6.2.5 随机游走搜索策略的改进
6.3 最大度搜索策略
6.3.1 最大度搜索策略
6.3.2 应用HDS策略求两点之间的路径
6.3.3 应用HDS策略对路径寻找的改进
6.3.4 幂律指数y可变的无标度网络模型
6.3.5 HDS策略与网络的非均匀性关系
6.4 万维网中的搜索
6.4.1 Google的核心技术——PageRank
6.4.2 万维网的实时搜索
习题6

第7章 复杂网络中的社团结构
7.1 引言
7.2 节点重要性的评价指标
7.2.1 基于节点删除方法的指标
7.2.2 基于节点关联性的指标
7.2.3 基于最短路径的方法
7.2.4 其他分析方法
7.3 社团结构的定义与判断标准
7.3.1 社团结构的定义
7.3.2 模块性p函数
7.3.3 经典检验网络
7.4 Kernighan-Lin算法
7.5 谱平均法
7.5.1 谱平均法的基本思想
7.5.2 基于Normal矩阵的谱平分法
7.6 派系过滤算法
7.6.1 相关概念
7.6.2 具体算法
7.7 分裂算法
7.7.1 GN算法
7.7.2 边聚类系数法
7.8 凝聚算法
习题7

第8章 网络层次分析法
8.1 网络层析分析法原理
8.1.1 ANP结构分析
8.1.2 ANP的优势度
8.1.3 ANP网络结构超矩阵
8.2 应用ANP评估桥梁设计方案
8.2.1 构造ANP模型
8.2.2 计算未加权超矩阵
8.2.3 计算加权超矩阵
8.2.4 计算极限超矩阵
习题8

第9章 网络博弈
9.1 引言
9.1.1 对策论和对策行为
9.1.2 对策现象的三要素
9.2 零和对策
9.3 零和对策的混合策略及解法
9.3.1 零和对策的混合策略
9.3.2 零和对策的解法
9.4 二人非常数和对策
9.4.1 纯策略问题
9.4.2 混合对策问题
9.4.3 纳什均衡的应用
9.5 合作博弈
9.5.1 Shapley值方法
9.5.2 其他分配方案
9.6 演化博弈理论
9.6.1 有限理性与演化博弈理论
9.6.2 两个演化博弈的例子
9.6.3 演化稳定策略
9.6.4 模仿者动态模型
9.7 复杂网络上的演化博弈
9.7.1 规则网络上的博弈
9.7.2 小世界网络上的博弈
9.7.3 无标度网络上的博弈
9.7.4 总结
习题9
参考文献

《复杂网络算法与应用》：
用网络结构熵研究复杂网络的非同质性，并不是说用网络结构熵取代度分布。网络结构熵与度分布的关系就如同随机变量的数字特征与其概率分布函数的关系。两者是互为补充的，网络结构熵是由度分布确定的，因而网络结构熵可以更加精确简洁地度量复杂网络的非同质性。根据上述结构熵的定义可知，当一个网络具有无标度特性时，其值会相对较小，此时网络的连通性也较好，其小世界性就会越明显。当网络受损分裂为几个随机网或多数节点非连通状态下，其熵的值就会变大，从一个节点到达另一个节点的最短路径就会变长，甚至根本无法到达。也就是说，当复杂网络失去了这种特定结构，其小世界性就会消失，熵也会有较大的变化。
综上所述，熵的定义可以为衡量网络的连通性和研究网络中哪些节点是其中的核心节点提供度量标准，这样就能对我们选择保护哪些网络中的节点才能起到保护整个网络的作用给予有价值的指导。
2.4.2特征谱
随着复杂网络研究的深入，关于含有网络结构丰富信息的特征谱（Characteristicspectrum）的研究逐渐引起了人们的重视。20世纪50年代末，美籍匈牙利科学家Wigner发表文章指出：对于一个N×N的实对称矩阵A，如果它的非对角线元素的均值为0，二阶矩为一个常数并且任意阶矩有限，则当N→∞时，A的谱密度（Spectraldensity）将收敛于半圆形分布。由于复杂网络可以由实对称矩阵来表示，因此它们的谱密度是否和Wigner所说的一样也收敛于半圆形分布呢？
……