基于谱分析方法的链路预测算法研究

发布时间：2018-06-21 05:01

本文选题：复杂网络 + 链路预测　；参考：《兰州大学》2017年硕士论文

【摘要】：生活中的众多真实系统都可以看作一个复杂网络系统,链路预测作为复杂网络非常重要的研究课题,其重要作用就是研究这些网络的演化机制或者发展方向,例如在蛋白质网络中想要知道蛋白质之间的相互作用、社交网络中节点之间是否成为朋友。因此,链路预测的研究具有重要的现实意义,在复杂网络的领域里作为重要的研究分支之一。链路预测的研究得到了大家的广泛关注,其算法大多通过对网络拓扑结构进行研究分析,对节点相似性进行计算等方法来判断节点之间有无连边。但是大多数的链路预测算法对于网络拓扑结构的考虑仅限于网络的局部信息或者路径信息,近几年新的社交网络链路预测算法中需要得知节点自身的额外属性信息,但是要得到这种额外信息非常困难,所以实用度不是很高。本文提出了一种关于直接针对边的基于机器学习的链路预测算法,将谱分析引入算法当中,通过拉普拉斯矩阵的特征值和特征向量将节点映射到二维空间,然后将对节点的相似性计算直接转化成对边的分类预测问题。论文采用一个测试数据集和六个真实网络数据集证明了算法的可行性,同已有的算法的评价结果进行了比较,评价了论文提出算法的有效性。在此基础上,论文为了提高算法的预测效果,考虑社团结构对于链路预测结果的影响(在同一个社团中的节点有连接的几率大于社团间的连接),引入了新的相似度计算方法,即基于角距离的谱分析方法,经证明,利用该相似度计算方法可划分得到更好的社团结构。将引入角距离的改进算法经过同样的一个测试数据集和六个真实网络数据集的实验验证之后,证明改进算法确实能够提高链路预测效果。在提高预测效果的基础上,可以发现在社团结构明显的数据集上的预测能力提升能力更好。
[Abstract]:Many real systems in life can be regarded as a complex network system. As a very important research topic of complex network, link prediction plays an important role in studying the evolution mechanism or development direction of these networks. For example, in a protein network you want to know how proteins interact, and whether nodes in a social network are friends. Therefore, the research of link prediction is of great practical significance, and it is one of the important branches in the field of complex networks. The research of link prediction has been paid more and more attention. Most of its algorithms are based on the analysis of network topology and the calculation of node similarity to judge whether there are links between nodes. However, most of the link prediction algorithms only consider the local information or path information of the network topology. In recent years, the new link prediction algorithms of social networks need to know the additional attribute information of the nodes themselves. But getting this extra information is very difficult, so the utility is not very high. In this paper, a link prediction algorithm based on machine learning is proposed. Spectral analysis is introduced into the algorithm and nodes are mapped to two-dimensional space by eigenvalues and Eigenvectors of Laplace matrix. Then, the similarity calculation of nodes is transformed directly into the problem of classification and prediction of opposite edges. In this paper, a test data set and six real network data sets are used to prove the feasibility of the algorithm, and compared with the evaluation results of the existing algorithms, the validity of the proposed algorithm is evaluated. On this basis, in order to improve the prediction effect of the algorithm, considering the influence of the community structure on the link prediction results (the probability of the nodes in the same community being connected is greater than the connection between the communities, a new similarity calculation method is introduced. The spectral analysis method based on angular distance has been proved to be better for community structure by using this similarity calculation method. The improved algorithm with angle distance is verified by the same test data set and six real network data sets. It is proved that the improved algorithm can improve the link prediction effect. On the basis of improving the prediction effect, it can be found that the prediction ability on the dataset with obvious community structure is better.
【学位授予单位】：兰州大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5;TP181

【相似文献】