大图数据管理与分析

本书第1章对大图数据的基本概念进行简要介绍, 为读者奠定大图数据管理与分析方面的理论基础; 第2章介绍图的结构与表征, 使读者有效定义图模型; 第3-8章对图计算系统、图相似与图查询、子图挖掘、图聚类、图中的异常检测和图缩减进行深入探讨, 以期为读者提供全面的大图数据管理与分析知识。

目 录 第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