大规模图数据的k^2-MDD表示方法与操作研究

Representation and Operations Research of k^2-MDD in Large-Scale Graph Data

对包含亿万个顶点和边的图数据进行高效、紧凑的表示和操作是大规模图数据分析处理的基础.针对该问题提出了基于决策图的大规模图数据的一种表示方法——k^2-MDD,给出了k^2-MDD的构造过程以及图的边查询、外(内)邻查询、出(入)度查询、添加(删除)边等基本操作.该表示方法在k^2树的基础上进行优化与改进,对图的邻接矩阵进行k^2划分后,采用多值决策图进行存储,从而达到存储结构更为紧凑的目的.通过对来自米兰大学LAW实验室的一系列真实网页图和社交网络图数据的实验结果可以看出,k^2-MDD结构在节点数上仅为k^2树的2.59%~4.51%,达到了预期效果.通过对随机图的实验结果可以看出,k^2-MDD结构不仅适用于稀疏图,同样也适用于稠密图.图数据的k^2-MDD表示,既具有k^2树表示的紧凑型和查询的高效性,又能实现符号决策图表示下图模式的高效操作,从而实现了描述和计算能力的统一.

Efficient and compact representation and operation of graph data which contains hundreds ofmillions of vertices and edges are the basis of analyzing and processing the large scale of graph data.Aiming at the problem,this paper proposes a representation of large-scale graph data based on thedecision diagram,that is^2-MDD,providing the initialization of^2-MDD and the basic operation suchas the edge query,inner(outer)neighbor query,finding out(in)-degree,adding(deleting)edge,etc.The representation method is optimized and improved on the basis of k2tree,and after dividing theadjacency matrix of graph into k2,it is stored with the multi valued decision diagram,so as to achievea more compact storage structure.According to the experimental results of a series of real Web graphand the social network graph data(cnr-2000,dewiki-2013,etc.)derived from the LAW laboratory atthe University of Milan,it can be seen that the number of^2-MDD5nodes is only2.59%-4.51%ofthe k2tree,which achieving the desired effect.According to the experimental results of randomgraphs,it can be seen that the^2-MDD structure is not only suitable for sparse graphs,but also fordense graphs.The graph data of^2-MDD shows that both containing the compact and query efficiencyrepresentation of k2tree and realizing the efficient operation of the graph model can thus achieve theunity of description and computing power.