圖算法：行業(yè)應(yīng)用與實(shí)踐

Contents　目　　錄
前言
第1章　圖思維方式 1
1.1　什么是圖 1
1.1.1　人類到底是如何思考的 2
1.1.2　由一道面試題引發(fā)的思考 6
1.2　圖論與圖計(jì)算 10
1.2.1　圖論及其發(fā)展史 10
1.2.2　圖計(jì)算概述 15
第2章　圖算法基礎(chǔ) 22
2.1　圖算法的分類 23
2.2　圖分析與數(shù)據(jù)科學(xué) 30
第3章　如何評(píng)估圖算法的效率 38
3.1　什么是算法效率 38
3.2　查詢模式、數(shù)據(jù)結(jié)構(gòu)和計(jì)算效率 40
3.2.1　查詢模式 41
3.2.2　數(shù)據(jù)結(jié)構(gòu)與計(jì)算效率 46
3.3　并發(fā)設(shè)計(jì)與加速 58
第4章　中心性算法 67
4.1　節(jié)點(diǎn)度中心性 67
4.1.1　算法歷史和原理 67
4.1.2　算法復(fù)雜度與算法參數(shù) 70
4.1.3　行業(yè)應(yīng)用：零售信貸消費(fèi)預(yù)測 71
4.2　接近中心性 72
4.2.1　算法歷史和原理 72
4.2.2　算法復(fù)雜度與算法參數(shù) 74
4.2.3　行業(yè)應(yīng)用：功能性場所選址 75
4.3　中介中心性 76
4.3.1　算法歷史和原理 76
4.3.2　算法復(fù)雜度與算法參數(shù) 78
4.3.3　行業(yè)應(yīng)用：交通樞紐評(píng)估 79
4.4　網(wǎng)頁排名 79
4.4.1　算法歷史和原理 79
4.4.2　算法復(fù)雜度與算法參數(shù) 82
4.4.3　行業(yè)應(yīng)用：互聯(lián)網(wǎng)網(wǎng)頁排名 82
4.5　虛假賬號(hào)排名 83
4.5.1　算法歷史和原理 83
4.5.2　算法復(fù)雜度與算法參數(shù) 85
4.5.3　行業(yè)應(yīng)用：社交網(wǎng)絡(luò)惡意賬號(hào)
　　　識(shí)別 85
第5章　相似度算法 86
5.1　杰卡德相似度 86
5.1.1　算法歷史和原理 86
5.1.2　算法復(fù)雜度與算法參數(shù) 88
5.1.3　行業(yè)應(yīng)用：度量學(xué)習(xí)模型的預(yù)測
　　　準(zhǔn)確性 89
5.2　重疊相似度 89
5.2.1　算法歷史和原理 89
5.2.2　算法復(fù)雜度與算法參數(shù) 90
5.2.3　行業(yè)應(yīng)用：文本相似度比較 91
5.3　余弦相似度 92
5.3.1　算法歷史和原理 92
5.3.2　算法復(fù)雜度與算法參數(shù) 94
5.3.3　行業(yè)應(yīng)用：人臉識(shí)別 95
5.4　歐幾里得距離 95
5.4.1　算法歷史和原理 95
5.4.2　算法復(fù)雜度與算法參數(shù) 97
5.4.3　行業(yè)應(yīng)用：異常檢測 97
5.5　皮爾森相關(guān)系數(shù) 98
5.5.1　算法歷史和原理 98
5.5.2　算法復(fù)雜度與算法參數(shù) 99
5.5.3　行業(yè)應(yīng)用：構(gòu)建相關(guān)性網(wǎng)絡(luò) 99
第6章　連通性和緊密度算法 101
6.1　全圖k鄰 101
6.1.1　算法歷史和原理 101
6.1.2　算法復(fù)雜度與算法參數(shù) 105
6.1.3　行業(yè)應(yīng)用：企業(yè)影響力分析
　　?。üど毯凸?yīng)鏈圖譜） 106
6.2　三角形計(jì)算 109
6.2.1　算法歷史和原理 109
6.2.2　算法復(fù)雜度與算法參數(shù) 113
6.2.3　行業(yè)應(yīng)用：社交網(wǎng)絡(luò)緊密性 114
6.3　二分圖 115
6.3.1　算法歷史和原理 115
6.3.2　算法復(fù)雜度與算法參數(shù) 120
6.3.3　行業(yè)應(yīng)用：地圖著色問題 121
6.4　連通分量 122
6.4.1　算法歷史和原理 122
6.4.2　算法復(fù)雜度與算法參數(shù) 128
6.4.3　行業(yè)應(yīng)用：中繼器網(wǎng)絡(luò)安全系數(shù)
　　　計(jì)算 128
6.5　最小生成樹 129
6.5.1　算法歷史和原理 129
6.5.2　算法復(fù)雜度與算法參數(shù) 134
6.5.3　行業(yè)應(yīng)用：電力、網(wǎng)絡(luò)線路
　　　規(guī)劃 135
第7章　傳播與分類算法 137
7.1　標(biāo)簽傳播 137
7.1.1　算法歷史和原理 137
7.1.2　算法復(fù)雜度與算法參數(shù) 142
7.1.3　行業(yè)應(yīng)用：社交網(wǎng)絡(luò)用戶興趣
　　　分類 143
7.2　k最近鄰 144
7.2.1　算法歷史和原理 144
7.2.2　算法復(fù)雜度與算法參數(shù) 148
7.2.3　行業(yè)應(yīng)用：手寫識(shí)別與離群點(diǎn)
　　　檢測 149
7.3　k均值 150
7.3.1　算法歷史和原理 150
7.3.2　算法復(fù)雜度與算法參數(shù) 153
7.3.3　行業(yè)應(yīng)用：基于向量聚類的圖像
　　　顏色縮減 153
7.4　魯汶識(shí)別 154
7.4.1　算法歷史和原理 154
7.4.2　算法復(fù)雜度與算法參數(shù) 159
7.4.3　行業(yè)應(yīng)用：用戶社交關(guān)系
　　　分類 159
第8章　拓?fù)滏溄宇A(yù)測算法 161
8.1　基于節(jié)點(diǎn)低階相似性 163
8.1.1　共同鄰居 163
8.1.2　AA指標(biāo) 164
8.1.3　資源分配 166
8.1.4　優(yōu)先連接 168
8.2　基于節(jié)點(diǎn)高階相似性 170
8.2.1　最短距離 170
8.2.2　Katz指標(biāo) 172
8.2.3　重啟型隨機(jī)游走 174
8.2.4　SimRank指標(biāo) 177
8.3　行業(yè)應(yīng)用：推薦系統(tǒng) 180
第9章　圖嵌入算法 182
9.1　圖嵌入的目的 182
9.2　基于隨機(jī)游走 186
9.2.1　隨機(jī)游走概述 187
9.2.2　Skip-gram模型 191
9.2.3　負(fù)采樣 196
9.2.4　損失函數(shù) 198
9.3　基于圖神經(jīng)網(wǎng)絡(luò) 200
9.3.1　圖神經(jīng)網(wǎng)絡(luò)概述 200
9.3.2　圖卷積網(wǎng)絡(luò) 201
9.3.3　GraphSAGE 207
9.4　行業(yè)應(yīng)用：藥物不良反應(yīng)預(yù)測 210
第10章　圖算法實(shí)戰(zhàn) 212
10.1　在流動(dòng)性風(fēng)險(xiǎn)管理中的創(chuàng)新
　　　應(yīng)用 213
10.1.1　應(yīng)用背景概述 214
10.1.2　傳