43
63
GraphBLAS_01_图的稀疏表示
2026-07-21 12:15:26
0点赞
0收藏
0评论
python直接安装：python -m pip install python-graphblas
1 邻接矩阵表示图
假设有如下0，1，2，3个节点的有向图
可以用邻接矩阵表示，沿行读取是出边，沿列读取是入边
沿行：例如node = 2，出边到node=0, node=3
沿列：例如node = 3, 可以看到有3个1，则入度为3，分别来自节点1，2，3
import numpy as np
A = np.array([
[0, 1, 1, 0],
[1, 1, 0, 1],
[1, 0, 0, 1],
[0, 0, 1, 1]
], dtype=np.int32)
虽然邻接矩阵概念上很好，但用二维稠密数组（就是每个数）存储极其低效，例如100 万用户社交关注关系图（平均每人关注 100 人） 的场景下：
2 稀疏存储表示图：
实际上就是只记录不为0的坐标和值，graphblas内部的计算基于稀疏数据结构，但是用哪种结构由框架智能选择。
2.1 COO/CSR/CSC
计算的时候从COO格式构造，内部计算都是用的CSR，没有必要显示指定，框架内部智能决定用什么数据结构
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)
显示查看COO, CSR,CSC的储存细节，CSC用的是按照列进行索引来记录非0坐标
import numpy as np
from 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 3种表达方式说明
2.3 和稠密的规模对比
场景：100 万用户关注关系的场景，平均每人关注 100 个人
3 介于稀疏和稠密之间的bitmapr，bitmapc
bitmapr（Bitmap by Row按行位图存储） 是 python-graphblas 的 另一种内部存储格式，SuiteSparse:GraphBLAS 7.0+新引入的一种内部格式，介于 CSR 和稠密矩阵之间，专为半稠密场景优化。
比如CSR是存每行的列索引（只存非零，那 BitMapR:就是每行用 01 位图标记所有列，"1" 的位置就是非零，构造逻辑如下：
bitmapc和bitmapr逻辑一致，只不过是按列。
3.1 bitmapr和CSR对比
BitMapR 的核心优势： A[i, j] 查询是 O(1)（读位图），CSR 要 O(log k) 二分查找。
3.2 什么时候用 BitmapR？
条件 推荐格式 每行非零数 / ncols < 10% CSR 每行非零数 / ncols ≈ 20%~6% BitmapR 每行非零数 / ncols > 80% FullR（稠密） 大量全空行 HyperCSR
