# A Hierarchical Parallel Graph Summarization Approach Based on Ranking Nodes
## 1 Introduction  
Nowadays, the amount of highly interactive applications is increasing rapidly. Graph structures can model entities and their complex relations, and are therefore widely deployed in various applications, such as social network analysis, citation networks, and protein biological network synthesis, etc. With the significant growth of interactive analysis applications, the scale and complexity of graph data are also increasing. In 2021, the number of web pages in China reached 335 billion [1], and the number of social network connections reached tens of billions [2; 3]. Meanwhile, the number of active users of Facebook in early 2022 was over 2.93 billion, with over 100 billion emails being delivered every day [4]. This voluminous user base incurs an overwhelming quantity of interaction data and is generally represented as graph data by researchers. Moreover, discovering ways in which to create simplified and efficient processing methods for massive graphs is becoming one of the most crucial issues in many fields [5]. Large graphs often contain billions of edges and vertices, which often exceed the memory limit and introduce high I/O expenses. Moreover, these graphs often contain a small proportion of vital information and lead to a waste of computing resources. Some researchers have proposed graph simplification techniques, such as graph compression, graph clustering, and graph summary [6], in order to reduce the storage cost and improve computation efficiencies. Graph clustering [7] aggregates together nodes with a similar structure, attributes, or other dimensions, while graph compression [8] mainly focuses on compact storage-savingtechniques, such as the k\({}^{2}\)-tree, adjacency list, and lexicographic order. These two simplifying technologies both shrink the graph data size; however, graph compression mainly focuses on reducing the storage cost, while graph clustering concentrates more on grouping similar nodes together, and is insufficient for expressing globally important features. Although graph clustering and graph summarization both have similar operations in terms of grouping vertices, graph clustering is more focused on the densely connected nodes, while graph summarization compresses a series of interconnected nodes and links to obtain a \"hyper-graph\", which can efficiently abstract the topology, attributes, and other information included in the original graph; this benefits a plethora of graph applications. Traditional graph summarization approaches, such as greedy or random algorithms, are mostly based on the topology structure or on the abstraction of attributes, both of these algorithms share the same MDL (Minimum Description Length) principle [9], but differ in their node-pair-choosing strategy. However, real-world graphs always have special characteristics, such as a small-world network [10], random network [11], or a power law distribution [12], which often leads to significant differences in the node importance; meanwhile, users expect to maximize the key information of the original graph with as few nodes as possible, especially for the analysis of visual graphs, such as Wikipedia's opinion-editing network [13], heterogeneous RDF visualization [14; 15], the financial risk network [16; 17] and other graph applications [18; 19]. In summary, these motivate the creation of novel techniques for graph contraction. This paper proposes a hierarchical parallel graph summarization approach that leverages the node importance factor and simultaneously avoids the low efficiency and incomprehensive summary dimension that exists in traditional graph summarization algorithms. Firstly, the shortcomings of the traditional summarization algorithms are addressed by quantitative analysis and via a comparison of the importance metrics on the summary graph, which shows that these methods ignore some key information during the summarizing phase.