基于鲲鹏的分布式图分析算法实战

本书全面、系统地介绍了单机和分布式图分析算法的理论基础、框架、实战应用等，侧重理论与实践相结合。在内容组织上，首先，本书整体介绍图分析技术的发展历程和现状，并分析图分析技术面临的挑战。其次，本书系统介绍了以下内容：单机图分析算法的基本原理、常用场景和基础解法；分布式图分析技术的关键步骤解析及调优策略指导；业界经典的大数据平台和主流的分布式开发框架，以及分布式图计算框架的运行机制和任务调度策略；结合工业界软硬件（鲲鹏芯片和鲲鹏BoostKit加速库）对分布式图分析算法进行调优的方法。最后，本书将分布式图分析技术应用于实际场景，帮助读者基于业务场景进行分布式图计算框架选型。 本书既可以帮助对大数据图分析算法感兴趣的读者了解典型图分析算法的原理与优化技术，也可以作为华为鲲鹏图分析算法框架下的实践参考书。

张志威，北京理工大学计算机学院教授，博士生导师，入选国家高层次人才计划。主持国家自然科学基金重点项目、科技部重点研发计划项目课题等多项国家与省部级科研项目。主要研究方向为大规模图数据管理与分析、分布式计算、数据湖、区块链等。在ACM SIGMOD、KDD、ICDE、VLDB..Journal等发表中国计算机学会（CCF）A类论文40余篇。多次担任ACM SIGMOD、VLDB、AAAI等国际学术会议程序委员会委员。 袁野，北京理工大学基础科学研究院院长，教授、博士生导师，国家杰青、优青基金获得者，CCF杰出会员，IEEE、ACM高级会员。主持国家自然科学基金重点项目，科技部重点研发项目等多项国家级科研项目。曾获国家科技进步二等奖，中国电子学会自然科学奖一等奖等多项省部级奖项。同时担任中国计算机学会（CCF）数据库专业委员会副主任、大数据专家委员会委员。曾作为香港科技大学、香港中文大学、英国爱丁堡大学访问学者。主要研究方向为大数据管理与分析。在ACM..SIGMOD、VLDB、ICDE、VLDB Journal、IEEE Trans. TKDE、IEEE Trans. TPDS等发表CCF A类论文100余篇。 曹莉，华为公司图分析算法专家，拥有近15年的图算法创新应用与研究经验，作为华为公司首个Spark分布式图分析算法专家，深入了解金融、互联网、交通、运营商、HPC等行业客户需求，带领团队构建了基于鲲鹏的大数据BoostKit图分析算法加速库，支持社团挖掘、中心性分析、路径分析、拓扑度量、相似性分析等典型40+算法，并在鲲鹏社区（hikunpeng）上线发布。

丛书序 前言 本书阅读导引 第1章　　图分析技术概述001 1.1　图分析技术的重要性002 1.1.1　发展脉络002 1.1.3　应用发展013 1.2　图分析技术体系015 1.2.1　图数据库技术015 1.2.2　图计算技术018 1.2.3　图学习技术021 1.2.4　图生成技术024 1.2.5　图可视化技术028 1.3　大数据背景下图分析技术面临的挑战030 第2章　　经典图算法033 2.1　路径分析034 2.1.1　最短路径算法034 2.1.2　环路检测算法041 2.2　社区挖掘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　度量统计063 2.4.1　三角形计数算法064 2.4.2　集聚系数算法066 2.5　相似性分析067 2.5.1　SimRank算法068 2.5.2　子图匹配算法069 第3章　　分布式图计算框架073 3.1　分布式大数据平台概述074 3.1.1　Hadoop074 3.1.2　Spark079 3.1.3　Flink082 3.1.4　小结085 3.2　分布式图计算框架核心技术086 3.2.1　编程模型086 3.2.2　通信模型088 3.2.3　执行模型090 3.2.4　计算模型091 3.2.5　图划分093 3.3　经典分布式图计算框架094 3.3.1　Pregel095 3.3.2　GraphLab096 3.3.3　GraphX098 3.3.4　Gemini099 3.4　分布式图计算的技术挑战100 第4章　　鲲鹏BoostKit图分析算法加速库103 4.1　鲲鹏芯片104 4.1.1　鲲鹏芯片的发展历程104 4.1.2　鲲鹏芯片的架构105 4.1.3　鲲鹏920的特性107 4.2　鲲鹏BoostKit概述108 4.2.1　鲲鹏应用使能套件BoostKit108 4.2.2　大数据使能套件111 4.3　鲲鹏BoostKit图分析算法加速库简介115 4.3.1　算法库概述115 4.3.2　算法加速库安装部署119 4.3.3　算法库集成开发125 4.3.4　算法库调测样例129 4.4　鲲鹏BoostKit图分析算法加速库调优指南131 4.4.1　平台侧调优131 4.4.2　资源侧调优133 4.4.3　算法侧调优136 第5章　　基于鲲鹏的分布式图分析算法优化实战139 5.1　环路检测算法140 5.1.1　分布式实现141 5.1.2　难点分析143 5.1.3　关键步骤与优化点解析145 5.1.4　鲲鹏BoostKit算法API介绍152 5.2　Louvain算法153 5.2.1　分布式实现154 5.2.2　难点分析157 5.2.3　关键步骤与优化点解析159 5.2.4　鲲鹏BoostKit算法API介绍165 5.3　Betweenness算法166 5.3.1　分布式实现167 5.3.2　难点分析171 5.3.3　关键步骤与优化点解析173 5.3.4　鲲鹏BoostKit算法API介绍177 5.4　PageRank算法179 5.4.1　分布式实现180 5.4.2　难点分析182 5.4.3　关键步骤与优化点解析183 5.4.4　鲲鹏BoostKit算法API介绍188 5.5　K-Core分解算法189 5.5.1　分布式实现191 5.5.2　难点分析193 5.5.3　关键步骤与优化点解析194 5.5.4　鲲鹏BoostKit算法API介绍199 5.6　子图匹配算法200 5.6.1　分布式实现200 5.6.2　难点分析204 5.6.3　关键步骤与优化点解析204 5.6.4　鲲鹏BoostKit算法API介绍207 第6章　　图分析算法应用实战211 6.1　网页搜索排名案例212 6.1.1　场景介绍212 6.1.2　整体方案213 6.1.3　关键步骤215 6.1.4　小结221 6.2　视频推荐案例222 6.2.1　场景介绍222 6.2.2　整体方案222 6.2.3　关键步骤224 6.2.4　小结229 6.3　金融风险识别案例230 6.3.1　场景介绍230 6.3.2　整体方案230 6.3.3　关键步骤232 6.3.4　小结240 参考文献241