共计 6410 个字符，预计需要花费 17 分钟才能阅读完成。
在进行各种图解决、图计算、图查问的时候，内存或是硬盘中如何存储图构造是一个影响性能的关键因素。本文次要剖析了几种常见的内存图构造，及其工夫、空间复杂度，心愿对你有所启发。
通常来说，对于图构造的几种常见的根底操作：
- 插入一个点
- 插入一个边
- 删除一个边
- 删除一个点的全副邻边
- 找到一个点的全副邻边
- 找到一个点的另一个邻点
- 全图扫描
- 获取一个点的入度或者出度
这些图相干的操作，除了要关怀工夫复杂度之外，须要思考空间占用的问题。
对于大多数实时读写型的零碎，增删改查的性能问题会比拟重要，它们比拟关注下面 1-6 的操作；对于局部密集计算的零碎，对批量读取的性能会比拟器重，偏重下面 5-8 的操作。
不过遗憾的是，无论是惯例的图查问，还是进阶的图计算，依据 RUM 猜测[1]，读快、写快、又省空间这样”既要又要也要”的坏事是不存在的。
上面，咱们介绍几个数据结构并给出大量的定量分析。
咱们先从三个典型的计划（邻接矩阵、压缩稠密矩阵和邻接表）说起，再介绍几种近几年的钻研的变种构造 PCSR、VCSR、CSR++。
邻接矩阵 Adjacency Matrix
用矩阵来示意图构造是大学里数据结构课程中都学过的常识，也是一种十分直观的方法。
点 i 与点 j 之间有一条边，等价对应于矩阵上 $M_{ij}$ 为 1。当然，这里的点 ID 是须要间断排列无空洞。
用矩阵来示意图构造有显著的益处，能够复用大量线性代数的研究成果：比方图上模式匹配类的问题等价于矩阵的相乘。
上面是一个模式匹配问题，它的大体意思是在全图上寻找这样一种图构造：
Match (src)-[friend * 2..4]->(fof)
WHERE src.age > 30
RETURN fof对于这样一个问题能够间接对应左边的矩阵操作：
比方，2 跳遍历等价于矩阵 F 自乘；2 – 4 跳遍历别离等价于 F^2、F^3、F^4；取属性等价于乘以一个过滤矩阵。
更进一步，因为矩阵操作是天生能够分块并行减速，这在性能上有极大的劣势。
上面，咱们对邻接矩阵操作进行一个简略的定量分析
| 操作 | 工夫复杂度 | 备注 |
|---|---|---|
| 插入一个点 | O(n^2) | 对于矩阵来说，减少一个点意味着整个矩阵的维度减少，通常须要另外开拓一块空间 |
| 插入一个边 | O(1) | 减少一个边只是将对应的地位置 1 |
| 删除一个边 | O(1) | 置 0 |
| 删除一个点的全副邻边 | O(n) | 对于某个点所有出边的删除对应某一行的置 0。入边对应某一列，能够批量操作 |
| 找到一个点的全副邻边 | O(n) | |
| 找到一个点的给定邻点 | O(1) | |
| 全图扫描 | O(n^2) |
其中，n=|V|，m=|E|。
优化上，批量操作（CPU Cache/SSD block）能够线性减少性能，例如 O(n) 能够升高到 O(n/B)，但不影响定量分析。
因为绝大多数图构造是极其稠密的，因而简略用邻接矩阵来示意图构造，其内存会有夸大的节约。更为严重的是，当有多种边类型时，每种边类型各须要一个邻接矩阵。这使得裸用矩阵在理论状况中只能解决很小数据量的场景。当然，对于古代服务器动辄几百 G 的内存，如果只有几亿点边的数据量，像是 twitter2010，这并不会是很重大的问题。但大多数状况下，条件容许的话，大家还是心愿找到一些更加经济的构造。
压缩稠密矩阵 CSR/CSC
压缩稠密矩阵是一种十分风行和紧凑的图构造示意形式，大多数图计算零碎都采纳 CSR。
这里简略介绍一下 CSR 的构造：
对于点 IDx，取街坊 ID 就是 F[N[x]] 到 F[N[x+1]-1]。
例如，查找点 ID2 的街坊，对应为 F[N[2]] 到 F[N[2+1]-1]，对应到上图也即 1 6 8。查找点 ID7 的街坊，对应为 F[N[7]] 到 F[N[7+1]-1]，也就是 2 和 4。
另外，CSR 记录的仅是出边的信息，如果要思考入边就应用 CSC，其原理是相似的。
| 操作 | 工夫复杂度 | 备注 |
|---|---|---|
| 插入一个点 | O(1) | 在点矢量尾部减少 |
| 插入一个边 <u,v> | O(m+n) | 边矢量，从 u 对应的街坊开始，都向后挪动一位；点矢量，从 u 对应地位开始每个值加 1 |
| 删除一个边 | O(m+n) | 插入边的逆过程 |
| 删除一个点 v 的全副邻边 | O(m+n) | 边矢量挪动 deg(v) 位，点矢量 u 对应地位置 0 |
| 找到一个点的全副邻边 | O(deg(v)) | |
| 找到一个点的给定邻点 | O(log(deg(v))) | deg(v) 内的排序查找 |
| 全图扫描 | O(m+n) |
CSR 的空间占用是 O(|V|+|E|)，在空间节俭和程序查找上是极其高效的 。但 在大量插入时，压缩稠密矩阵和邻接矩阵一样，须要从新开拓空间，效率很低。所以，它适宜于计算密集场景但不适宜增改频繁的场景。
CSR 还有一个显著的长处是能够疾速获取每个点的出入度，只有计算 N[x+1]-N[x]，这在判断一些点是否为超级节点时很不便。如果不是稠密矩阵的话，通常会用另外一个独自的构造来记录出入度。
此外，CSR 不容易实现并发批改，其每次插入都须要对两个矢量进行位移，这并不高效。
这里举荐两个相干的开源我的项目，能够进一步理解下 CSR 的应用：
- https://github.com/DrTimothyAldenDavis/GraphBLAS
- https://github.com/GraphBLAS/LAGraph
邻接链表 Adjacency List
和基于矩阵的形式不同，邻接链表 AL 空间上有劣势，但对于边的读写上会稍微慢一点（指针在内存中不能间断挪动）。AL 的做法是把邻边（出边）用 list 或者有序 list 的形式串连起来。由此延长的一个变种是邻边从 list 改为 array。
| 操作 | 工夫复杂度 | 备注 |
|---|---|---|
| 插入一个点 | O(1) | 尾插入 |
| 插入一个边 <u,v> | O(log(deg(u))) | 有序 list |
| 删除一个边 | O(log(deg(u))) | |
| 删除一个点 v 的全副邻边 | O(1) | |
| 找到一个点的全副邻边 | O(deg(u)) | |
| 找到一个点的给定邻点 | O(log(deg(u))) | |
| 全图扫描 | O(n+m) |
AL 相比 CSR 通常不能间接取得点的出入度，能够通过能够独自保护一个字段实现该性能。
此外，邻接表并不需要 ID 间断排布，对于频繁增删点的场景特地敌对。AL 对于并发批改的反对也更敌对，人造在点级别有并行度。当然，对于超级节点，间接用 list 的形式，还是会有些性能的问题要思考；优化上可能会进一步革新成 Blocked list 的形式，能够带来更好的数据局部性和细颗粒度。
因为 ID 不必严格间断排布，AL 的一个常见变种就是 Tree。
Tree
在这种构造中，一个点和其所有的邻边被建模成了 key-value，key 是点 ID，value 是所有邻边的编码。Key 通过 Tree 的形式组织在一起。这里的树能够是 B-Tree 等各变种 Tree。尽管本文没有探讨图属性，但 value 中也是能够寄存 value。
| 操作 | 工夫复杂度 | 备注 |
|---|---|---|
| 插入一个点 | O(log(n)) | |
| 插入一个边 <u,v> | O(deg(u) log(n)) | |
| 删除一个边 | O(deg(u) log(n)) | |
| 删除一个点 v 的全副邻边 | O(log(n)) | |
| 找到一个点的全副邻边 | O(deg(u) log(n)) | |
| 找到一个点的给定邻点 | O(log(n deg(u)) | |
| 全图扫描 | O(n+m) |
为了管制拜访颗粒度，每个叶子通常会被限定为固定的大小（页）。这就是在数据库类零碎外面最常见的方法 B-tree。为了增改不便，也能够把每页的 in-place update 改成 Copy-On-Write 的形式；一个典型的代表就是 LLAMA[2]，但这种多版本的读取通常会须要更多的空间，并且当有大量累积批改时，须要定期的多版本合并以升高跨快照读。某种程度上，它和 LSM-Tree 的思路有些靠近。
基于 CSR 的变种 PCSR 和 VCSR
因为 CSR 在空间和读性能上有很大的劣势，但在插入时的耗时和空间上都很弱，因而本节几个变种的次要目标都是为了改善其弱项，大体思路都是分块和 buffer。
在 CSR 的边矢量进行增删时能够留神到，次要耗时是在对于矢量的元素位移上。因而，一个直观的思路是预留一些插入空白位，在删除时也不立即回收这些空白。
而分块思维，是指将一些部分数据放在同一个分块内，例如 Tree 中每个 page 就是一种分块的形式。与此对应的是，buffer 空白之间的间断区域。
PCSR
PCSR [3]的根本思维是：对于点矢量，其元素从一个值改为对应边矢量中对应邻边地位的 < 终点, 起点 >。而对于边矢量，在这些分块所对应边界搁置哨兵 sentinel，上图中的 S，上图的“-“对应预留插入地位留空。
事实上，原文中，对于边矢量，其本质是实现为一个 B-Tree，本文先简化成一个 Array。
| 操作 | 工夫复杂度 | 备注 |
|---|---|---|
| 插入一个点 | O(1) | 间接在点矢量和边矢量的尾插入 |
| 插入一个边 <u,v> | O(log(deg(u)) | 边矢量对应分片的二分 + 空位查找 |
| 删除一个边 | O(log(deg(u)) | |
| 删除一个点 v 的全副邻边 | O(1) | 边矢量对应分片置空，点矢量对应 ID 地位置空 |
| 找到一个点的全副邻边 | O(deg(u)) | |
| 找到一个点的给定邻点 | O(log(deg(u)) | |
| 全图扫描 | O(n+m) |
能够看到，PCSR 的预留地位多少都是须要重均衡，不能过多也不能有余。特地是大批量增删时，对预留地位的解决会是一个较重的操作。
此外，如果把 PMA 的 B-Tree 以及须要 rebalance 的实质思考进去，其和前述 Tree 形式的区别并不是很大。
VCSR
VCSR[4]次要是对 PCSR 的一个改良，其奢侈思维是 PCSR 的留空是平均的，而大多数图构造的出入度，是存在 20-80 这样的幂率特色，而 PCSR 的一个次要痛点是频繁的 rebalance。VCSR 的做法是为每个分块预留空间反比于其分块内的点的数量，即：边矢量中，一个分块内，如果点的数量多，就多预留一些空位。在直觉上，点数量多时，其分块对应的边插入会更多一些，这样能够缩小 rebalance 的频率。
此外，VCSR 还有些版本号之类的优化。
CSR++
事实上，CSR++[5]在设计上其实更靠近一种 AL/Tree 的变种，而不是 CSR。它次要有三个方面的优化：
第一，对于 Vertex Array 再分段，将一个大的 Array 拆成多段，这样能够有更细的读写颗粒度。通过 段 ID + 点 ID 来定位每个点和其邻边。
第二，Vertex Array 中每个元素，除了记录点 ID 之外，对于邻边数量很少的点，间接把街坊 ID 也对齐地塞 inline 进去。
对于大多数的点，其邻边就不须要独自的 Edge Array 来存储了。
能够看到这种形式在图比拟稠密的时候，对于 CPU Cache 扫描是很敌对的。
第三，对于每个点的邻边，采纳 copy-on-write、标记删除等常见的优化方法，构建成相似 std::vector 构造。
小结
最初，因为在图查问、图存储和图计算不同场景下，对于图构造的读写扫描和生命周期都有些不同的要求，不同的数据结构也有不同的优劣。
当然，本文只是探讨了图构造能够放在内存中的状况。当不得不把局部数据放在硬盘上时，问题就齐全不同了。当然本文也没有探讨不同 CPU 对于不同间隔内存的性能差别 NUMA，或者跨过程通信带来的影响。
延长浏览
最初，咱们来理解下在图计算 / 图算法上的图操作。
图算法中的图操作
在图计算中，存在多种图构造算法，可能会波及多种根底操作。
核心性 Centrality Algorithms，一种掂量一个节点在整个网络图中所在核心水平的算法，包含：度核心性、靠近核心性、介数核心性等，会波及“找到一个点的全副邻边”、“找到一个点的另一个邻点”、“全图扫描”的操作组合。
- 度核心性通过节点的度数，即关联的边数来刻画节点的受欢迎水平，这将会要求找到一个点的所有邻边。
- 靠近核心性，通过计算每个节点到全图其余所有节点的门路和来刻画节点与其余所有节点的关系密切水平，这将会要求进行全图扫描，查找点和图中所有点的门路信息。
- 介数核心性，则用于掂量一个顶点呈现在其余任意两个顶点对之间最短门路上的次数，从而来刻画节点的重要性，这将会要求进行全图扫描，找到一个点和它的邻点及门路信息
PageRank，又称网页排名、谷歌左侧排名，是一种由搜索引擎依据网页之间互相的超链接计算的技术作为网页排名的因素之一的排名办法。它以 Google 公司创办人拉里·佩奇 Larry Page 之姓来命名。Google 用它来体现网页的相关性和重要性，在搜索引擎优化操作中是常常被用来评估网页优化的功效因素之一。一般来说，PageRank 的值越高，示意其被很多其余网页链接到，阐明它的重要性很高；而如果一个 PageRank 很高的网页链接到其余网页，被链接的网页的 PageRank 值也会随之进步。PageRank 的计算过程如下：
假如由 4 个网页组成的汇合：A、B、C、D，每个页面的初始 PageRank 值雷同，为了满足概率值为 0-1 之间，假如这个值为 0.25。
如果所有页面都只链接至 A，如下图，则 A 点的值将是 B、C、D 的 PageRank 值的和。
假使是下图这种图构造：
B 链接到 C，D 链接到 B 和 C，A 点的值计算的形式如下：
这里的 2、1、3，别离是 B 点对外链接的 2 条边，C 点对外链接的 1 条边，D 点对外链接的 3 条边。
换句话说，算法将依据每个页面连出总数平分该页面的 PR 值，并将其加到其所指向的页面：
最初，所有这些 PR 值被换算成百分比模式再乘上一个修改系数。
因为“没有向外链接的网页”传递进来的 PR 值会是 0，这时候如果递归的话，会导致指向它的页面的 PR 值的计算结果同样为零，所以 PageRank 会赋给每个页面一个最小值。
因而，一个页面的 PR 值间接取决于指向它的的页面。如果在最后给每个网页一个随机且非零的 PR 值，通过反复计算，这些页面的 PR 值会趋向于某个定值，也就是处于收敛的状态，即最终后果。
简略来说，大多数迭代图计算模型都是基于“找到一个点的全副邻边”、“找到一个点的另一个邻点”操作。
AIGC 小课堂
在 AIGC 小课堂局部，咱们会用 NebulaGraph 接入的 aibot 来解说下文中的局部概念。你如果对 chatgpt 或者是 aibot 有趣味，能够来 https://discuss.nebula-graph.com.cn/ 向 aibot 提出你的要求。
参考文献
- Athanassoulis, M., Kester, M. S., Maas, L. M., et al. (2016). Designing Access Methods: The RUM Conjecture. In EDBT (pp. 461-466).
- Macko, P., Marathe, V. J., Margo, D. W., et al. (2015). Llama: Efficient Graph Analytics Using Large Multiversioned Arrays. In 2015 IEEE 31st International Conference on Data Engineering (pp. 363-374). IEEE.
- Wheatman, B., & Xu, H. (2018). Packed Compressed Sparse Row: A Dynamic Graph Representation. In 2018 IEEE High Performance Extreme Computing Conference (HPEC) (pp. 1-7). IEEE.
- Islam, A. A. R., Dai, D., & Cheng, D. (2022). VCSR: Mutable CSR Graph Format Using Vertex-Centric Packed Memory Array. In 2022 22nd IEEE International Symposium on Cluster, Cloud and Internet Computing (CCGrid) (pp. 71-80). IEEE.
- Firmli, S., Trigonakis, V., Lozi, J. P., et al. (2020). CSR++: A Fast, Scalable, Update-Friendly Graph Data Structure. In 24th International Conference on Principles of Distributed Systems (OPODIS’20).