Compact Representation of Temporal Graphs Based on 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 ck^d--tree (compressed k^d-tree) and 23.17%~41.95% of the number of nodes in the bck^d--tree (bucket ck^d--tree). The k^d--MDD structure is an effective and unified methodology for the representation and operation of large-scale temporal graphs.