面向社交网络的链接预测算法研究

发布时间：2020-06-16 12:54

【摘要】：信息技术的飞速发展使互联网渗透到社会生活的方方面面,社交类应用已经成为人们生活中不可或缺的一部分,并形成了规模庞大、信息丰富的社交网络。作为社交网络数据挖掘领域重要的研究内容之一,链接预测可以帮助学者评估网络形成机制、完善网络中缺失的信息、预测网络结构,可以帮助用户快速发现感兴趣的内容,从而应对信息过载等问题,对于学术研究和商业应用都有着重要的价值,吸引了诸多学者的关注。当前,面向社交网络的链接预测仍然存在诸多难点。首先,社交网络作为以人为主体构建的网络,个体并非完全独立,有多方面因素会影响个体行为进而影响到网络中链接的变化,在研究链接预测时,应当对这些因素加以研究。其次,社交网络规模较大,包含信息庞杂,仅基于节点间相似度预测链接时,往往存在信息利用不充分的问题,影响链接预测的效果。随着人们要求的提高和网络规模的扩大,如何合理挖掘网络上的信息来预测链接成为了重要的研究内容。根据当前的研究现状,本文的贡献如下:(1)节点的中心性对其建立新链接的情况有一定影响,研究结合中心性的链接预测算法,首先提出一种新的节点中心性评价算法:LRC算法。经典的局部中心性忽略了节点间的相互作用,LRC算法基于自我中心网络提出关联强度,并用其表示直接相邻节点间的相互影响,综合节点的局部环境和节点间相互作用共同进行中心性评价。实验表明,LRC算法能有效发现关键节点,对节点中心性评价的准确性优于对比算法。(2)对于面向社交网络的链接预测来说,传统的基于相似度的链接预测算法对节点间关系和社交网络特性考虑不足,研究基于改进相似度的链接预测算法。提出一种基于中心性的节点间相似度链接预测算法:LP-LRC算法,根据社交网络的弱连接特性和节点的LRC值,提升低中心性的共同邻居在新链接建立过程中发挥的作用,降低高中心性的共同邻居的作用,更符合社交网络特点。提出一种基于关联强度的链接预测算法:RWCN算法,以节点间关联强度区分不同的共同邻居对新链接建立的影响,改进经典的CN算法。实验表明,LP-LRC算法和RWCN算法在实验网络上的性能优于对比算法,在部分网络上优于部分改进算法。(3)针对可获取领域信息的社交网络,研究基于节点间多特征的链接预测算法,提出两个基于领域信息特征的提取方法,描述节点在网络中的活跃度和节点间兴趣相似度,与基于拓扑结构获取的特征结合,基于节点间多特征预测链接。DBLP上的实验表明,本文设计的基于领域信息提取的特征信息增益更高,能有效提升链接预测性能。
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5;TP301.6
【图文】：

邻接矩阵,社交,示例,访问速度

为了获得更快的访问速度选择基于邻接矩阵的存储方式。图2.1 中左图展示了一个小型社交网络，右图展示了将其抽象为含 4 个节点 3 条边的无向无权图的邻接矩阵。图 2.1 社交网络及其邻接矩阵示例

预测问题,链接,示例,相似度

图 2.2 链接预测问题示例2.2.2 基于相似度的链接预测一般的，认为共同特征越多的两个节点间的相似度越大，但由于节点的属性等关键信息往往难以获得，因此基于相似度的链接预测算法大都基于网络拓扑计算节点间相似度，定义表示基于相应算法得到的节点和节点之间的相似度。下面介绍其中基于局部信息的算法、基于路径的算法以及基于随机游走的算法。1.基于局部信息的相似度算法基于局部信息的算法基于网络的局部拓扑结构计算节点间相似度来预测链接。（1）CN 指标(Common Neighbors Index)若与互为邻居节点，同时和也互为邻居节点，则称是和的共同邻居。CN 指标认为，两个节点之间的共同邻居个数与他们之间的相似度情况成正比，共同邻居越多的节点间形成链接的可能性越大。定义如下：

【参考文献】