目 錄
第1章 大圖數(shù)據(jù)概述 1
1.1 引言 1
1.1.1 什么是圖 1
1.1.2 圖的基本概念 3
1.1.3 圖的存儲 6
1.1.4 大圖數(shù)據(jù) 7
1.1.5 圖與分布式計算 8
1.2 圖數(shù)據(jù)管理與分析中研究的問題 8
1.2.1 圖查詢 8
1.2.2 圖匹配 9
1.2.3 圖的社區(qū)檢測 9
1.2.4 圖模式挖掘 10
1.2.5 圖中的最短路徑 10
1.3 發(fā)展趨勢與展望 11
1.3.1 圖數(shù)據(jù)管理與分析面臨的挑戰(zhàn) 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 圖數(shù)據(jù)的分類 21
2.2 圖數(shù)據(jù)的基本操作 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章 圖計算系統(tǒng) 44
3.1 圖計算概述 44
3.1.1 圖計算與通用大數(shù)據(jù)處理系統(tǒng) 45
3.1.2 圖計算框架 46
3.1.3 圖計算的編程模型 50
3.1.4 圖計算系統(tǒng)中的語言 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 圖數(shù)據(jù)的稀疏矩陣組織 67
3.3.2 圖數(shù)據(jù)的劃分 68
3.3.3 圖數(shù)據(jù)劃分中的內存管理 69
3.2.4 頂點程序的調度 70
3.2.5 計算與通信模式 70
3.4 現(xiàn)代圖計算系統(tǒng) 71
3.4.1 單機內存 71
3.4.2 單機外存 72
3.4.3 多機內存 73
3.4.4 多機外存 73
3.4.5 動態(tài)圖計算系統(tǒng) 74
3.4.6 圖計算系統(tǒng)例析 74
3.5 圖計算的應用 78
3.5.1 傳統(tǒng)的圖計算應用 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圖相似度函數(shù) 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 圖查詢處理系統(tǒng)例析 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 啟發(fā)式算法 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 靜態(tài)圖異常檢測 160
7.2.2 動態(tài)圖異常檢測 167
7.3 圖異常檢測系統(tǒng) 171
7.3.1 GraphRAD 171
7.3.2 Perseus系統(tǒng) 174
第8章 圖縮減 176
8.1 圖的縮減 176
8.1.1 有窮自動機的縮減 177
8.1.2 有向無環(huán)圖的縮減 181
8.2 圖摘要 184
8.2.1 基于分組的圖摘要 185
8.2.2 動態(tài)圖摘要 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