Efficient and compact representation and operation of graph data w hich contains hundreds of millions 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 the decision diagram ,that is k2‐MDD ,providing the initialization of k2‐MDD and the basic operation such as 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 k2 tree ,and after dividing the adjacency matrix of graph into k2 ,it is stored with the multi valued decision diagram ,so as to achieve a more compact storage structure .According to the experimental results of a series of real Web graph and the social network graph data (cnr‐2000 ,dewiki‐2013 ,etc .) derived from the LAW laboratory at the University of Milan ,it can be seen that the number of k2‐MDD’ nodes is only 2.59% 4.51% of the k2 tree , w hich achieving the desired effect . According to the experimental results of random graphs ,it can be seen that the k2‐MDD structure is not only suitable for sparse graphs ,but also for dense graphs .The graph data of k2‐MDD shows that both containing the compact and query efficiency representation of k2 tree and realizing the efficient operation of the graph model can thus achieve the unity of description and computing power .%对包含亿万个顶点和边的图数据进行高效、紧凑的表示和操作是大规模图数据分析处理的基础．针对该问题提出了基于决策图的大规模图数据的一种表示方法——— k2‐M DD ，给出了 k2‐M DD的构造过程以及图的边查询、外（内）邻查询、出（入）度查询、添加（删除）边等基本操作．该表示方法在 k2树的基础上进行优化与改进，对图的邻接矩阵进行 k2划分后，采用多值决策图进行存储，从而达到存储结构更为紧凑的目的．通过对来自米兰大学LAW实验室的一系列真实网页图和社交网络图数据的实验结果可以看出，k2‐M DD结构在节点数上仅为 k2树的2.59％～4.51％，达到了预期效果．通过对随机图的实验结果可以看出，k2‐M DD结构不仅适用于稀疏图，同样也适用于稠密图．图数据的 k2‐M DD表示，既具有 k2树表示的紧凑型和查询的高效性，又能实现符号决策图表示下图模式的高效操作，从而实现了描述和计算能力的统一．
展开▼
