The Research On New Methods For Vital Nodes Identification And Link Prediction On Complex Network

The recent study of complex networks has directed most interests to unfolding the distinct roles played by the micro-level,such as individual nodes and links.In this paper,the research has focused on methods for vital node identification and link prediction on complex networks.On the one hand,measuring the importance of nodes and then identifying vital nodes has important theoretical implications for understanding the structure,evolutionary processes and dynamics of networks.On the other hand,the link prediction algorithm can be used to extract missing information,identify spurious interactions,evaluate mechanisms through which networks evolve,and so on.The study in the paper is thus about the hotspots and difficulties of complex network research.First of all,on the basis of a great deal of domestic and foreign literature,a comprehensive survey is made on vital node identification and link prediction.Secondly,according to the problems of existing methods,new methods for vital node identification and link prediction on complex networks are proposed.Finally,by using various effective evaluation methods and standards,the validity of the proposed methods are proved through experiments on multiple real networks.The main contributions are as follows:(1)Covered level based methods are proposed to identify vital nodes.Firstly,the covered level of a node is proposed.Secondly,on the basis of k-shell decomposition,the covered level based vital node identification method is given.Finally,experiments of two types of evaluation standard prove that the covered level is better.This method overcomes the weaknesses of coreness that are assigned by the k-shell decomposition process,including being highly coarsegrained,different connecting patterns not being considered,fake cores,and so on.Moreover,the covered level reflects the distance of a node from the edge of the network,which is more fine-grained,and better describes the positions of the structural hole occupied by nodes.(2)Three H-index based link prediction methods are proposed: H-Salton,HSorenson,and the H-AA algorithm.Firstly,through the empirical analysis of citation network characteristics,the H-index,which is more suitable for measuring the importance of citation network nodes,is chosen.Secondly,on the basis of existing methods,the new H-index based link prediction methods are proposed.Finally,experiments on real citation networks demonstrate that using the H-index to measure the importance of citation network nodes can significantly improve the prediction accuracy of link prediction methods applied to citation networks.(3)A complex network evolution mechanism called knowledge dissemination(KD)and a KD-based link prediction method(KDLP)are proposed.Firstly,knowledge dissemination is proposed with the assumption of knowledge disseminating through the paths of a network.Accordingly,a new link prediction method-knowledge dissemination based link prediction(KDLP)-is proposed on the basis of KD.Moreover,experiments on six real-world networks demonstrate that KDLP is a strong link prediction method which performs at higher prediction accuracy than four well-known similarity measures including common neighbors,the local path index,average commute time and the matrix forest index.Furthermore,based on the common conclusion that an excellent link prediction method reveals a good evolving mechanism,the experiment results suggest that KD is a considerable mechanism through which complex networks form and evolve.