论文部分内容阅读
随着网络技术的飞速发展以及人们生活节奏的加快,在线社交以其方便快捷的优势越来越受到广大网民的追捧,链接预测技术已经成为社交网络平台自我优化的重要一环。社交网络用户量与结构的日益庞大,为链接预测技术带来了前所未有的挑战。针对目前常用的链接预测方法精确度低、预测速度慢且无法发现社交网络中潜在的隐藏链接等问题,本文将重叠社区发现技术引入到链接预测中,提出了基于qLFMflp重叠社区发现算法的LPBOCD链接预测模型。本文的创新及工作主要为以下三个方面:(1)针对目前常用的链接预测方法的预测精确度低、运行时间长且忽视了隐藏链接的发现与利用等问题,本文提出了一种基于qLFMflp重叠社区发现算法的LPBOCD链接预测模型。该模型将重叠社区发现技术与链接预测技术相结合,可以有效地减少链接预测范围并发现重叠社区间链接信息,以此提升运行速度和精确度。(2)为LFM重叠社区发现算法进行了改进并提出了能够快速分区并适用于链接预测技术的qLFMflp重叠社区发现算法。首先本文通过为节点添加“访问”标志解决了LFM算法在社区扩张过程中出现的同一节点反复被加入与剔除问题。其次针对LFM算法结果只给出社区聚类集合未保留节点社区归属信息的问题,本文提出对节点进行二级编码,在保留节点信息的同时保留节点的社区信息使其能够快速定位节点所在的社区及与之重叠的社区,适用于基于重叠社区结构的链接预测技术。最后利用中心节点解决LFM算法每扩张一个节点就重复计算社区内所有节点适应度的问题。通过在LFR基准网络上进行对比实验,验证了本文提出的qLFMflp算法比LFM算法的NMI指标值平均提高了7.3%,执行时间能够减少到原来的一半,在社区划分准确性和执行速率上都显示出了巨大优势。(3)设计并实现了LPBOCD链接预测模型,在Facebook网络数据上进行十折交叉实验验证,并使用精确度、召回率、F1指标和执行时间对模型性能进行评估。实验表明,本文提出的链接预测方法比CN、Jaccard、RA、LP、Katz(ω=0.1)五种常用的链接预测方法中最好的结果相比在精确度上平均提高了5%,在召回率上平均提高了11.4%,在F1指标值上平均提高了8.8%。同时,跟执行速率最快的CN指标花费的1分55秒相比,本模型只需1秒表现出了巨大优势,验证了模型的可行性与优越性。