A Hierarchical Parallel Graph Summarization Approach Based on Ranking Nodes

Abstract

Graph summarization techniques are vital in simplifying and extracting enormous quantities of graph data. Traditional static graph structure-based summarization algorithms generally follow a minimum description length (MDL) style, and concentrate on minimizing the graph storage overhead. However, these methods also suffer from incomprehensive summary dimensions and inefficiency problems. In addition, the need for graph summarization techniques often varies among different graph applications, but an ideal summary method should generally retain the important characteristics of the key nodes in the final summary graph. This paper proposes a novel method based on ranking nodes, called HRNS, that follows a hierarchical parallel graph summarization approach. The HRNS first preprocesses the node ranking using a hybrid weighted importance strategy, and introduces the node importance factor into traditional MDL-based summarization algorithms; it then leverages a hierarchical parallel process to accelerate the summary computation. The experimental results obtained using both real and simulated datasets show that HRNS can efficiently extract nodes with high importance, and that the average importance over six datasets ranges from 0.107 to 0.167; thus, HRNS can achieve a significant performance gain on speedups, as the sum error ratios are also lower than the methods traditionally used.

Keywords

• graph contraction
• ranking nodes
• hierarchical summarization approach
• parallel computing
• minimum description length (MDL)