Dense Subgraphs Summarization: An Efficient Way to Summarize Large Scale Graphs by Super Nodes

摘要

For large scale graphs, the graph summarization technique is essential, which can reduce the complexity for large-scale graphs analysis. The traditional graph summarization methods focus on reducing the complexity of original graph, and ignore the graph restoration after summarization. So, in this paper, we proposed a graph Summarization method based on Dense Subgraphs (DSS) and attribute graphs (dense subgraph contains cliques and quasi cliques), which recognizes the dense components in the complex large-scale graph and converts the dense components into super nodes after deep sub-graph mining process. Due to the nodes in the dense component are closely connected, our method can easily achieve the lossless reduction of the summarized graph. Experimental results show that our method performs well in execution time and information retention, and with the increase of data, DSS algorithm shows good scalability.