GraphBLAS_01_图的稀疏表示

python直接安装python -m pip install python-graphblas1 邻接矩阵表示图假设有如下0123个节点的有向图可以用邻接矩阵表示沿行读取是出边沿列读取是入边沿行例如node 2出边到node0, node3沿列例如node 3, 可以看到有3个1则入度为3分别来自节点123importnumpyasnp Anp.array([[0,1,1,0],[1,1,0,1],[1,0,0,1],[0,0,1,1]],dtypenp.int32)虽然邻接矩阵概念上很好但用二维稠密数组就是每个数存储极其低效例如100 万用户社交关注关系图平均每人关注 100 人的场景下2 稀疏存储表示图实际上就是只记录不为0的坐标和值graphblas内部的计算基于稀疏数据结构但是用哪种结构由框架智能选择。2.1 COO/CSR/CSC计算的时候从COO格式构造内部计算都是用的CSR没有必要显示指定框架内部智能决定用什么数据结构importgraphblasasgb# COO 三元组row[0,0,1,1,1,2,2,3,3]col[1,2,0,1,3,0,3,2,3]val[1]*9# 构建矩阵默认 CSRAgb.Matrix.from_coo(row,col,val,nrows4,ncols4)# Matrix 4x4, int64, 9 entries# 默认就是 CSR 格式print(A)显示查看COO, CSR,CSC的储存细节CSC用的是按照列进行索引来记录非0坐标importnumpyasnpfromscipy.sparseimportcoo_matrix,csr_matrix# 1. 准备 COO 格式的数据rownp.array([0,0,1,1,1,2,2,3,3])colnp.array([1,2,0,1,3,0,3,2,3])datanp.array([1,1,1,1,1,1,1,1,1])# 2. 构建 COO 矩阵构建阶段coocoo_matrix((data,(row,col)),shape(4,4))# 3. 转换为 CSR 格式计算阶段这会自动完成压缩csrcoo.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 格式计算阶段这会自动完成压缩csccoo.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 介于稀疏和稠密之间的bitmaprbitmapcbitmaprBitmap 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