基于kd-MDD的时序图紧凑表示  

Compact Representation of Temporal Graphs Based on k^(d)-MDD

作　　者：李凤英[1] 申会强 董荣胜[1] Li Fengying;Shen Huiqiang;Dong Rongsheng(Guangxi Key Laboratory of Trusted Software(Guilin University of Electronic Technology),Guilin,Guangxi 541004)

机构地区：[1]广西可信软件重点实验室(桂林电子科技大学),广西桂林541004

出　　处：《计算机研究与发展》2022年第6期1286-1296,共11页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(62062029,61762024);广西自然科学基金项目(2017GXNSFDA198050)。

摘　　要：时序图是顶点之间的连通性随时间变化的图,大规模时序图的紧凑表示和高效操作是分析和处理时序图数据的基础.提出了一种基于决策图的时序图数据紧凑表示方法——k^(d)-MDD.k^(d)-MDD是对k^(d)-tree的改进,该方法对时序图的邻接矩阵进行k^(d)划分,通过引入多值决策图来合并相同子矩阵,即k^(d)-tree图数据表示中存在的同构子树,存储结构更加紧凑.在k^(d)-MDD紧凑表示基础上,提供了基于k^(d)-MDD的时序图的基本操作(如顶点正向反向邻居的检索、边是否处于活动状态的检查、边的添加和删除等).在真实的时序图数据集上(Flickr-growth,YouTube-growth,Wikipedia等)的实验结果表明,k^(d)-MDD表示中的节点数仅为k^(d)-tree表示中节点数的1.58%~4.65%,与c k^(d)-tree和bc k^(d)-tree相比,其节点数为c k^(d)-tree中节点数的11.13%~20.39%,为bc k^(d)-tree(bucket c k^(d)-tree)中节点数的23.17%~41.95%.实验结果验证了k^(d)-MDD表示时序图的优越性.Temporal graphs represent vertices and binary relations that change with time.Compact representation and efficient operation of large-scale temporal graphs are the basis of analyzing and processing temporal graph data.In this paper,a novel representation of temporal graph data based on decision diagram,namely k^(d)-MDD,is proposed.k^(d)-MDD improves upon the k^(d)-tree and can deal with unclustered data with a good use of space.Firstly,the adjacency matrix of time temporal graph is divided into k^(d).Then,a large number of the same sub matrices,that is the homogeneous subtrees in k^(d)-tree representation of graph,are merged by introducing MDD.The storage structure is more compact.The initialization of k^(d)-MDD and the basic operation of temporal graph(retrieving active direct reverse neighbors of a vertex,checking whether an edge is active,adding(deleting)an edge,etc.)based on k^(d)-MDD are provided.Experiments implemented on real temporal graph data(Flickr-growth,YouTube-growth,Wikipedia etc.)show that the number of nodes in the k^(d)-MDD structure is only 1.58%~4.65%of the number of nodes in the k^(d)-tree,11.13%~20.39%of the number of nodes in the c k^(d)-tree(compressed k^(d)-tree)and 23.17%~41.95%of the number of nodes in the bc k^(d)-tree(bucket c k^(d)-tree).The k^(d)-MDD structure is an effective and unified methodology for the representation and operation of large-scale temporal graphs.

关 键 词：时序图 紧凑表示 决策图 k^(d)-tree k^(d)-MDD 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]