目 錄
第1章 大圖數(shù)據(jù)概述 1
1.1 引言 1
1.1.1 什么是圖 1
1.1.2 圖的基本概念 3
1.1.3 圖的存儲(chǔ) 6
1.1.4 大圖數(shù)據(jù) 7
1.1.5 圖與分布式計(jì)算 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 總結(jié) 17
第2章 圖的結(jié)構(gòu)與表征 18
2.1 圖的結(jié)構(gòu)和模型 18
2.1.1 圖的基本結(jié)構(gòu) 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 隨機(jī)游走 26
2.2.3 PageRank 31
2.3 圖結(jié)構(gòu)表征 34
2.3.1 結(jié)構(gòu)一致性 35
2.3.2 Struc2vec 35
2.3.3 node2vec 38
2.3.4 LINE 40
2.3.5 圖自編碼器 41
第3章 圖計(jì)算系統(tǒng) 44
3.1 圖計(jì)算概述 44
3.1.1 圖計(jì)算與通用大數(shù)據(jù)處理系統(tǒng) 45
3.1.2 圖計(jì)算框架 46
3.1.3 圖計(jì)算的編程模型 50
3.1.4 圖計(jì)算系統(tǒng)中的語言 52
3.2 圖計(jì)算模型 53
3.2.1 頂點(diǎn)中心計(jì)算模型 53
3.2.2 GAS計(jì)算模型 58
3.2.3 邊中心計(jì)算模型 60
3.2.4 路徑中心計(jì)算模型 61
3.2.5 子圖中心計(jì)算模型 64
3.3 關(guān)鍵技術(shù) 67
3.3.1 圖數(shù)據(jù)的稀疏矩陣組織 67
3.3.2 圖數(shù)據(jù)的劃分 68
3.3.3 圖數(shù)據(jù)劃分中的內(nèi)存管理 69
3.2.4 頂點(diǎn)程序的調(diào)度 70
3.2.5 計(jì)算與通信模式 70
3.4 現(xiàn)代圖計(jì)算系統(tǒng) 71
3.4.1 單機(jī)內(nèi)存 71
3.4.2 單機(jī)外存 72
3.4.3 多機(jī)內(nèi)存 73
3.4.4 多機(jī)外存 73
3.4.5 動(dòng)態(tài)圖計(jì)算系統(tǒng) 74
3.4.6 圖計(jì)算系統(tǒng)例析 74
3.5 圖計(jì)算的應(yīng)用 78
3.5.1 傳統(tǒng)的圖計(jì)算應(yīng)用 78
3.5.2 新興的圖計(jì)算應(yīng)用 79
第4章 圖相似與圖查詢 82
4.1 圖的相似性 82
4.2 圖匹配 82
4.2.1 圖的同構(gòu) 83
4.2.2 子圖同構(gòu) 84
4.2.3 圖編輯距離 86
4.2.4 DELTACON圖相似度函數(shù) 88
4.2.5 圖匹配算法 89
4.2.6 圖匹配在生物信息領(lǐng)域的應(yīng)用 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 譜聚類算法的改進(jìn) 135
6.4 SCAN類算法 139
6.4.1 SCAN算法 139
6.4.2 ppSCAN算法 140
6.5 深度圖聚類 141
6.5.1 圖神經(jīng)網(wǎng)絡(luò) 142
6.5.2 圖卷積網(wǎng)絡(luò) 144
6.5.3 自適應(yīng)圖卷積方法 147
6.5.4 不同輸入圖的處理 149
6.6 屬性圖的聚類 151
6.6.1 屬性圖聚類概述 151
6.6.2 邊屬性圖聚類 152
6.6.3 頂點(diǎn)屬性圖聚類 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 動(dòng)態(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 有窮自動(dòng)機(jī)的縮減 177
8.1.2 有向無環(huán)圖的縮減 181
8.2 圖摘要 184
8.2.1 基于分組的圖摘要 185
8.2.2 動(dòng)態(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 隨機(jī)圖采樣 197
8.4.2 基于特征的圖采樣 198