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

被引：15

作者：

饶君

吴斌

东昱晓

机构：

[1] 北京邮电大学北京市智能通信软件与多媒体重点实验室

来源：

软件学报 | 2012年 / 23卷 / 12期

关键词：

链路预测; 复杂网络; 局部信息; 并行算法; MapReduce;

D O I：

暂无

中图分类号：

TP393.0 [一般性问题];

学科分类号：

摘要：

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

引用

页码：3175 / 3186

页数：12

共 5 条

[1] Predicting missing links via local information[J] . Tao Zhou,Linyuan Lü,Yi-Cheng Zhang.The European Physical Journal B . 2009 (4)
[2] Prediction and ranking algorithms for event-based network data[J] . Joshua O’Madadhain,Jon Hutchins,Padhraic Smyth.ACM SIGKDD Explorations Newsletter . 2005 (2)
[3] Link mining[J] . Lise Getoor,Christopher P. Diehl.ACM SIGKDD Explorations Newsletter . 2005 (2)
[4] Evolution of networks
Dorogovtsev, SN
Mendes, JFF
[J]. ADVANCES IN PHYSICS, 2002, 51 (04) : 1079 - 1187
[5] A NEW STATUS INDEX DERIVED FROM SOCIOMETRIC ANALYSIS
KATZ, L
[J]. PSYCHOMETRIKA, 1953, 18 (01) : 39 - 43

← 1 →