二分网络链接预测的研究及应用

发布时间：2018-01-30 18:52

本文关键词： 二分网络链接预测潜在边矩阵完全数据恢复非负矩阵分解推荐　出处：《扬州大学》2017年硕士论文　论文类型：学位论文

【摘要】：在自然界与人类社会活动中,各种复杂类型的系统都可以转化成相应的复杂网络,比如经济系统、生物系统、群体生态系统以及其他领域内系统。复杂网络分析领域的一个重要研究方向是它的链接预测。现在,链接预测问题在社会学、人类学、信息科学以及计算机科学等各个领域都受到了广泛的关注。相对于单分网络,二分网络不仅是复杂网络中重要的表现形式之一,而且在现实社会复杂网络中具有普遍性,已经成为复杂网络的重要研究对象。在现实社会中,许多复杂网络都自然地呈现出二分结构。譬如:作者与文章的合作网络、演员与影视作品的合作网络、投资者与股份制公司的股份合作网络、疾病与基因的作用网络、俱乐部成员与俱乐部举办活动的参与网络、观众与歌曲的喜好网络、P2P系统中终端计算与交互数据的网络等。因此,二分网络链接预测对于研究复杂网络有非常重要的理论意义和实用价值。譬如,在学术圈的探测、功能分析、推荐系统、疾病诊断以及链接预测等方面都有很多重要的应用。虽然已有一些工作提出了对于二分网络链接预测的算法,但是这些算法都具有复杂度较高、预测困难等问题,不能应用于大规模网络。本文针对以上问题,研究二分网络链接预测的有效算法,主要工作以及研究成果有:(1)我们提出了基于投影的二分网络链接预测算法。算法首先将二部图投影到一个单部图,在此基础上定义了潜在边的概念,使得对二分网络链接预测仅在潜在边中进行,大大降低了预测算法的复杂度。我们定义了潜在边所覆盖的模式以及模式的权重,通过潜在边所覆盖的模式的权重来计算潜在边的可信度,作为该潜在边上存在实际链接的评分。实验结果表明,所提出的算法能够有效地提高链接预测的速度和结果的精度。(2)针对二分网络中数据存在的高维稀疏性特点,受压缩感知中对缺失数据恢复方法的启发,提出基于低秩矩阵完全的网络链接预测算法。已有的链接预测算法难免受数据稀疏性的影响而降低预测的准确性,基于低秩矩阵完全的网络链接预测算法可以在不改变原有数据的情况下恢复缺失数据并进行填充,从而对未链接的边进行预测。通过大量的对比实验验证,所提出的算法可以取得较高的预测精度。(3)在实际的推荐问题中,由于数据的高维稀疏性等问题存在,使得推荐的过程耗时长,算法时间复杂度高。已有的算法对于实时更新的网络的推荐准确度较低。我们在二分网络上提出基于非负矩阵分解的动态推荐算法。算法主要针对两种经常出现的数据更新情况。第一种是针对用户评分矩阵中用户修改评分的情况,第二种是针对用户评分矩阵中新增加用户评分向量的情况。算法的主要思路是运用非负矩阵分解方法,将原始矩阵分解成两个非负的基矩阵和权重矩阵。在动态更新数据时,根据前一时刻非负矩阵分解的中间结果进行更新,这样能够极大地缩短动态推荐时的等待时间。在推荐时,我们采用基于K近邻的资源分配策略,这种方法能够降低数据的存储空间。实验结果表明,算法能够在快速完成动态推荐的同时保证较高的推荐准确度。
[Abstract]:There are many important applications in complex networks , such as economic system , biological system , group ecosystem and other fields . ( 3 ) In the practical recommendation problem , due to the high - dimensional sparsity of data , the proposed algorithm is time - consuming and time - complexity . The proposed algorithm is based on the non - negative matrix factorization method . The second is to update the user ' s score vector in the user ' s scoring matrix . The first is to use the non - negative matrix factorization method to decompose the original matrix into two non - negative matrix and weight matrices .

【学位授予单位】：扬州大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【相似文献】