# A Complex Network Important Node Identification Based on the KPDN Method
## 5 Results and Analysis
### Result of Monotonicity of Different Methods  
This paper measures the monotonicity of various algorithms. The higher the monotonicity of the algorithm, the stronger the ability of the method to determine a unique ranking. The bold text in Tables 4 and 5 corresponds to the optimal value.  
Although the monotonicity is not the best on some networks, the monotonicity of the KPDN method is higher than that of other algorithms on larger networks.  
By comparing Tables 4 and 5, we can see that for real-world networks of scale \(10^{3}\)-\(10^{4}\), the monotonicity of our proposed method is second only to the PageRank method, but for networks of scale \(10^{4}\)-\(10^{5}\), the monotonicity of both the KPDN method and PageRank rank high or first. Therefore, our proposed method also has some advantages in monotonicity for larger-scale networks.  
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Methods** & **Email-Univ** & **US-Airports** & **Power-Eris1176** & **Bio-Grid-Worm** & **p2p-Gnutella08** & **Fb-Pages-Government** \\ \hline KPD & 99.8463\% & 99.7662\% & 93.6236\% & 96.9196\% & 97.9375\% & 99.9788\% \\ KPDN & 99.9978\% & 99.8689\% & 97.8811\% & 97.9240\% & 99.9841\% & 99.9990\% \\ DC & 89.0558\% & 85.0127\% & 71.8568\% & 43.2396\% & 76.4186\% & 95.3086\% \\ KSHELL & 81.2117\% & 83.4311\% & 65.3067\% & 36.6958\% & 60.2274\% & 93.1956\% \\ CC & 99.9719\% & 99.8235\% & 98.7163\% & 97.8977\% & 99.9827\% & 99.9958\% \\ DWT & 98.8019\% & 99.8154\% & 94.8756\% & 94.7545\% & 92.7645\% & 99.3225\% \\ CI & 96.5451\% & 91.5538\% & 97.9252\% & 48.2129\% & 85.2549\% & 99.4984\% \\ WL & 99.8790\% & 99.8104\% & 94.1200\% & 96.9638\% & 97.7698\% & 99.9765\% \\ HC & 99.9981\% & 99.8761\% & 99.0951\% & 97.9289\% & **99.9876\%** & 99.9990\% \\ INCC & 87.6090\% & 88.3489\% & 98.7560\% & 10.9898\% & 21.1736\% & 98.3378\% \\ PR & **99.9981\%** & **99.9948\%** & **98.9275\%** & **97.9340\%** & **99.9876\%** & **99.9990\%** \\ \hline \hline \end{tabular} Note: Due to the inconsistency in the size of the number of nodes \(n\) and the number of edges e in different networks, we retain the number of nodes \(n\) and the number of edges when calculating time and space complexity. According to the actual complexity network, subsequent researchers can calculate and compare by themselves with the size of \(<k>\) (this paper considers the complexity of \(<k>=\frac{e}{n}\) to be of the order of \(O(1)\)).  
\end{table}
Table 4: Monotonicity results of real-world networks (scale \(10^{3}\)–\(10^{4}\) ).  
\begin{table}
\begin{tabular}{c c c} \hline \hline
**Methods** & **Time Complexity** & **Space Complexity** \\ \hline DC & \(O(n)\) & \(O(n)\) \\ K-shell & \(O(n+n\log n+e)\) & \(O(2n)\) \\ CI & \(O(n+\frac{e^{2}}{n})\) & \(O(n+\frac{e^{2}}{n})\) \\ BC & \(O(n^{3})\) & \(O(n^{3})\) \\ WL & \(O(e+n)\) & \(O(e+n)\) \\ DWT & \(O(n+e+\frac{e^{2}}{n})\) & \(O(n+2e)\) \\ HC & \(O(n^{3})\) & \(O(n^{3})\) \\ CC & \(O(n^{3})\) & \(O(n^{3})\) \\ Pagerank & \(O(2n+e)\) & \(O(2n+e)\) \\ INCC & \(O(n+\frac{e^{2}}{n}+2\frac{e^{2}}{n^{2}}+\frac{e^{4}}{n^{2}}+2e)\) & \(O(5n)\) \\ KPD & \(O(n+n\log n+e)\) & \(O(3n)\) \\ KPDN & \(O(2n+n\log n+e+\frac{e^{2}}{n})\) & \(O(4n+e)\) \\ \hline \hline \end{tabular} Note: Due to the inconsistency in the size of the number of nodes \(n\) and the number of edges e in different networks, we retain the number of nodes \(n\) and the number of edges when calculating time and space complexity. According to the actual complexity network, subsequent researchers can calculate and compare by themselves with the size of \(<k>\) (this paper considers the complexity of \(<k>=\frac{e}{n}\) to be of the order of \(O(1)\)).  
\end{table}
Table 3: Time and space complexity of different methods.