Summarizing Graph Data Via the Compactness of Disjoint Paths

Document Type : Original Article


Faculty of Science, Benha University


Graphs are widely used to model many real-world data in many application domains such as chemical compounds, protein structures, gene structures, metabolic pathways, communication networks, and images entities. Graph summarization is very important task which searching for a summary of the given graph. There are many benefits of the graph summarization task which are as follows. By graph summarization, we reduce the data volume and storage as much as possible, speedup the query processing algorithms, and apply the interactive analysis. In this paper, we propose a novel graph summarization method based on the compactness of disjoint paths. Our algorithm called DJ_Paths. DJ_Paths is edge-grouping technique. The experimental results show that DJ_Path outperforms the state-of-the-art method (Slugger [9]) with respect to compression ratio (it achieves up to 2x better compression), total response time (It outperforms Slugger by more than one order of magnitude), and memory usage (it is 8x least memory consumption).


Main Subjects