常雅文

(西安航空学院， 西安 710077)

0 引言

复杂网络链路预测由于在社交网络、信息通信等社会方面的广泛应用，现已成为数据挖掘的主要研究方向，已成为学术界关注的热点[1]。网络链路预测作为一种预测方式主要是通过已知网络拓扑结构和网络节点属性等信息预测网络中未产生连边的节点产生连接的可能性[2]。传统的链路预测算法以节点属性为特点，譬如马尔科夫链或机械学习等算法，尽管算法预测精度高，但由于计算复杂度高、计算中涉及的非普适性参数应用的限制，导致算法使用受限[3-4]。另一类传统链路算法则以网络结构为特点进行最大似然估计，文献[5]中介绍了一种网络层次结构为基础的链路预测算法，并显示该类算法在层次结构明显的网络中具有较高的预测精度，但该类算法的计算复杂度高。

与传统的链路预测算法相比，以网络拓扑结构为基础的链路预测算法通用性强，且网络拓扑结构极易获得。但在处理大规模复杂网络链路时，由于算法复杂度和单台计算机内存限制，处理速度慢，且准确性不足。MapReduce[6]作为Google公司2004年提出的可以并行处理海量数据的编程模式和任务调度模式，可以通过屏蔽底层实现细节减少并行编程复杂度，提高编程效率而具有广泛应用。基于MapReduce编程时，开发人员只要考虑应用程序本身特性，无需考虑集群处理，将其交由平台处理。因此在MapReduce背景下进行复制网络链路预测分析具有重要的使用价值和意义。……