基于矩阵填充的链接预测算法研究

发布时间：2018-09-07 19:56

【摘要】：近年来,随着web2.0技术的迅猛发展,社会网络的规模也不断发展壮大,复杂网络分析对研究者们来说成为一项重要的研究任务。而链接预测问题作为复杂网络分析的一个研究分支,其在社会网络、生物信息网络、食物网等诸多与人类生活密切相关的方面都有着广泛的应用价值。因此,本文深入学习了链接预测问题。在数据挖掘领域,链接预测问题扮演着十分重要的角色,其目的是根据网络已知的各类信息估计两个不相连的节点存在链接的概率。链接预测作为数据挖掘领域的重要研究内容,已经被研究许多年了。它被分为两种类型:一预测未知链接;二预测未来链接。第一种致力于挖掘应该存在但未被人所知的链接,第二种致力于预测现有网络中不存在但未来可能发生的链接。本文主要集中于预测未知的链接。现存的链接预测算法大体分为四类:一基于拓扑结构的链接预测;二基于社会学理论的链接预测;三基于机器学习的链接预测;四基于矩阵分析的链接预测。本文就第一点和第四点展开了深入的研究。提出了以下几点创新点:1.本文针对基于拓扑结构的链接预测算法进行改进,将CN算法和RA算法结合在一起,提出一种新的相似度度量方法CN-RA。这种方法不仅考虑社会网络中共同邻居数目,还考虑了单个共同邻居节点对节点相似度的影响,同CN算法、RA算法和其它基准的基于拓扑结构的算法相比,取得了更好的预测效果。2.本文提出一种多特征融合的链接预测框架。受到已有的基于矩阵填充的链接预测方法的启发,我们深入研究了增广拉格朗日乘子算法-ALM。使用邻接矩阵表示社会网络,由于社会网络邻接矩阵具有低秩性,因此我们可以使用ALM算法优化邻接矩阵,解决链接预测问题。基于此方法,本文提出了一种多特征融合的链接预测框架,将拓扑结构特征和低秩特征融合在一起,进行了实验验证。实验结果表明,这种框架与传统基于拓扑结构的方法和单独使用ALM算法相比,更进一步提高了预测效果。同时,这个框架还保证了可扩展性,可将其它特征(如节点属性信息、社会学信息)融合进来,进一步分析动态网络链接预测问题。为了验证以上两点的可行性与有效性,本文选取了三个真实数据集进行实验验证,分别为USAir数据集、Net Science数据集、Jazz数据集,使用CN、AA、PA、RA、Jaccard方法作为基准方法,使用ROC曲线和AUC值评估实验结果。实验结果表明,本文提出的方法得到了预期的预测效果,而结合了多特征的链接预测框架更是显著提高了预测效果。
[Abstract]:In recent years, with the rapid development of web2.0 technology, the scale of social network is also growing, complex network analysis has become an important research task for researchers. As a branch of complex network analysis, link prediction is widely used in social network, biological information network, food web and many other aspects closely related to human life. Therefore, this paper delves into the problem of link prediction. In the field of data mining, the problem of link prediction plays a very important role in estimating the probability of the existence of links between two disconnected nodes based on the known information of the network. As an important research content in the field of data mining, link prediction has been studied for many years. It is divided into two types: one predicting unknown links and the other predicting future links. The first is to mine links that should exist but are not known, and the second is to predict links that do not exist in existing networks but may occur in the future. This paper focuses on predicting unknown links. The existing link prediction algorithms are divided into four categories: link prediction based on topology; link prediction based on sociological theory; link prediction based on machine learning; and link prediction based on matrix analysis. In this paper, the first point and the fourth point of the in-depth study. Put forward the following points of innovation: 1. In this paper, the link prediction algorithm based on topology structure is improved, and a new similarity measure method, CN-RA., is proposed by combining CN algorithm with RA algorithm. This method not only considers the number of common neighbors in the social network, but also considers the influence of a single common neighbor node on the node similarity. Compared with the CN algorithm and other benchmark algorithms based on topology structure, this method is more effective than the traditional algorithm. Better prediction effect. 2. 2. In this paper, a link prediction framework based on multi-feature fusion is proposed. Inspired by the existing link prediction methods based on matrix filling, we deeply study the augmented Lagrangian multiplier algorithm-ALM. Because the adjacent matrix of social network is of low rank, we can use ALM algorithm to optimize the adjacent matrix and solve the problem of link prediction. Based on this method, a link prediction framework based on multi-feature fusion is proposed, which combines topology features with low-rank features, and is verified by experiments. The experimental results show that compared with the traditional topology based method and the ALM algorithm alone, the prediction effect of this framework is further improved. At the same time, the framework also ensures scalability, and other features (such as node attribute information, sociological information) can be combined to further analyze the dynamic network link prediction problem. In order to verify the feasibility and validity of the above two points, this paper selects three real data sets for experimental verification, one is the USAir dataset net Science dataset and the other is the CN,AA,PA,RA,Jaccard method. ROC curves and AUC values were used to evaluate the experimental results. The experimental results show that the method proposed in this paper can achieve the expected prediction effect, and the link prediction framework with multiple features can significantly improve the prediction effect.
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5;TP311.13

【相似文献】