大圖數據管理與分析

圖不僅被當成建模工具使用，而且是一種應用廣泛的數據結構。如何高效地管理和挖掘大圖數據成為具有挑戰性的問題。本書將面向大圖數據介紹與大圖數據的管理、分析相關的理論和技術，特別是最新的研究成果。 本書第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