从图的角度看矩阵计算和大数据

《从图的角度看矩阵计算和大数据》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、大数据应用63从图的角度看矩阵计算和大数据孙茹君江南计算技术研究所无锡214083摘要：本文是一篇综述性文章，讨论了图计算和矩阵计算的关系，将图计算对应在矩阵计算中，并且分析了矩阵的更一般的计算。同时，面对海量数据对于图计算的要求，分析了典型的数据挖掘算法在大数据意义下的局限性。关键词：图计算，矩阵计算，数据挖掘局限性，大数据。1.简介和基本概念加法，卷积乘法（Kronecker积）。矩阵参数：1.1图表1矩阵的计算和计算机相关的“图”有三种含义，其一是矩阵的秩最大线性无关行/列的个数图形学（graphics），属于计算可视化（computer行列式visualizatio

2、n）的范畴，比较典型的是其中计算几何所积和式研究的各种图形以及点或者其他构成的空间关系；的根集合：特征值其二是图论（graphtheory），属于组合数学的范畴；其三是较为高层次的一种数据关系--图（graph），特征向量特征值所对应的向量常见的是“关系型数据”这种描述，通过简单的数的一个1元素换成0元素后矩阵可约或者部分可分。据结构或者由其组合表示而得（比如用树是一种特殊的图，简单的一个结构加上一系列指向邻边的指2.图计算的计算机意义针构成了图）。在计算机数学领域，图论被分列在组合数从图的含义可以知道，图有抽象和具象之分。学中，而计算机数学主要包括计算数学和组合数我们的研究

3、关注抽象的图，所以关注的是图所表示学。计算数学处理的是科学计算和数值分析等有的关系和结构。图可以被用边和点来描述G:=(V，E),关“数”的计算，更注重连续性质，即使只有离散边连接点，其整体构成一个图。的计算机精度，也要更精确地表示出连续的数值；而组合数学关注的是离散的性质，研究排列组合，1.2矩阵研究序列。图论就属于排列组合领域的一个小分支。2.1图的计算机表示2.1.1一般表示点属性（所接边）集合——边列表：边列表（关联表）即对于顶点vi，用与之相连的边的集合形成一个列表，这个列表可以用向量或者链表的形式存储。每个顶点形成的整张图的集合可图1矩阵的计算类别用链表来存储。数

4、学中的矩阵是一种二维结构。可以研究单点属性（相邻点）集合——点列表：点列表（个矩阵的参数计算（比如秩，特征值，特征向量邻接表）即对于顶点vi，用与之相连的顶点集合形成等）；也可以研究两个矩阵的运算，除了简单的加其对应的列表，同样用向量或者链法和乘法以外还有以两个矩阵笛卡尔积为元素的圆表的形式存储。64《高性能计算发展与应用》2014年第四期总第四十九期表2图的表示以点为索引每条的元素是点的邻边链表以点为索引每条的元素是点的邻点邻接矩阵A点-点关联矩阵B点-边矩阵度矩阵D对角阵，元素是点的度数Laplace矩阵LL=D-A=B×BTSeidel矩阵S点-点。对角线元素是0，相邻

5、点-1，不相邻1表3图的一般表示的等价性和各操作的复杂性操作邻接表关联表邻接矩阵关联矩阵存储空间添加顶点添加边删除顶点删除边查询（两个顶点是否相邻）点-边关系描述——关联矩阵：关联矩阵：矩阵vi所连的边的数目。IR[i]用于在JC中索引，JC的元素的行和列分别是图的顶点和边集合。当点是边的端是边号。点时在矩阵中对应元素为1，有向图可以用{+1,-1}来区分，自环边对应的列只有一个元素是1。带权图可以在边对应的列再加一条属性表示权值。点-点关系描述——邻接矩阵：邻接矩阵：行和列都是所有顶点的集合，顶点间相连表示边，对应元素是1或者权值。有向图只规定按照方向对应图2邻接表（左）与

6、CSR（右）表示示例的矩阵元素。也有用矩阵元素描述边的重数的方2.1.3各种表示之间的关系式，这样就可以描述重边。2.1.2复合或优化表示元组集合：整个集合表示一张图，集合中的元素是表示边的三元组，每个元组包含边的两个端点和权值信息。此种表示方式和链表中元素的思想类似，但由于和边有关系的点只有两个，故对于整图3图的各种表示张图的分割性能较好。但对于图的结构描述不够直从图3中可以看到，表示图的结构从松散的几乎观。如果仅需要查找邻边都需要遍历所有的边。一没有结构的元组集合，到结构严整查询方便的矩阵个好的方式是按照元组中的点对三元组进行排序。有很多种。且以上列举的只是大类，在现代的

7、优化表4元组的表示措施中，很多对图的表示方法都是这条表示线上大三元组类中间的状态。或者某几类结合以达到综合效果的起点终点权值优化。向量：向量是矩阵和链表的中间状态，它既可由左至右，结构越来越松散，改变图的代价越以像矩阵一样被索引，又不必像矩阵一样每次修改来越小；由右至左，结构越来越严整，需要的存储都用矩阵大小（至少O(n2)）的代价（n是节点数）等表示代价越来越大，但是查询越来越方便。对于较稀疏的图，稀疏矩阵可以描述，同时各种表示方式适用于不同的体系结构和算法要用列表的压缩形式更加灵活和节省空间。CSR