MapReduce环境下的并行复杂网络链路预测

• 作者: 东昱晓 吴斌 饶君
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 链路预测 复杂网络 局部信息 并行算法 MapReduce
• 年，卷（期）: 2012,（12）
• 所属期刊栏目: 计算机网络与信息安全
• 页码范围: 3175-3186
• 页数: 12页
• 分类号: TP393
• 字数: 7983字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2012.04206

摘要

为使链路预测应用于大型复杂网络,设计并实现了一种基于 MapReduce 计算模型的并行链路预测算法,包含了9种基于局部信息的相似性指标,在稀疏网络上的时间复杂度为O(N).首先,在公共数据集上验证了并行算法的有效性,随着抽取因子的增加,召回率升高而准确率下降.在不同类型的10个大规模复杂网络数据集上的实验结果表明,基于MapReduce计算模型的并行链路预测算法比传统算法具有更高的效率,算法的运行时间随着并行程度的增加而下降.提出并证明了AUC(area under a receiver operating characteristic curve)评价指标的上下界,实验表明,上下界的中值和实际AUC值很接近,并且AUC评价指标侧重于预测分数值是否为0而不是分数值的大小.在网络拓扑性质中,平均聚集系数对AUC值的影响最大,并且AUC值随着网络平均聚集系数的增加而提高.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	吴斌	北京邮电大学北京市智能通信软件与多媒体重点实验室	80	1409	15.0	36.0
2	饶君	北京邮电大学北京市智能通信软件与多媒体重点实验室	2	42	2.0	2.0
3	东昱晓	北京邮电大学北京市智能通信软件与多媒体重点实验室	3	85	3.0	3.0