本书主要介绍复杂网络社团发现理论与应用。复杂网络社团发现旨在揭示复杂网络中真实存在的网络社团结构。研究复杂网络社团结构,在分析实体复杂网络的拓扑结构、理解现实复杂网络的功能、发现复杂网络隐藏的规律和预测复杂网络的动力学行为等方面具有重要的现实意义,并且具有广泛的应用前景。本书首先介绍复杂网络基础知识、社团定义及相关基础和社团定量刻画;其次介绍主流的社团发现方法、算法和社团结构的层次性;最后介绍社团发现的应用。
样章试读
目录
- 目录
前言
第1章 复杂网络基础知识 1
1.1 复杂网络概述 1
1.2 图论基础 2
1.2.1 图的矩阵表示 3
1.2.2 度分布 5
1.3 无标度网络 7
1.3.1 泊松分布与幂律分布 7
1.3.2 BA模型 9
1.4 小世界网络 13
1.4.1 平均路径长度与聚类系数 13
1.4.2 WS模型和NW模型 16
1.5 度相关性 20
1.6 现实世界中的复杂网络 22
参考文献 24
第2章 社团定义及相关基础 26
2.1 网络的社团特性 26
2.1.1 网络社团的普遍性 26
2.1.2 社团定义 34
2.1.3 社团内部结构 41
2.2 基准网络及其社团结构 45
2.2.1 计算机生成的基准网络 45
2.2.2 实际基准网络 47
2.2.3 划分结果比较方法 50
参考文献 52
第3章 社团定量刻画 55
3.1 社团分割的合理化指标 55
3.2 Newman模块度 56
3.2.1 配置模型 57
3.2.2 基于Newman模块度的GN算法 57
3.2.3 Newman模块度的局限性 60
3.3 基于信息论的社团分割合理性度量 68
3.3.1 网络中的随机行走理论 69
3.3.2 基于随机行走理论的模块度 75
3.3.3 基于编码的模块度 76
参考文献 77
第4章 基于寻优的社团发现方法 79
4.1 贪婪算法 79
4.1.1 基于Newman模块度的寻优方法 79
4.1.2 基于编码模块度的寻优方法 85
4.2 蚁群算法 90
4.2.1 基于Newman模块度的寻优方法 92
4.2.2 基于编码模块度的寻优方法 94
4.3 模拟退火算法 97
4.3.1 基于Newman模块度的寻优方法 98
4.3.2 基于编码模块度的寻优方法 101
参考文献 102
第5章 基于直观概念的社团发现算法 104
5.1 分裂算法 104
5.2 网络合并算法 116
5.2.1 网络合并算法概述 116
5.2.2 相似度指标 124
5.2.3 基于相似度的网络合并 126
5.3 谱分析算法 126
5.3.1 基于谱分析的社团划分算法 129
5.3.2 网络矩阵谱分析方法的综合分析 136
参考文献 140
第6章 重叠社团发现算法 142
6.1 重叠社团的定义 142
6.2 派系过滤算法 144
6.3 基于边的社团发现算法 150
参考文献 166
第7章 多尺度社团发现与网络的层次结构 168
7.1 社团发现方法的分辨率局限特性 168
7.2 多尺度社团发现方法 172
7.2.1 基于社团数量的多尺度社团发现方法 173
7.2.2 基于参数化模块度的多尺度社团发现方法 183
7.2.3 不同尺度社团结构之间的嵌套性分析 191
参考文献 195
第8章 社团发现的应用 197
8.1 用户通话网络的社团结构 197
8.1.1 用户通话网络模型构建及拓扑结构 197
8.1.2 通话网络的社团发现及应用分析 203
8.2 BBS用户网络的社团结构 208
8.2.1 BBS用户网络模型构建及拓扑结构 208
8.2.2 社团发现与热点主题 212
8.3 复杂公交网络的性能分析 215
8.3.1 城市公交网络模型 216
8.3.2 社团划分及其应用 223
8.3.3 公交停靠站点网络抗毁性分析和网络优化 225
参考文献 227