A node ranking method: Reducing structural indexes to avoid evaluation redundancy

Node ranking is of great significance for understanding the structure and function of graphs. The single index or comprehensive index on node ranking has some certain information one-sidedness or redundancy weakness. This work focuses on critical node identification and proposes a structural index reduction method (SIRM) to rank nodes by reducing information redundancy, which is an measurement method for any network structure. SIRM integrates as many indexes as possible without evaluation redundancy to build a comprehensive evaluation index system. The main idea of reducing evaluation redundancy is to model indexes into an association graph based on grey correlation degrees of them, and then cluster indexes into categories in which each pair of indexes are equivalent in one community. One index is randomly chosen as the representative element from each category consists of the evaluation indexes set in SIRM, and finally the node is evaluated by the linear combination of the representative indexes. Applications on sets of artificial graphs and real-world graphs show that SIRM displays favorable feasibility and efficiency. In addition, comparing SIRM with the single index or comprehensive index approaches and benchmarks, SIRM has preferable features of graph connectivity and graph efficiency. SIRM extends clustering analysis methods from the perspective of association graphs in a sense, providing a more accurate alternative method for graph analysis.