第1章 大规模图数据处理：问题与挑战 1
1.1 大图数据处理的背景 1
1.2 图数据的表示 2
1.3 传统的大图数据管理方法 4
1.4 云计算环境处理大图数据的优势 6
1.5 新型大图计算系统面临的挑战 7
1.6 关键技术问题 8
第2章 大图分布式处理的计算模型和执行机制 11
2.1 大图分布式处理的基本计算框架 11
2.1.1 基于MapReduce的计算框架 11
2.1.2 基于BSP的计算框架与GAS模型 14
2.1.3 MapReduce与BSP对比 16
2.1.4 其他处理框架 17
2.2 图查询处理的遍历模式 19
2.2.1 以顶点为中心 19
2.2.2 以子图为中心 19
2.2.3 以边和路径为中心 19
2.3 消息通信 20
2.3.1 消息发送时序控制 20
2.3.2 消息交换模式 20
2.3.3 网络通信平台 22
2.3.4 上层消息优化技术 23
2.4 同步控制 23
2.4.1 同步模式 24
2.4.2 异步模式 25
2.4.3 混合模式 25
2.4.4 跨步模式 26
2.5 容错管理 26
2.5.1 故障恢复技术 26
2.5.2 故障侦测技术 30
2.6 任务调度 30
2.7 可扩展性 32
第3章 大图数据划分技术 34
3.1 图数据划分技术综述 34
3.1.1 离线划分算法 35
3.1.2 在线划分算法 36
3.1.3 动态划分算法 38
3.2 大图划分定义 41
3.2.1 处理流程和定义 41
3.2.2 真实图的局部性分析 42
3.3 OnFlyP划分算法 44
3.3.1 Range划分 44
3.3.2 OnFlyP划分 45
3.3.3 负载均衡控制机制 47
3.3.4 计算接口描述 49
3.3.5 动态调整机制 51
3.4 性能评价 52
3.5 小结 55
第4章 大图数据分布式存储与索引技术 56
4.1 大图数据的存储索引技术综述 56
4.2 图迭代算法的状态转换模型 60
4.3 大图的磁盘存储管理机制 62
4.3.1 基于列存储模型的静态Hash索引策略 62
4.3.2 基于状态转换的动态Hash索引策略 66
4.4 基于消息有序的磁盘迭代 71
4.4.1 消息有序迭代MSI 71
4.4.2 OERSV数据模型 72
4.4.3 两阶段计算过程 74
4.5 性能评价 75
4.6 小结 77
第5章 大图数据分布式三角形查询技术 78
5.1 大图三角形查询技术综述 78
5.1.1 集中式算法 79
5.1.2 分布式算法 81
5.1.3 近似算法 84
5.2 分布式大图三角形查询优化技术 84
5.2.1 存储结构 84
5.2.2 EN-Iterator算法 86
5.2.3 消息优化 87
5.3 基于采样的近似处理技术 89
5.3.1 采样策略 89
5.3.2 算法描述 91
5.4 性能评价 92
5.5 小结 95
第6章 大图数据分布式最大k边连通子图查询技术 96
6.1 大图最大k边连通子图查询技术综述 96
6.2 分布式最大k边连通子图优化技术 103
6.2.1 顶点优化 103
6.2.2 剪枝策略 104
6.2.3 消息优化 106
6.3 基于采样的近似处理技术 107
6.3.1 采样策略 107
6.3.2 算法描述 108
6.4 性能评价 109
6.5 小结 112
第7章 大图数据分布式最小生成树查询技术 113
7.1 大图数据最小生成树综述 113
7.2 顶点驱动的并行MST算法 118
7.2.1 PB算法（分区Prim算法＋Bor？vka算法） 118
7.2.2 算法正确性 119
7.2.3 双重索引 120
7.2.4 终止条件 121
7.2.5 索引维护 122
7.3 基于并行处理模型的PB算法 122
7.3.1 基于MapReduce模型的PB算法 122
7.3.2 基于BSP模型的PB算法 124
7.3.3 PB算法代价分析 124
7.4 动态图的MST维护算法 126
7.4.1 MST结果预处理 126
7.4.2 删除边维护 127
7.4.3 删除顶点维护 129
7.4.4 维护代价 129
7.5 性能评价 130
7.6 小结 132
第8章 大图数据分布式频繁子图挖掘技术 133
8.1 图数据频繁子图挖掘技术综述 133
8.1.1 图数据集中的频繁模式挖掘算法 134
8.1.2 单个大图的频繁模式挖掘算法 134
8.1.3 并行图频繁模式挖掘 136
8.2 基于最大团频繁计数的频繁子图挖掘 137
8.2.1 整体框架 137
8.2.2 挖掘频繁1-子图 140
8.2.3 候选子图产生 141
8.2.4 频繁计数 143
8.3 频繁子图挖掘分布式处理的优化 146
8.4 基于AMNI频繁计数的子图挖掘 149
8.5 频繁子图挖掘的BSP实现 151
8.6 性能评价 152
8.7 小结 155
第9章 大图数据分布式重叠社区发现技术 156
9.1 复杂网络重叠社区发现技术综述 156
9.1.1 团渗透方法 158
9.1.2 边图与边划分方法 159
9.1.3 局部扩展最优化算法 159
9.1.4 模糊检测法 160
9.1.5 基于混合概率模型算法 161
9.1.6 基于非负矩阵分解算法 161
9.1.7 其他类型算法 162
9.2 分布式并行极大团枚举 162
9.2.1 问题描述 163
9.2.2 极大团枚举方法 164
9.2.3 极大团枚举方法优化 166
9.2.4 并行极大团枚举方法 169
9.2.5 复杂度分析 172
9.3 复杂网络中并行重叠社区发现 173
9.3.1 问题描述 173
9.3.2 GCE基本算法 174
9.3.3 GCE算法的优化 175
9.3.4 GCE算法并行化 177
9.4 性能评价 183
9.5 小结 185
第10章 大规模图数据分布式处理系统和应用 186
10.1 基于MapReduce模型的大图处理系统 186
10.1.1 PECASUS 186
10.1.2 HaLoop 187
10.1.3 Twister 187
10.2 基于BSP模型的大图处理系统 188
10.2.1 Pregel 188
10.2.2 Hama 188
10.2.3 Giraph 189
10.2.4 Giraph++ 190
10.2.5 GPS 191
10.2.6 X-Pregel 191
10.2.7 Pregelix 192
10.2.8 MOCgraph 192
10.2.9 Kylin 193
10.3 其他代表性系统 193
10.3.1 PowerGraph 193
10.3.2 Trinity 194
10.3.3 GBase 194
10.3.4 Spark(GraphX) 195
10.3.5 GraphLab 195
10.3.6 Chronos 196
10.3.7 LFGraph 196
10.3.8 GraphChi、X-Stream和TurboGraph 197
10.4 BC-BSP系统介绍 200
10.4.1 体系结构概况 200
10.4.2 图处理作业的执行流程 201
10.4.3 PageRank算法示例 203
10.5 大规模图数据分布式处理的应用 207
10.5.1 Web应用 207
10.5.2 社会网络应用 210
10.5.3 生物和化学领域应用 215
参考文献 220