GraphBLAS图的稀疏表示方法

首先安装所需工具：只需运行 python -m pip install python-graphblas 即可。

1 邻接矩阵：图的一种直观表示方法

首先介绍最直观的图表示方法——邻接矩阵。假设有一个由4个节点（0、1、2、3）构成的有向图，如下所示：

邻接矩阵中，行表示出边，列表示入边。例如，第2行（节点2）指向节点0和节点3；第3列（节点3）中有三个1，表示其入度为3，分别来自节点1、2、3（节点3自身也存在自环）。这种表达方式非常直观易懂。

下面使用NumPy数组来构建这个邻接矩阵的代码：

 复制代码import numpy as npA = np.array([
    [0, 1, 1, 0],
    [1, 1, 0, 1],
    [1, 0, 0, 1],
    [0, 0, 1, 1]
], dtype=np.int32)

虽然邻接矩阵在概念上容易理解，但如果直接采用二维稠密数组存储，效率会非常低下。以实际场景为例：一个拥有100万用户的社交网络，平均每人关注100人，若全部使用稠密矩阵存储，会导致怎样的结果？请参考下图对比：

2 稀疏存储：高效表示图结构

因此，实际应用中采用稀疏存储方式——仅记录非零元素的坐标和值。GraphBLAS内部基于稀疏数据结构，具体格式由框架自动选择最优方案。

2.1 COO、CSR、CSC格式详解

通常，我们从COO（三元组）格式开始构建数据，但在内部计算时默认会转换为CSR格式。你无需手动指定，框架会自动选择。下面使用python-graphblas演示COO格式的构建过程：

 复制代码import graphblas as gb# COO 三元组 
row = [0, 0, 1, 1, 1, 2, 2, 3, 3] 
col = [1, 2, 0, 1, 3, 0, 3, 2, 3] 
val = [1]*9 
# 构建矩阵（默认 CSR） 
A = gb.Matrix.from_coo(row, col, val, nrows=4, ncols=4) #  
# 默认就是 CSR 格式
print(A) 

如果想了解三种格式的内部存储细节，可以使用SciPy的稀疏矩阵进行对比。以下代码演示了COO、CSR和CSC的构造与输出，注意CSC是按列索引记录非零坐标：

 复制代码import numpy as npfrom scipy.sparse import coo_matrix, csr_matrix# 1. 准备 COO 格式的数据row = np.array([0, 0, 1, 1, 1, 2, 2, 3, 3])col = np.array([1, 2, 0, 1, 3, 0, 3, 2, 3])data = np.array([1, 1, 1, 1, 1, 1, 1, 1, 1])  # 2. 构建 COO 矩阵（构建阶段）
coo = coo_matrix((data, (row, col)), shape=(4, 4))
  # 3. 转换为 CSR 格式（计算阶段，这会自动完成压缩）
csr = coo.tocsr()# 查看结果
print(csr.toarray())    # 输出: [[0 1 0] [0 0 1] [0 0 0]]
print(csr.indptr)       # 输出: [0 2 5 7 9]  (行索引被压缩了)
print(csr.indices)      # 输出: [1 2 0 1 3 0 3 2 3]
print(csr.data)         # 输出: [1 1 1 1 1 1 1 1 1]
#4. 转换为 CSC 格式（计算阶段，这会自动完成压缩）
csc = coo.tocsc()
print(csc.toarray())
print(csc.indptr)       # 输出: [0 2 4 6 9]  (列索引被压缩了)
print(csc.indices)      # 输出: [1 2 0 1 0 3 1 2 3]
print(csc.data)         # 输出: [1 1 1 1 1 1 1 1 1]

2.2 三种表达方式详细说明

2.3 稀疏存储与稠密存储的规模对比

场景：100万用户的关注关系，平均每人关注100人。以下两张图直观展示了稀疏存储与稠密存储之间的巨大差异：

3 介于稀疏与稠密之间的位图格式：bitmapr与bitmapc

除CSR等格式外，GraphBLAS 7.0及以上版本还引入了一种介于稀疏和稠密之间的格式——bitmapr（Bitmap by Row，按行位图）。其思路是：每行使用一个0/1位图标记所有列，1的位置表示非零元素。构造逻辑如下：

bitmapc 与 bitmapr 逻辑相同，区别在于按列进行位图标记。

3.1 BitmapR与CSR的对比

BitmapR的核心优势在于：随机查询 A[i, j] 的时间复杂度为 O(1)（直接读取位图），而CSR需要 O(log k) 的二分查找。在半稠密场景下，这一优势尤为突出。

3.2 何时选择BitmapR？