New Algorithms On Multivariate Evaluation For Node Centrality And Community Detection In Complex Networks

The research on the qualitative and quantitative characteristics can reveal the universal rules and unknown information in the complex network, which has important significance in various fields of computer science, physics, biology, sociology, mathematics, etc. The central node identification and community structure detection are always hot issues in complex network. Researches on these topics have significance in explaining the characteristics of network, understanding the structure of network, recognizing the networks and instructing the network behavior.The major researches of this paper include the multivariate evaluation for node centrality and the community structure detection based on node centrality in complex networks.The main research content and innovations are as follows:By considering the varioussingle-indicators which contain eigenvector centrality, betweenness centrality, closeness centrality, degree centrality, mutual-information centrality, etc., and compared with mainstream dimension reduction algorithms, a new multi-indicator evaluation algorithm (MI-LDA) for node centrality has been proposed. This new algorithm can solve the problems of one-sidedness and instability with some single-indicator evaluation methods, and the issues of high computational complexity and inaccuracy in some multi-indicator evaluation algorithms. This algorithm projects the high-dimensional pattern sample to a best sample vector space, and the feature space dimension is compressed. The experimental results show that this proposed algorithm can identify the central nodes efficiently, and has lower complexity than other mainstream dimension reduction algorithms.To improve the accuracy of evaluation on node centrality, another new multi-indicator evaluation algorithm (MI-LLE) for identifying central nodes is studied. The multi-indicator values are regarded as initial data inputs. Under the condition of remaining the neighbor nodes, with the thought of minimizing the cost function, the data dimension reduction has been converted into characteristic decomposition. After that, this algorithm can project the high dimensional model sample to the optimal discriminant vector space and compress the feature space, and finally, the central nodes can been found. The simulation results indicate that this studied algorithm is more accurate than other mainstream dimension reduction algorithms.Because the central node is also the center of community in most networks, a novel algorithm Infomap-SA based on node centrality for detecting community is studied. This new algorithm indetifies the central nodes by LDA algorithm, and then orders the nodes by descending order. After that, the Infomap and SA algorithms are integrated to optimize the modularity function. The simulation results indicate that this algorithm can identify the communities accurately and efficiently, and has higher values of modularity as well as density and lower computable complexity than Infomap algorithm. Furthermore, the Infomap-SA is more suitable for community detection of large-scale network.By making full use of the advantages of global hierarchical clustering algorithm CNM, and combing with the thought of node centrality, a new algorithm CNM-Centrality for detecting communities is proposed. Based on the fast greedy clustering algorithm CNM, this new algorithm identifies the central nodes using PageRank algorithm, and then optimally divides the central nodes and their neighbor nodes into correct communities. The experimental results show that this new algorithm can detect the communities accurately and efficiently. Furthermore, this algorithm can also acquire higher values of modularity and NMI than the CNM, Infomap, and Walktrap algorithms.This paper studies and realizes the multi-indicator evaluation algorithms MI-LDA and MI-LLE for identifying central nodes, and the community detection algorithms Infomap-SA and CNM-Centrality based on node centrality. These new algorithms are verified in real-world networks and computer-generated networks based on LFR-benchmark, and compared with mainstream dimension reduction algorithms and community detection algorithms. The experimental results indicate that these new algorithms have higher accuracy and effectiveness, and are of great significance in both theory and practice.