图状矩阵数据结构之简介

图（graph）是用于表示对象之间联结关系的抽象数据结构，通常使用顶点（vertex）集和边（edge）集进行描述：顶点表示对象，边表示对象之间的关系。根据边是否有方向和权值，图又可细分为有向图/无向图以及有权图/无权图等。当边有方向时，我们将一条边连接的两个顶点按方向分为原点（source vertex）和终点（destination vertex）。

对于可抽象成用图表示的数据，我们通常称之为图状结构数据（graph-structured data）。随着互联网的飞速发展，这类数据正在受到越来越多的关注：社交网络中用户间的关注和互动、互联网上网页之间的连接、电子商务平台上用户对物品的评分记录等都是典型的图状结构数据。在天体物理学、计算化学、生物信息学等自然科学领域，图状结构数据也是无处不在。对这些数据的分析都离不开基于图的算法设计，以及面向图的高性能计算系统。

尽管图在数学上可以对应成矩阵，然而图状结构数据的一些特点让我们很难将实现传统科学计算应用所得到的经验直接移植过来：现实世界的图通常平均度数（即边数与顶点数的比值）只有几到几百，与上千万甚至上亿个顶点的规模相比显得极为稀疏，且度数呈幂律分布；而科学计算中我们经常面对的是稠密矩阵，或是较为规则的稀疏矩阵，数据的划分和并行较为容易。

另一方面，基于图的算法通常采用迭代式计算，同时，并非每一轮迭代都需要所有顶点参与计算，且活跃的顶点集不断变化的特点也使得图状结构数据的处理更加复杂，导致通用的大数据处理系统难以有效应对图计算问题。例如，MapReduce在每轮迭代计算中都需要反复读写磁盘，产生大量不必要的开销；而Spark的数据模型RDD由于其不变性（Immutable），产生的大量中间结果会导致不必要的内存占用从而影响能够处理的数据集大小和数据处理的效率。