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

深入介绍图数据挖掘的算法原理和分布式实现
详述企业级图分析算法的极致性能优化
结合案例解析鲲鹏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