复杂网络中的抽样链接预测

• 作者: 戴彩艳 李斌 陈伯伦 陈崚
• 来源期刊: 浙江大学学报(工学版)
• 学科: 工学
• 关键词: 链接预测 随机游走 复杂网络 容错阈值 相似度误差 子图
• 年，卷（期）: 2017,（3）
• 所属期刊栏目: 计算机技术、电子通信技术
• 页码范围: 554-561
• 页数: 8页
• 分类号: TP391.1
• 字数: 6791字
• 语种: 中文
• DOI: 10.3785/j.issn.1008-973X.2017.03.017

摘要

针对传统相似度算法无法预测给定顶点存在的链接问题,以抽样方法为基础,提出一种对复杂网络进行链接预测的方法,找出用户感兴趣节点的相关链接.根据用户感兴趣的节点,使用随机游走的方法,构造一个子图.设定该子图的大小使相似度估计值的误差小于给定的容错阈值.该方法仅在一个小的包含全局信息的子图上进行相似度计算,可以使计算时间大大减少.实验结果表明,算法的时间复杂度与数据集大小呈线性关系,基于局部指标的常见邻居(CN)算法、Jaccard以及PA指标算法的时间复杂度与数据集大小呈平方关系,以全局拓扑路径为基础的Katz算法的时间复杂度与数据集大小呈立方关系.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈崚	南京航空航天大学计算机科学与技术学院	150	1914	19.0	39.0
3	李斌	扬州大学信息工程学院	83	372	10.0	16.0
4	戴彩艳	南京航空航天大学计算机科学与技术学院	4	9	2.0	3.0
7	陈伯伦	南京航空航天大学计算机科学与技术学院	2	14	1.0	2.0