# A Key Node Mining Method Based on K-Shell and Neighborhood Information
## 4 Experiments and Results
### Performance of KCH
#### 4.3.2 Monotonicity Analysis  
In this paper, we utilize the monotonicity metric M and rank distribution graphs to evaluate the monotonicity of the methods. In the rank distribution graph, the horizontal axis represents the rank of the nodes, while the vertical axis indicates the number of nodes with the same rank. To assess whether an algorithm exhibits good monotonicity in the graph, we examine its rank distribution curve; the closer the curve lies to the bottom of the graph as a straight line, the better the algorithm's monotonicity. Table 4 presents the results of the monotonicity M-values for different methods.  
From the aforementioned results, it is evident that the KS method exhibits the worst monotonicity, while KCH, HKS, and CNC+ exhibit the best monotonicity. Among these methods, HKS has the highest average monotonicity, closest to 1, followed by CNC+ and then KCH. However, the average monotonicity of KCH only differs from CNC+ by 0.0092 and from HKS by 0.0165.  
The HKS method estimates the node's importance based on node position, degree, and the characteristics of neighboring nodes, while CNC+ assesses the node's importance by considering the degree of neighboring nodes and KS values. While these methods offer high monotonicity, they also come with drawbacks. The HKS method exhibits very high time complexity, making it challenging to apply in large networks. For example, in the HepPh network, when implementing the algorithm on the same computer with the same programming language and style, the HKS method takes up to 2756 s of CPU time, while the KCH method only takes 24 s, with the complex importance calculation of HKS bringing a hundredfold increase in time cost. Additionally, the HKS and the CNC+  
\begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline
**Networks** & **KCH** & **CI** & **SC** & **HKS** & **KS** & **CC** & **CNC+** \\ \hline Windsurfer & **0.4170** & 0.4191 & 0.4240 & 0.4283 & 0.4294 & 0.4310 & 0.4240 \\ WikiVote & **0.2052** & 0.2188 & 0.2419 & 0.2799 & 0.2200 & 0.2954 & 0.2638 \\ USpowerGrid & **0.0826** & 0.0876 & 0.0915 & 0.1000 & 0.2113 & 0.1973 & 0.1179 \\ Tribes & **0.4219** & 0.4375 & 0.4375 & 0.4414 & 0.4375 & 0.4297 & 0.4375 \\ Seventh & **0.4578** & 0.4602 & 0.4661 & 0.4637 & 0.4649 & 0.4602 & 0.4661 \\ Rhesus & **0.4063** & 0.4141 & 0.4102 & 0.4141 & 0.4375 & 0.4141 & 0.4141 \\ HepPh & 0.2727 & **0.2693** & 0.2868 & 0.3323 & 0.2814 & 0.2851 & 0.3270 \\ Health & **0.4195** & 0.4202 & 0.4281 & 0.4514 & 0.4437 & 0.4353 & 0.4376 \\ Dolphins & **0.2789** & 0.2882 & 0.3184 & 0.3387 & 0.2968 & 0.3699 & 0.3215 \\ C\_ElegansNeural & **0.3464** & 0.3480 & 0.3869 & 0.3722 & 0.3902 & 0.3942 & 0.3869 \\ \hline \hline \end{tabular}
\end{table}
Table 3: Robustness indicator R-values of various centrality metrics on different datasets, with the method having the smallest R-value highlighted in bold.  
methods may overlook important information when assessing the importance of nodes, and their accuracy may not match that of the KCH.  
The reason KCH possesses extremely high monotonicity stems from its combination of global network information and local structural information to jointly assess the importance of nodes. As long as two nodes do not have completely identical neighbor structures and the same KS levels, KCH can distinguish the importance of different nodes. The slightly lower monotonicity of KCH compared to methods like HKS in the USpowerGrid network may be attributed to the presence of numerous peripheral nodes with only one neighbor, leading to a lack of distinguishing features for KCH in assessing the importance of these peripheral nodes. Overall, although KCH trails slightly behind HKS and CNC+ in terms of monotonicity, its accuracy surpasses that of HKS and CNC+, and its time cost is much lower than that of HKS. Therefore, KCH generally outperforms other methods.  
Figure 3 displays the rank distribution graphs of different methods on the Dolphins, USpowerGrid, WikiVote, and HepPh networks (with rank distribution graphs for all networks presented in Appendix B).