主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
饶君,吴斌,东昱晓.MapReduce 环境下的并行复杂网络链路预测.软件学报,2012,23(12):3175-3186
MapReduce 环境下的并行复杂网络链路预测
Parallel Link Prediction in Complex Network Using MapReduce
投稿时间:2011-07-18  修订日期:2012-02-28
DOI:10.3724/SP.J.1001.2012.04206
中文关键词:  链路预测  复杂网络  局部信息  并行算法  MapReduce
英文关键词:link prediction  complex network  local information  parallel algorithm  MapReduce
基金项目:国家自然科学基金(90924029, 60905025, 61074128)
作者单位E-mail
饶君 北京邮电大学 北京市智能通信软件与多媒体重点实验室,北京 100876 raojun_06@bupt.edu.cn 
吴斌 北京邮电大学 北京市智能通信软件与多媒体重点实验室,北京 100876  
东昱晓 北京邮电大学 北京市智能通信软件与多媒体重点实验室,北京 100876  
摘要点击次数: 3420
全文下载次数: 4236
中文摘要:
      为使链路预测应用于大型复杂网络,设计并实现了一种基于MapReduce 计算模型的并行链路预测算法,包含了9 种基于局部信息的相似性指标,在稀疏网络上的时间复杂度为O(N).首先,在公共数据集上验证了并行算法的有效性,随着抽取因子的增加,召回率升高而准确率下降.在不同类型的10 个大规模复杂网络数据集上的实验结果表明,基于MapReduce 计算模型的并行链路预测算法比传统算法具有更高的效率,算法的运行时间随着并行程度的增加而下降.提出并证明了AUC(area under a receiver operating characteristic curve)评价指标的上下界,实验表明,上下界的中值和实际AUC 值很接近,并且AUC 评价指标侧重于预测分数值是否为0 而不是分数值的大小.在网络拓扑性质中,平均聚集系数对AUC 值的影响最大,并且AUC 值随着网络平均聚集系数的增加而提高.
英文摘要:
      To apply link prediction methods into large-scale complex network, this paper designs and implements a parallel link prediction algorithm based on MapReduce, which includes nine similarity Indices via local information. The parallel link prediction algorithm has a time complexity of O(N) in sparse networks. First, the paper verifies the validity of the algorithm on public datasets, increase in the extraction factor, recall ascends, and precision descends. The experimental results on ten large-scale datasets of variety network types show that the parallel link prediction algorithm is more effective than traditional ones, and its running time decreases with more compute units. The upper and lower bounds of AUC (area under a receiver operating characteristic curve) are proposed. The experimental results show the median of the upper and lower bounds are close to the real value of AUC, which focuses on whether prediction score is zero rather than the actual score value. The network average clustering coefficient has the greatest impact on AUC among most topological features and AUC rises as the network average clustering coefficient increases.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利