# A Hierarchical Parallel Graph Summarization Approach Based on Ranking Nodes
## 2 Materials and Methods
### Problem Statement  
Traditional graph summarization algorithms [9] mostly concentrate on minimizing the edge storage overhead, and aggregate nodes into \"super-nodes\" that are recursively based on a two-hop candidate strategy; they also lack the ability to consider the essential factorsof the graph, especially in some special distributions. As a result, the traditional algorithms often lead to the early merging of partial important vertices and miss the key information.  
Figure 1 describes the four-step execution of the sample graph on the random algorithm, which only follows the random candidates and the maximum edge-cost-saving strategy, and ignores the characteristics of key nodes. Here, we have utilized the eigenvector centrality to measure the significance of each node in the sample graph. Eigenvector centrality ([[https://en.wikipedia.org/wiki/Eigenvector_centrality](https://en.wikipedia.org/wiki/Eigenvector_centrality)]([https://en.wikipedia.org/wiki/Eigenvector_centrality](https://en.wikipedia.org/wiki/Eigenvector_centrality)) (accessed on 15 September 2022)) reflects the contributions of connections, and the more important the nodes that are connected with the node are, the higher the eigenvector value of the node is. As a metric for assessing a node's influence on a network, eigenvector centrality considers not only its degree, but also the significance of its neighboring nodes. As shown in Figure 1, I-IV are the process of graph summarization. Green nodes in the figure represent original nodes, and purple nodes represent super nodes. As shown in II, purple node 67 represents two original nodes 6 and 7 merged into one super node. C represents the correction set of summary graph. The average eigenvector value of nodes should generally increase with the deepening of graph compression. However, due to the concentration on minimizing the graph storage overhead, the average eigenvector value of the nodes irregularly changes in four steps.  
Figure 2 describes the comparison of the importance metrics in the summary graph for both greedy and random algorithm execution on the Ca-GrQc ([[https://snap.stanford.edu/data/ca-GrQc.html](https://snap.stanford.edu/data/ca-GrQc.html)]([https://snap.stanford.edu/data/ca-GrQc.html](https://snap.stanford.edu/data/ca-GrQc.html)) (accessed on 5 December 2022)) dataset. The eigenvector centrality value of the summary graph is chosen as the measure of importance metrics. Theoretically, the probability density distribution of the summary graph should mostly retain the key characteristics of higher regions and have a regular positive growth with the compression  
Figure 1: Average node importance example in random summarization.  
ratio. However, as the evaluation results show in Figure 2a, the greedy and random algorithm extracted little features of the key nodes, and the probability density distribution, represent less deviation from the original graph. Figure 2b shows the average node importance variation trends. Due to the lack of the importance factor, the algorithms exhibit irregular changes, which leads to a significant loss of node information.  
Motivated by these analyses, this paper proposes a graph summarization algorithm that is based on ranking nodes, which follows a hierarchical parallel approach, and contracts the importance characteristics efficiently.