Research On Spurious Linking Method Based On Third Order Path And Degree Centrality

Link prediction and spurious link problem is an important bridge between complex network and information science,which plays an increasingly important role in the practical application.In recent years,the research of link prediction problem has become the focus of attention,scholars have proposed a lot of prediction algorithm for the structure and characteristics of the network,and through these algorithms to explore and analyze the evolution of the structure of the target network,but there are few studies on the spurious links in the network.The study of the reliability and importance of spurious links can better exploit the structural features of the network.At present,many scholars think link prediction method can be used to identify spurious links directly,but in many networks to identify spurious link effect will not be very satisfied because of different point of view in prediction.In view of the problems above,this paper makes the experimental analysis on 8 real data sets,and verifies that the evaluation performance decline after applying link prediction algorithm on the spurious link.Then put forward two kinds of spurious link index,first method is the resource allocation index based on three order path,which consider the three order path effects based on two order allocation of resources.Another method is DCHPI index based on the CN index and HPI index.The two methods are validated in different real networks respectively and found that both methods can produce higher prediction accuracy.The dissertation is divided into five chapters.Chapter One is an introduction,mainly introduces the research background and the research significance of this article,the current research situation at home and abroad,and briefly explains the content and innovation of this paper.Chapter Two is the introduction of link prediction,which describes the link prediction problem,introduces the research methods and evaluation indicators of link prediction briefly,and introduces the problem of spurious link briefly.Comparing the prediction effect of link prediction method for spurious link by experi-ment in chapter three.Firstly,we discuss the prediction effect of local similarity index under the same partition ratio p value,and find out that in spurious link,HPI index is the best,LHN is the second.In link prediction,RA index is the best,AA is the second.It shows that the performance of the same index in spurious link and link prediction is not proportional directly.Secondly,the prediction effect of the local similarity index under the different par-tition ratio p value is discussed,and it is found that in the same data set,there are little difference between the AUC values when the p value is small,but with the increase of p value,the AUC value decreased gradually,and the difference between AUC of these indexes increased gradually.It shows that the p value will have a greater impact on the prediction results.Finally,the prediction effect of semi-local and global similarity index is discussed,and it is found that CN index is better than these two indexes from the comprehensive consideration.The discussion of these three parts fully shows that the performance of link prediction algorithm will change greatly when it is directly applied to spurious link.Chapter Four introduces two methods of spurious link.The first is resource allocation index based on third-order path,which combines RA index of third-order path with HPI index.The similarity between nodes is described from two structural features,and compared with the real network,the effectiveness of the method is verified.The second is the HPI index based on nodal centrality.This method takes into account the degree centrality of nodes.And the parameter ? is introduced to estimate the influence of node degree on the similarity score value.The effectiveness and feasibility of the new method are verified by comparison with other methods on 9 real network data sets.Chapter Five is the conclusion.This paper makes an experimental analysis on the evaluation effect of the link prediction method on the spurious link,which find that the link prediction method can not be used in the identification of the spurious link directly.The two spurious link indexes proposed in this paper can be used to identify the spurious link in the network and improve the prediction accuracy of the algorithm.