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