第1章 引言 1
参考文献 3
第2章 社区分析基本知识 4
2.1 社区发现的原理 4
2.1.1 社区的定义 4
2.1.2 社区发现的方法分类 6
2.1.3 计算复杂度 8
2.2 数据集与算法的评价指标 9
2.2.1 经典数据集 9
2.2.2 人工数据集产生 13
2.2.3 评价指标 15
参考文献 21
第3章 社区发现经典算法 24
3.1 传统基于图分割和谱分析的社区发现算法 25
3.1.1 Kernighan-Lin算法 25
3.1.2 谱划分 27
3.2 基于图聚类的社区发现算法 32
3.2.1 主要聚类方法分类 32
3.2.2 基于划分聚类的社区发现算法 34
3.2.3 基于层次聚类的社区发现算法 37
3.2.4 基于密度聚类的社区发现算法 38
3.3 社区评估指标及目标优化常用方法 41
3.3.1 单目标优化——模块度最优化算法 43
3.3.2 多目标优化算法 54
3.4 基于信息论和概率的社区发现算法 63
3.4.1 标签传播算法 63
3.4.2 信息编码算法 67
3.4.3 贝叶斯概率模型 71
3.4.4 基于随机游走模型的图分割 74
3.5 基于物理模型的社区发现算法 76
3.5.1 派系过滤算法 76
3.5.2 电阻网络电压谱分割方法 79
3.5.3 自旋模型 79
3.5.4 基于拓扑势的网络社区发现方法 81
参考文献 83
第4章 社区发现的新兴方法 86
4.1 非重叠社区发现方法 86
4.1.1 基于多目标的社区发现方法 86
4.1.2 基于遗传算法的社区发现方法 88
4.1.3 基于稳定度的社区发现方法 89
4.1.4 基于后验方法的社区发现方法 90
4.1.5 基于截断PageRank的社区发现方法 91
4.1.6 基于果蝇爬山策略的社区发现方法 93
4.1.7 基于密度的社区发现方法 93
4.1.8 基于动态距离学的社区发现方法 93
4.1.9 其他社区发现方法 96
4.2 重叠社区发现方法 96
4.2.1 重叠社区发现的定义及相关概念 96
4.2.2 结合隐式链接偏好的重叠社区发现方法 97
4.2.3 利用链路空间变换的重叠社区发现 101
4.2.4 从局部谱子空间检测重叠社区方法 109
4.2.5 重叠社区检测的局部种子选择方法 109
4.2.6 基于边聚类的重叠社区发现方法 110
4.2.7 基于最大团的重叠社区发现方法 111
4.3 属性网络社区发现方法 112
4.3.1 属性网络社区发现研究综述 112
4.3.2 基于数据融合角度的大规模网络重叠社区发现方法 122
4.3.3 属性网络社区发现的其他方法 123
4.4 本章小结 124
参考文献 124
第5章 虚拟社区演化 127
5.1 动态网络 127
5.1.1 动态网络分析 127
5.1.2 动态社区发现与社区演化 127
5.2 社区演化模型 128
5.2.1 基于核节点的社区演化模型 128
5.2.2 带权社区的涌现模型 130
5.2.3 基于图模体的GMM 132
5.3 演化社区发现算法 133
5.3.1 基于动态增量的演化社区发现 133
5.3.2 基于距离增量的演化社区发现 136
5.3.3 基于博弈论的社会网络动态社区检测 139
5.3.4 基于多模式聚类的演化社区发现 141
5.3.5 基于拉普拉斯动力学方法的演化社区发现 143
5.3.6 基于差分演化的演化社区发现 144
5.3.7 基于相邻时刻相似度比较的演化社区发现 146
5.4 演化分析框架 147
5.4.1 基于事件的社区网络演化分析 147
5.4.2 基于角色的社区网络演化分析 152
5.4.3 基于独立社区发现的演化分析 156
5.4.4 基于网络融合的演化分析 157
5.4.5 基于演化聚类平滑性的演化分析 157
5.4.6 基于节点行为的社区演化分析 158
5.4.7 基于张量分解的社区演化分析 159
5.5 社区演化评价 164
5.5.1 基于时空独立评价的方法 165
5.5.2 基于时空集成评价的方法 165
5.5.3 基于统一评价的方法 167
参考文献 170
第6章 社区分析与其他领域交叉研究 173
6.1 基于社区分析的情感研究 173
6.1.1 基于多元情感行为时间序列的社交网络用户聚类分析 173
6.1.2 社交网络情感社区发现研究 176
6.2 基于社区分析的预测方法 178
6.2.1 基于社区结构的链接预测和属性推断联合解决方法 178
6.2.2 面向多模社交网络的聚类信任预测 180
6.3 异质网络中的聚类和排序算法 182
6.3.1 异质网络中的社区发现 182
6.3.2 基于排序的聚类问题研究 188
6.4 社区分析在推荐系统的应用 189
6.4.1 社会化推荐 190
6.4.2 基于社区的组推荐模型 191
6.4.3 其他有关社区分析的推荐算法 192
6.5 其他研究 194
6.5.1 社区分析在实体消歧领域的应用 194
6.5.2 基于社区分析的链路预测 200
6.6 本章小结 206
参考文献 206
第7章 社区发现与演化分析快速计算方法 209
7.1 图并行计算框架 209
7.1.1 面向大图数据的并行计算模型 209
7.1.2 基于内存的并行计算模型 215
7.2 图挖掘的快速计算 221
7.2.1 大规模图数据处理问题 221
7.2.2 图挖掘快速计算：增量式计算实例 222
7.2.3 图挖掘快速计算：并行计算实例 229
7.3 并行社区发现与演化分析 234
7.3.1 基于Spark的并行大型多维网络分析 234
7.3.2 一种可扩展的非重叠社区发现算法框架 236
7.3.3 基于MapReduce框架的社区发现并行计算方法InfoMR 237
7.3.4 基于链路图的大规模网络并行重叠社区发现算法 238
7.3.5 基于GraphLab框架的重叠社区发现并行计算方法：DOCvN 245
7.4 并行社区发现评估及应用 249
7.4.1 传统社区发现评价指标 249
7.4.2 并行社区发现评价指标 250
参考文献 253
第8章 社区分析算法评测平台 256
8.1 评测平台综述 256
8.1.1 现有的评测方法与平台 256
8.1.2 本平台的设计目标 259
8.2 平台框架与功能设计 260
8.2.1 技术背景 260
8.2.2 整体设计 263
8.2.3 功能设计 268
8.3 平台的扩展 277
8.4 平台操作案例 280
8.4.1 数据角度 280
8.4.2 算法角度 282
8.4.3 指标角度 287
8.5 平台使用实例 290
参考文献 294
第9章 总结 296
参考文献 298