ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2019, Vol. 56 ›› Issue (6): 1338-1355.doi: 10.7544/issn1000-1239.2019.20180371

Previous Articles    

Progress and Challenges of Graph Summarization Techniques

Wang Xiong1, Dong Yihong1, Shi Weijie1, Pan Jianfei1,2   

  1. 1(Faculty of Electrical Engineering and Computer Science, Ningbo University, Ningbo, Zhejiang 315211);2(Baidu Online Network Technology Company, Beijing 100085)
  • Online:2019-06-01
  • Supported by: 
    This work was supported by the National Natural Science Foundation of China (61572266), the Natural Science Foundation of Zhejiang Province of China (LY16F020003), and the Natural Science Foundation of Ningbo City of China (2017A610114).

Abstract: Graph summarization aims to search a group of simple hypergraphs or sparse graphs, which illustrate the main structural information or change trend of the original graph. Based on the application field and background of original graph, different graph summarization techniques are used to construct a specific summary graph, which can solve the problems of information overload, query optimization, spatial compression, impact analysis, social network visualization and so on. According to the classification criteria of the main purpose of the summary, the existing graph summarization techniques are divided into four categories: the graph summarization based on spatial compression, the graph summarization based on query optimization, the graph summarization based on pattern visualization and the graph summarization based on impact analysis. The partial graph summarization algorithms of non-attribute graphs and attribute graphs are tested on real data sets to analyze the indexes of information retention rate, compression rate, information entropy and running time experimentally. At last, not only the development trends of the graph summarization are highlighted, but also the challenges and the future research directions that can be explored in depth are pointed out. Combining with the popular deep learning technology, some valuable and potential Macro coutermeasures are put forward to solve these challenges.

Key words: survey, graph summarization, graph aggregation, graph synopsis, graph compression, visualization

CLC Number: