图不仅被当成建模工具使用，而且是一种应用广泛的数据结构。如何高效地管理和挖掘大图数据成为具有挑战性的问题。本书将面向大图数据介绍与大图数据的管理、分析相关的理论和技术，特别是最新的研究成果。 本书第1章对大图数据的基本概念进行简要介绍，为读者奠定大图数据管理与分析方面的理论基础；第2章介绍图的结构与表征，使读者有效定义图模型；第3～8章对图计算系统、图相似与图查询、子图挖掘、图聚类、图中的异常检测和图缩减进行深入探讨，以期为读者提供全面的大图数据管理与分析知识。 本书以实用性为导向，通过教科书式的体例安排，对大图数据管理与分析进行全方位的解构，兼顾理论与实践、基础与前沿，适合作为高等学校“数据科学与大数据技术”专业的核心课程教材，也可供相关技术人员参考。

王宏志，男，汉族，1978年生。长聘教授，博士生导师；计算机科学与工程系主任，计算学部海量数据计算研究中心主任，数据科学与大数据技术专业负责人，黑龙江省大数据科学与工程重点实验室主任, 哈工大青年科学家工作室负责人；计算学部校友会秘书长。中国计算机学会杰出会员，IEEE Senior member。研究方向为数据库、大数据管理与分析、大数据治理等，发表论文350余篇，SCI收录百余次，他引4000余次，先后主持国家自然科学基金重点项目、国际合作项目等10余项项目，以主要成员身份参与国家自然科学基金重点项目以及一批省部级重点项目和多项国际合作项目等。 获得黑龙江省教学名师、青年龙江学者、微软学者、中国优秀数据库工程师、IBM博士英才等称号，获得黑龙江省自然科学奖和教育部高校科技进步奖各1项，黑龙江省“头雁计划”团队成员。

目 录
第1章 大图数据概述 1
1.1 引言 1
1.1.1 什么是图 1
1.1.2 图的基本概念 3
1.1.3 图的存储 6
1.1.4 大图数据 7
1.1.5 图与分布式计算 8
1.2 图数据管理与分析中研究的问题 8
1.2.1 图查询 8
1.2.2 图匹配 9
1.2.3 图的社区检测 9
1.2.4 图模式挖掘 10
1.2.5 图中的最短路径 10
1.3 发展趋势与展望 11
1.3.1 图数据管理与分析面临的挑战 11
1.3.2 总结 17
第2章 图的结构与表征 18
2.1 图的结构和模型 18
2.1.1 图的基本结构 18
2.2.2 图的表示方法 18
2.1.2 概率图 20
2.1.3 图数据的分类 21
2.2 图数据的基本操作 23
2.2.1 图搜索 23
2.2.2 随机游走 26
2.2.3 PageRank 31
2.3 图结构表征 34
2.3.1 结构一致性 35
2.3.2 Struc2vec 35
2.3.3 node2vec 38
2.3.4 LINE 40
2.3.5 图自编码器 41
第3章 图计算系统 44
3.1 图计算概述 44
3.1.1 图计算与通用大数据处理系统 45
3.1.2 图计算框架 46
3.1.3 图计算的编程模型 50
3.1.4 图计算系统中的语言 52
3.2 图计算模型 53
3.2.1 顶点中心计算模型 53
3.2.2 GAS计算模型 58
3.2.3 边中心计算模型 60
3.2.4 路径中心计算模型 61
3.2.5 子图中心计算模型 64
3.3 关键技术 67
3.3.1 图数据的稀疏矩阵组织 67
3.3.2 图数据的划分 68
3.3.3 图数据划分中的内存管理 69
3.2.4 顶点程序的调度 70
3.2.5 计算与通信模式 70
3.4 现代图计算系统 71
3.4.1 单机内存 71
3.4.2 单机外存 72
3.4.3 多机内存 73
3.4.4 多机外存 73
3.4.5 动态图计算系统 74
3.4.6 图计算系统例析 74
3.5 图计算的应用 78
3.5.1 传统的图计算应用 78
3.5.2 新兴的图计算应用 79
第4章 图相似与图查询 82
4.1 图的相似性 82
4.2 图匹配 82
4.2.1 图的同构 83
4.2.2 子图同构 84
4.2.3 图编辑距离 86
4.2.4 DELTACON图相似度函数 88
4.2.5 图匹配算法 89
4.2.6 图匹配在生物信息领域的应用 92
4.3 图查询算法 92
4.3.1 图查询概述 92
4.3.2 图查询语言 94
4.3.3 子图匹配算法 98
4.2.4 图查询处理系统例析 101
第5章 子图挖掘 104
5.1 图挖掘 104
5.2 二分图匹配 104
5.3 频繁子图挖掘 106
5.3.1 频繁子图 107
5.3.2 基于Apriori的算法 107
5.3.3 基于Patern-Growth的算法 109
5.3.4 其他算法 112
5.4 密集子图检测 113
5.4.1 子图密度与密集子图 113
5.4.2 基于Clique的方法 114
5.4.3 基于k-core的方法 115
5.4.4 基于k-truss的方法 117
5.4.5 基于k-plex的方法 119
5.4.6 启发式算法 120
5.4.7 近似算法 120
第6章 图聚类 122
6.1 聚类算法的思路和特性 122
6.2 图划分理论 124
6.2.1 KL算法 124
6.2.2 几何划分算法 125
6.2.3 多级层次划分算法 126
6.3 基于谱聚类的算法 127
6.3.1 拉普拉斯矩阵 127
6.3.2 谱聚类算法概述 129
6.3.3 谱聚类算法的改进 135
6.4 SCAN类算法 139
6.4.1 SCAN算法 139
6.4.2 ppSCAN算法 140
6.5 深度图聚类 141
6.5.1 图神经网络 142
6.5.2 图卷积网络 144
6.5.3 自适应图卷积方法 147
6.5.4 不同输入图的处理 149
6.6 属性图的聚类 151
6.6.1 属性图聚类概述 151
6.6.2 边属性图聚类 152
6.6.3 顶点属性图聚类 153
6.7 以图为对象的聚类 154
第7章 图中的异常检测 156
7.1 异常检测概述 156
7.1.1 异常检测 156
7.1.2 面向图的异常检测 157
7.1.3 图异常检测方法概述 159
7.2 图异常检测算法 160
7.2.1 静态图异常检测 160
7.2.2 动态图异常检测 167
7.3 图异常检测系统 171
7.3.1 GraphRAD 171
7.3.2 Perseus系统 174
第8章 图缩减 176
8.1 图的缩减 176
8.1.1 有穷自动机的缩减 177
8.1.2 有向无环图的缩减 181
8.2 图摘要 184
8.2.1 基于分组的图摘要 185
8.2.2 动态图摘要 187
8.2.3 其他方法 187
8.3 图压缩 188
8.3.1 基于邻接矩阵的压缩 189
8.3.2 基于邻接表的压缩 191
8.3.3 基于形式化方法的压缩 194
8.4 图采样 197
8.4.1 随机图采样 197
8.4.2 基于特征的图采样 198