人工智能之图计算

报告摘要

图计算是一种基于图数据结构的分析技术，能够高效地处理大规模图数据。它在人工智能领域扮演着使能技术的角色，尤其在社交网络分析、语义 Web 分析、生物信息网络分析、自然语言处理等新兴领域具有重要应用价值。

图计算系统是专门针对图结构数据进行处理的系统，具有高性能、可扩展性以及容错机制等关键特征。随着图数据量的指数级增长，传统的单机处理模式和分布式大数据平台如 MapReduce、Spark 已经无法满足需求，因此可扩展的分布式图计算系统成为研究热点。

图计算特征：
- 基于图抽象的数据模型，能够表达复杂的关联关系。
- 图数据模型并行抽象，支持高效的并行计算。
- 图模型系统优化，包括数据划分、负载均衡和内存管理等。
图计算系统分类：
- 单机内存图处理系统：如 Ligra、GraphMat、Polymer 等，适用于小规模图处理。
- 单机外存图处理系统：如 GraphChi、X-Stream、GridGraph 等，利用外存扩展图处理能力。
- 分布式内存图处理系统：如 Pregel、GraphLab、PowerGraph、GraphX、Gemini 等，支持大规模图计算。
- 分布式外存图处理系统：如 Chaos，支持万亿级边的图处理。
图计算面临的挑战：
- 局部性差：图结构通常不规则，影响缓存效率。
- 数据及图结构驱动的计算：图算法依赖于图结构，难以统一处理。
- 非结构化特性：图数据难以有效划分，影响存储、通信和计算的负载均衡。
- 高访存/计算比：计算过程需要多次迭代，导致高 I/O 开销。
图算法与框架：
- 典型图算法包括 PageRank、最短路径、社区发现等。
- 图计算框架如 Pregel、GraphLab、PowerGraph、GraphX、Gemini 等，各有其优化策略。

Pregel: A System for Large-Scale Graph Processing (2010)
Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud (2012)
PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs (2012)
GraphX: Graph Processing in a Distributed Dataflow Framework (2014)
X-Stream: Edge-Centric Graph Processing Using Streaming Partitions (2013)
Ligra: A Lightweight Graph Processing Framework for Shared Memory (2013)
PowerLyra: Differentiated Graph Computation and Partitioning on Skewed Graphs (2015)
GridGraph: Large-Scale Graph Processing on a Single Machine Using 2-Level Hierarchical Partitioning (2015)

全球图计算学者分布：主要集中于北美洲，其次为亚洲和欧洲西部。
中国学者分布：集中在长三角、珠三角和京津冀等沿海地区，内陆学者主要分布在华北及东北地区。
学者迁徙情况：美国为图计算人才流动的主要地区，中国、印度等国也存在一定的迁徙。
h-index分布：全球图计算学者的平均 h-index 为 21，其中 61.97% 的学者 h-index 低于平均值，仅 6.99% 的学者 h-index ≥ 60。
性别比：男性学者占比 96.31%，女性学者仅占 3.69%。