Link Prediction Based On Topological Structure And Spectral Analysis

Link prediction is one of the hot research topics in complex networks.It has great signif icance in the application of social networks,biological networks and transportation networks,etc.At present,in most of the link prediction algor ithms,topological properties of the network are used to calculate the similar ity of nodes.At the same time,in the existing prediction methods based on machine learning,additional attributes of nodes need to be obtained.For example,information such as the age and job of users in social networks is not easily accessible,which limits the universality of the algorithm.Therefore,this thesis considers the topological structure of the networks and introduces spectral analys is methods to study it.In the thesis,considering the two topological structures-degree and clustering coefficient-of the common neighbors,we propose a new index CDLP.The results of experiments on eight real network datasets show that CDLP index is superior to other indices based on local topolog ical features.It is proved that the more effective topological features are considered,the higher accuracy of the prediction results will be.In most of the existing methods,the similar ity of nodes needs to be calculated and the prediction results are susceptible to the changes of topological structure.However,we introduce spectral analysis method.First,we use the eigenvalues and eigenvectors calculated by the standardized Laplacian equation,map the nodes to the dimension space and calculate the similar ity distance as an attribute of edges.Then,the upper triangle(or lower triangle)of the adjacency matrix is used as a label attribute too.The two attributes are combined to form a new attribute set of the edges.Finally,it is transformed into a binary prediction for edges by the classification method of machine learning.The results of experiments shows that the method based on spectral analysis can obviously improve the prediction performance and the algorithm has good robustness.In order to further improve the prediction accuracy,we consider both the network topological features and the spectral analysis method.First,the average degree and the average clustering coefficient of the two nodes are regarded as the attribute of edges in experiments,respectively.Then,the set of edge attributes constructed by the average degree and the average clustering coefficient are respectively combined with the set of similarity distance attributes.Finally,the set of edge attributes constructed by the average degree and the average clustering coefficient are both combined with the set of similar ity distance attributes at the same time.The upper triangle of the adjacency matrix is still used as a label attribute.By comparison of experiment results,it is found that the result of the final combined method by two topological features with the similarity distance attribute set is best.The final combined method does not need additional information of the nodes,avoids the direct influence of the network topology changes and has better applicability.