序 xi
前言　xiii
第　1章 導論　1
1．1　何謂圖　1
1．2　何謂圖分析和圖算法　3
1．3　圖處理、圖數(shù)據(jù)庫、圖查詢和圖算法　5
1．4　為何要關心圖算法　6
1．5　圖分析用例　9
1．6　小結(jié)　10
第　2章 圖論及其概念　11
2．1　術(shù)語　11
2．2　圖的類型和結(jié)構(gòu)　12
2．3　圖的種類　14
2．3．1　連通圖與非連通圖　14
2．3．2　無權(quán)圖與加權(quán)圖　15
2．3．3　無向圖與有向圖　16
2．3．4　無環(huán)圖與有環(huán)圖　17
2．3．5　稀疏圖與稠密圖　18
2．3．6　單部圖、二部圖和k部圖　19
2．4　圖算法的類型　21
2．4．1　路徑查找　21
2．4．2　中心性　21
2．4．3　社團發(fā)現(xiàn)　22
2．5　小結(jié)　22
第3章　圖平臺和圖處理　23
3．1　圖平臺和圖處理的注意事項　23
3．1．1　平臺注意事項　23
3．1．2　處理注意事項　24
3．2　典型平臺　25
3．2．1　選擇平臺　25
3．2．2　Apache Spark　26
3．2．3　Neo4j圖平臺　28
3．3　小結(jié)　30
第4章　路徑查找算法和圖搜索算法　31
4．1　示例數(shù)據(jù)：交通圖　33
4．1．1　將數(shù)據(jù)導入Spark　35
4．1．2　將數(shù)據(jù)導入Neo4j　36
4．2　廣度優(yōu)先搜索　36
4．3　深度優(yōu)先搜索　38
4．4　最短路徑算法　40
4．4．1　何時使用最短路徑算法　41
4．4．2　使用Neo4j實現(xiàn)最短路徑算法　41
4．4．3　使用Neo4j實現(xiàn)加權(quán)最短路徑算法　43
4．4．4　使用Spark實現(xiàn)加權(quán)最短路徑算法　44
4．4．5　最短路徑算法的變體：A*算法　46
4．4．6　最短路徑算法的變體：Yen的k最短路徑算法　48
4．5　所有點對最短路徑算法　49
4．5．1　近觀所有點對最短路徑算法　50
4．5．2　何時使用所有點對最短路徑算法　51
4．5．3　使用Spark實現(xiàn)所有點對最短路徑算法　51
4．5．4　使用Neo4j實現(xiàn)所有點對最短路徑算法　52
4．6　單源最短路徑算法　53
4．6．1　何時使用單源最短路徑算法　54
4．6．2　使用Spark實現(xiàn)單源最短路徑算法　55
4．6．3　使用Neo4j實現(xiàn)單源最短路徑算法　57
4．7　最小生成樹算法　57
4．7．1　何時使用最小生成樹算法　58
4．7．2　使用Neo4j實現(xiàn)最小生成樹算法　59
4．8　隨機游走算法　61
4．8．1　何時使用隨機游走算法　61
4．8．2　使用Neo4j實現(xiàn)隨機游走算法　61
4．9　小結(jié)　63
第5章　中心性算法　64
5．1　示例數(shù)據(jù)：社交圖　66
5．1．1　將數(shù)據(jù)導入Spark　67
5．1．2　將數(shù)據(jù)導入Neo4j　67
5．2　度中心性算法　68
5．2．1　可達性　68
5．2．2　何時使用度中心性算法　69
5．2．3　使用Spark實現(xiàn)度中心性算法　69
5．3　接近中心性算法　70
5．3．1　何時使用接近中心性算法　71
5．3．2　使用Spark實現(xiàn)接近中心性算法　72
5．3．3　使用Neo4j實現(xiàn)接近中心性算法　74
5．3．4　接近中心性算法變體：Wasserman & Faust算法　75
5．3．5　接近中心性算法變體：調(diào)和中心性算法　77
5．4　中間中心性算法　78
5．4．1　橋與控制點　78
5．4．2　計算中間中心性得分　79
5．4．3　何時使用中間中心性算法　79
5．4．4　使用Neo4j實現(xiàn)中間中心性算法　80
5．4．5　中間中心性算法變體：RA-Brandes算法　82
5．5　PageRank算法　83
5．5．1　影響力　84
5．5．2　PageRank算法公式　84
5．5．3　迭代、隨機沖浪者和等級沉沒　85
5．5．4　何時使用PageRank算法　86
5．5．5　使用Spark實現(xiàn)PageRank算法　87
5．5．6　使用Neo4j實現(xiàn)PageRank算法　88
5．5．7　PageRank算法變體：個性化PageRank算法　90
5．6　小結(jié)　91
第6章　社團發(fā)現(xiàn)算法　92
6．1　示例數(shù)據(jù)：軟件依賴圖　94
6．1．1　將數(shù)據(jù)導入Spark　96
6．1．2　將數(shù)據(jù)導入Neo4j　97
6．2　三角形計數(shù)和聚類系數(shù)　97
6．2．1　局部聚類系數(shù)　97
6．2．2　全局聚類系數(shù)　98
6．2．3　何時使用三角形計數(shù)和聚類系數(shù)　98
6．2．4　使用Spark實現(xiàn)三角形計數(shù)算法　99
6．2．5　使用Neo4j實現(xiàn)三角形計數(shù)算法　99
6．2．6　使用Neo4j計算局部聚類系數(shù)　100
6．3　強連通分量算法　101
6．3．1　何時使用強連通分量算法　102
6．3．2　使用Spark實現(xiàn)強連通分量算法　102
6．3．3　使用Neo4j實現(xiàn)強連通分量算法　103
6．4　連通分量算法　106
6．4．1　何時使用連通分量算法　106
6．4．2　使用Spark實現(xiàn)連通分量算法　106
6．4．3　使用Neo4j實現(xiàn)連通分量算法　107
6．5　標簽傳播算法　108
6．5．1　半監(jiān)督學習和種子標簽　110
6．5．2　何時使用標簽傳播算法　110
6．5．3　使用Spark實現(xiàn)標簽傳播算法　110
6．5．4　使用Neo4j實現(xiàn)標簽傳播算法　111
6．6　Louvain模塊度算法　113
6．6．1　通過模塊度進行基于質(zhì)量的分組　114
6．6．2　何時使用Louvain模塊度算法　117
6．6．3　使用Neo4j實現(xiàn)Louvain模塊度算法　118
6．7　驗證社團　122
6．8　小結(jié)　122
第7章　圖算法實戰(zhàn)　123
7．1　使用Neo4j分析Yelp數(shù)據(jù)　123
7．1．1　Yelp社交網(wǎng)絡　124
7．1．2　導入數(shù)據(jù)　124
7．1．3　圖模型　125
7．1．4　Yelp數(shù)據(jù)概覽　125
7．1．5　行程規(guī)劃應用程序　129
7．1．6　旅游商務咨詢　134
7．1．7　查找相似類別　138
7．2　使用Spark分析航班數(shù)據(jù)　142
7．2．1　探索性分析　144
7．2．2　熱門機場　144
7．2．3　源自ORD的延誤　145
7．2．4　SFO的糟糕一天　147
7．2．5　通過航空公司互連的機場　149
7．3　小結(jié)　154
第8章　使用圖算法增強機器學習　155
8．1　機器學習和上下文的重要性　155
8．2　關聯(lián)特征提取與特征選擇　157
8．2．1　圖特征　158
8．2．2　圖算法特征　158
8．3　圖與機器學習實踐：鏈接預測　160
8．3．1　工具和數(shù)據(jù)　161
8．3．2　將數(shù)據(jù)導入Neo4j　162
8．3．3　合著者關系圖　163
8．3．4　創(chuàng)建均衡的訓練數(shù)據(jù)集和測試數(shù)據(jù)集　164
8．3．5　如何預測缺失鏈接　169
8．3．6　創(chuàng)建機器學習管道　170
8．3．7　預測鏈接：基本圖特征　171
8．3．8　預測鏈接：三角形和聚類系數(shù)　181
8．3．9　預測鏈接：社團發(fā)現(xiàn)　184
8．4　小結(jié)　190
8．5　總結(jié)　190
附錄　額外信息及資料　191
關于作者　195
關于封面　195