基于鯤鵬的分布式圖分析算法實(shí)戰(zhàn) 張志威 袁野 曹莉
定 價(jià):99 元
- 作者:張志威 袁野 曹莉
- 出版時(shí)間:2024/10/1
- ISBN:9787111760276
- 出 版 社:機(jī)械工業(yè)出版社
- 中圖法分類:
- 頁(yè)碼:
- 紙張:膠版紙
- 版次:
- 開(kāi)本:16開(kāi)
本書(shū)全面、系統(tǒng)地介紹了單機(jī)和分布式圖分析算法的理論基礎(chǔ)、框架、實(shí)戰(zhàn)應(yīng)用等,側(cè)重理論與實(shí)踐相結(jié)合。在內(nèi)容組織上,首先,本書(shū)整體介紹圖分析技術(shù)的發(fā)展歷程和現(xiàn)狀,并分析圖分析技術(shù)面臨的挑戰(zhàn)。其次,本書(shū)系統(tǒng)介紹了以下內(nèi)容:?jiǎn)螜C(jī)圖分析算法的基本原理、常用場(chǎng)景和基礎(chǔ)解法;分布式圖分析技術(shù)的關(guān)鍵步驟解析及調(diào)優(yōu)策略指導(dǎo);業(yè)界經(jīng)典的大數(shù)據(jù)平臺(tái)和主流的分布式開(kāi)發(fā)框架,以及分布式圖計(jì)算框架的運(yùn)行機(jī)制和任務(wù)調(diào)度策略;結(jié)合工業(yè)界軟硬件(鯤鵬芯片和鯤鵬BoostKit加速庫(kù))對(duì)分布式圖分析算法進(jìn)行調(diào)優(yōu)的方法。最后,本書(shū)將分布式圖分析技術(shù)應(yīng)用于實(shí)際場(chǎng)景,幫助讀者基于業(yè)務(wù)場(chǎng)景進(jìn)行分布式圖計(jì)算框架選型。
本書(shū)既可以幫助對(duì)大數(shù)據(jù)圖分析算法感興趣的讀者了解典型圖分析算法的原理與優(yōu)化技術(shù),也可以作為華為鯤鵬圖分析算法框架下的實(shí)踐參考書(shū)。
深入介紹圖數(shù)據(jù)挖掘的算法原理和分布式實(shí)現(xiàn)
詳述企業(yè)級(jí)圖分析算法的極致性能優(yōu)化
結(jié)合案例解析鯤鵬BoostKit大數(shù)據(jù)圖分析算法庫(kù)實(shí)戰(zhàn)應(yīng)用
隨著大數(shù)據(jù)時(shí)代的到來(lái),圖數(shù)據(jù)規(guī)模呈爆炸式增長(zhǎng)。圖數(shù)據(jù)作為一種刻畫(huà)實(shí)體間關(guān)聯(lián)關(guān)系的數(shù)據(jù)模型,具有極強(qiáng)的多元關(guān)系表達(dá)能力,其蘊(yùn)含的價(jià)值在科學(xué)研究、制造業(yè)、金融、互聯(lián)網(wǎng)等諸多領(lǐng)域產(chǎn)生了巨大影響。近年來(lái),對(duì)圖數(shù)據(jù)的分析、挖掘得到了工業(yè)界與學(xué)術(shù)界的廣泛關(guān)注。
華為公司自主研發(fā)設(shè)計(jì)的鯤鵬高性能處理器不斷演進(jìn),其高性能、低功耗、高集成、高吞吐的特性給圖數(shù)據(jù)分析注入了新的活力。然而,機(jī)遇與挑戰(zhàn)并存,圖數(shù)據(jù)存在規(guī)模巨大、關(guān)聯(lián)數(shù)據(jù)復(fù)雜以及類型多樣等諸多特點(diǎn),這些特點(diǎn)對(duì)大規(guī)模圖數(shù)據(jù)的分析與挖掘提出了新的挑戰(zhàn)。例如,如何面向高性能硬件特性設(shè)計(jì)高效的分布式圖分析算法以解決分布式圖分析并行難、通信代價(jià)高、計(jì)算復(fù)雜度高等問(wèn)題,如何通過(guò)圖分析算法選型構(gòu)建高可用的圖分析應(yīng)用以應(yīng)對(duì)復(fù)雜多樣的業(yè)務(wù)需求。
正是由于長(zhǎng)期共同的研究興趣,我們與華為公司的領(lǐng)域?qū)<议_(kāi)展了圖算法優(yōu)化的相關(guān)研究。也正是由于這樣的契機(jī),我們有幸合作撰寫(xiě)了本書(shū)。這也給我們提供了一個(gè)全面且系統(tǒng)地將研究成果與實(shí)踐相結(jié)合的機(jī)會(huì),由衷感謝華為公司的信任和支持。本書(shū)針對(duì)大規(guī)模圖數(shù)據(jù)分析算法,介紹圖分析算法的算法原理與優(yōu)化技術(shù),以及在華為鯤鵬等分布式圖分析框架下的應(yīng)用實(shí)踐。針對(duì)大規(guī)模圖數(shù)據(jù)的特點(diǎn)與挑戰(zhàn),本書(shū)將以分布式圖算法為切入點(diǎn),介紹大規(guī)模圖數(shù)據(jù)算法在數(shù)據(jù)結(jié)構(gòu)選擇、硬件環(huán)境適配、計(jì)算開(kāi)銷等方面的特定優(yōu)化。部分優(yōu)化方法在實(shí)踐中,特別是在大圖數(shù)據(jù)分析任務(wù)中可將性能提升超過(guò)兩個(gè)數(shù)量級(jí)。因此,本書(shū)既可以幫助對(duì)大數(shù)據(jù)圖分析算法感興趣的讀者了解典型圖分析算法的原理與優(yōu)化技術(shù),也可以作為華為鯤鵬圖分析算法框架下的實(shí)踐參考。
在此,衷心感謝為本書(shū)內(nèi)容做出重要貢獻(xiàn)的喬鵬鵬、趙帥、李逸文、王欣洲、苗壯、崔博遠(yuǎn)、鄒媛婷、趙影、王朝陽(yáng)、程果、曹夢(mèng)婕同學(xué);衷心感謝華為公司計(jì)算產(chǎn)品線算法專家王工藝對(duì)本書(shū)的大力支持;衷心感謝華為公司俞麗君、李子健兩位老師對(duì)本書(shū)內(nèi)容提出的意見(jiàn)與建議,并在撰寫(xiě)過(guò)程中與我們并肩作戰(zhàn);同時(shí)也感謝華為公司參與本書(shū)審讀工作的各位老師,包括弋飛、周亭亭、張言哲、陳偉、鐘韜、韓慶森、楊勇、耿雪萍。
因作者水平有限,本書(shū)難免存在不足及疏漏,歡迎各位讀者批評(píng)指正。
張志威,北京理工大學(xué)計(jì)算機(jī)學(xué)院教授,博士生導(dǎo)師,入選國(guó)家高層次人才計(jì)劃。主持國(guó)家自然科學(xué)基金重點(diǎn)項(xiàng)目、科技部重點(diǎn)研發(fā)計(jì)劃項(xiàng)目課題等多項(xiàng)國(guó)家與省部級(jí)科研項(xiàng)目。主要研究方向?yàn)榇笠?guī)模圖數(shù)據(jù)管理與分析、分布式計(jì)算、數(shù)據(jù)湖、區(qū)塊鏈等。在ACM SIGMOD、KDD、ICDE、VLDB..Journal等發(fā)表中國(guó)計(jì)算機(jī)學(xué)會(huì)(CCF)A類論文40余篇。多次擔(dān)任ACM SIGMOD、VLDB、AAAI等國(guó)際學(xué)術(shù)會(huì)議程序委員會(huì)委員。
袁野,北京理工大學(xué)基礎(chǔ)科學(xué)研究院院長(zhǎng),教授、博士生導(dǎo)師,國(guó)家杰青、優(yōu)青基金獲得者,CCF杰出會(huì)員,IEEE、ACM高級(jí)會(huì)員。主持國(guó)家自然科學(xué)基金重點(diǎn)項(xiàng)目,科技部重點(diǎn)研發(fā)項(xiàng)目等多項(xiàng)國(guó)家級(jí)科研項(xiàng)目。曾獲國(guó)家科技進(jìn)步二等獎(jiǎng),中國(guó)電子學(xué)會(huì)自然科學(xué)獎(jiǎng)一等獎(jiǎng)等多項(xiàng)省部級(jí)獎(jiǎng)項(xiàng)。同時(shí)擔(dān)任中國(guó)計(jì)算機(jī)學(xué)會(huì)(CCF)數(shù)據(jù)庫(kù)專業(yè)委員會(huì)副主任、大數(shù)據(jù)專家委員會(huì)委員。曾作為香港科技大學(xué)、香港中文大學(xué)、英國(guó)愛(ài)丁堡大學(xué)訪問(wèn)學(xué)者。主要研究方向?yàn)榇髷?shù)據(jù)管理與分析。在ACM..SIGMOD、VLDB、ICDE、VLDB Journal、IEEE Trans. TKDE、IEEE Trans. TPDS等發(fā)表CCF A類論文100余篇。
曹莉,華為公司圖分析算法專家,擁有近15年的圖算法創(chuàng)新應(yīng)用與研究經(jīng)驗(yàn),作為華為公司首個(gè)Spark分布式圖分析算法專家,深入了解金融、互聯(lián)網(wǎng)、交通、運(yùn)營(yíng)商、HPC等行業(yè)客戶需求,帶領(lǐng)團(tuán)隊(duì)構(gòu)建了基于鯤鵬的大數(shù)據(jù)BoostKit圖分析算法加速庫(kù),支持社團(tuán)挖掘、中心性分析、路徑分析、拓?fù)涠攘、相似性分析等典?0+算法,并在鯤鵬社區(qū)(hikunpeng)上線發(fā)布。
叢書(shū)序
前言
本書(shū)閱讀導(dǎo)引
第1章 圖分析技術(shù)概述001
1.1 圖分析技術(shù)的重要性002
1.1.1 發(fā)展脈絡(luò)002
1.1.3 應(yīng)用發(fā)展013
1.2 圖分析技術(shù)體系015
1.2.1 圖數(shù)據(jù)庫(kù)技術(shù)015
1.2.2 圖計(jì)算技術(shù)018
1.2.3 圖學(xué)習(xí)技術(shù)021
1.2.4 圖生成技術(shù)024
1.2.5 圖可視化技術(shù)028
1.3 大數(shù)據(jù)背景下圖分析技術(shù)面臨的挑戰(zhàn)030
第2章 經(jīng)典圖算法033
2.1 路徑分析034
2.1.1 最短路徑算法034
2.1.2 環(huán)路檢測(cè)算法041
2.2 社區(qū)挖掘046
2.2.1 連通分量算法046
2.2.2 Louvain算法049
2.3 中心性分析052
2.3.1 Betweenness算法052
2.3.2 K-Core分解算法060
2.4 度量統(tǒng)計(jì)063
2.4.1 三角形計(jì)數(shù)算法064
2.4.2 集聚系數(shù)算法066
2.5 相似性分析067
2.5.1 SimRank算法068
2.5.2 子圖匹配算法069
第3章 分布式圖計(jì)算框架073
3.1 分布式大數(shù)據(jù)平臺(tái)概述074
3.1.1 Hadoop074
3.1.2 Spark079
3.1.3 Flink082
3.1.4 小結(jié)085
3.2 分布式圖計(jì)算框架核心技術(shù)086
3.2.1 編程模型086
3.2.2 通信模型088
3.2.3 執(zhí)行模型090
3.2.4 計(jì)算模型091
3.2.5 圖劃分093
3.3 經(jīng)典分布式圖計(jì)算框架094
3.3.1 Pregel095
3.3.2 GraphLab096
3.3.3 GraphX098
3.3.4 Gemini099
3.4 分布式圖計(jì)算的技術(shù)挑戰(zhàn)100
第4章 鯤鵬BoostKit圖分析算法加速庫(kù)103
4.1 鯤鵬芯片104
4.1.1 鯤鵬芯片的發(fā)展歷程104
4.1.2 鯤鵬芯片的架構(gòu)105
4.1.3 鯤鵬920的特性107
4.2 鯤鵬BoostKit概述108
4.2.1 鯤鵬應(yīng)用使能套件BoostKit108
4.2.2 大數(shù)據(jù)使能套件111
4.3 鯤鵬BoostKit圖分析算法加速庫(kù)簡(jiǎn)介115
4.3.1 算法庫(kù)概述115
4.3.2 算法加速庫(kù)安裝部署119
4.3.3 算法庫(kù)集成開(kāi)發(fā)125
4.3.4 算法庫(kù)調(diào)測(cè)樣例129
4.4 鯤鵬BoostKit圖分析算法加速庫(kù)調(diào)優(yōu)指南131
4.4.1 平臺(tái)側(cè)調(diào)優(yōu)131
4.4.2 資源側(cè)調(diào)優(yōu)133
4.4.3 算法側(cè)調(diào)優(yōu)136
第5章 基于鯤鵬的分布式圖分析算法優(yōu)化實(shí)戰(zhàn)139
5.1 環(huán)路檢測(cè)算法140
5.1.1 分布式實(shí)現(xiàn)141
5.1.2 難點(diǎn)分析143
5.1.3 關(guān)鍵步驟與優(yōu)化點(diǎn)解析145
5.1.4 鯤鵬BoostKit算法API介紹152
5.2 Louvain算法153
5.2.1 分布式實(shí)現(xiàn)154
5.2.2 難點(diǎn)分析157
5.2.3 關(guān)鍵步驟與優(yōu)化點(diǎn)解析159
5.2.4 鯤鵬BoostKit算法API介紹165
5.3 Betweenness算法166
5.3.1 分布式實(shí)現(xiàn)167
5.3.2 難點(diǎn)分析171
5.3.3 關(guān)鍵步驟與優(yōu)化點(diǎn)解析173
5.3.4 鯤鵬BoostKit算法API介紹177
5.4 PageRank算法179
5.4.1 分布式實(shí)現(xiàn)180
5.4.2 難點(diǎn)分析182
5.4.3 關(guān)鍵步驟與優(yōu)化點(diǎn)解析183
5.4.4 鯤鵬BoostKit算法API介紹188
5.5 K-Core分解算法189
5.5.1 分布式實(shí)現(xiàn)191
5.5.2 難點(diǎn)分析193
5.5.3 關(guān)鍵步驟與優(yōu)化點(diǎn)解析194
5.5.4 鯤鵬BoostKit算法API介紹199
5.6 子圖匹配算法200
5.6.1 分布式實(shí)現(xiàn)200
5.6.2 難點(diǎn)分析204
5.6.3 關(guān)鍵步驟與優(yōu)化點(diǎn)解析204
5.6.4 鯤鵬BoostKit算法API介紹207
第6章 圖分析算法應(yīng)用實(shí)戰(zhàn)211
6.1 網(wǎng)頁(yè)搜索排名案例212
6.1.1 場(chǎng)景介紹212
6.1.2 整體方案213
6.1.3 關(guān)鍵步驟215
6.1.4 小結(jié)221
6.2 視頻推薦案例222
6.2.1 場(chǎng)景介紹222
6.2.2 整體方案222
6.2.3 關(guān)鍵步驟224
6.2.4 小結(jié)229
6.3 金融風(fēng)險(xiǎn)識(shí)別案例230
6.3.1 場(chǎng)景介紹230
6.3.2 整體方案230
6.3.3 關(guān)鍵步驟232
6.3.4 小結(jié)240
參考文獻(xiàn)241