随着信息技术的发展,随之而来的是海量的数据,这些网络数据具有数据量大、数据类型丰富等特点,其中也包含了很多潜在的富有价值的信息,如何从这些数据中挖掘出潜在的未知的信息一直是人们关注的重点,网络数据的链路预测作为数据挖掘领域重要的方法之一,因此受到了人们的密切关注。但是随着数据量的增加,传统的链路预测方法在解决大规模的网络数据的挖掘问题时,往往受到时间复杂度高、运算量大等问题的限制,从而不能够有效地应用于大规模的网络数据。为了进一步解决该问题,本文从降低时间复杂度和并行算法设计两方面考虑该问题,关于降低时间复杂度问题,通过抽样可以减少计算复杂度,但是抽样结果的质量与预测结果紧密相关,那么如何保证抽样的质量是抽样过程中的必须关注的核心问题之一;另外,并行框架的出现为有效地处理大规模数据提供了可能,关于链路预测问题也可以通过并行计算框架提升运算速度。针对第一方面,本文基于图勾勒技术对现有的链路预测方法进行扩展,提出了基于All Distances Sketches(ADS)技术的链路预测方法,根据勾勒的结果结合现有的预测方法,定义了基于ADS结构的链路预测方法,分析比较了 ADS技术在计算节点相似性时是如何降低时间复杂度的,同时给出了链路预测以及基于ADS技术的链路预测的具体算法;针对第二方面,由于Spark GraphX并行计算框架在图数据处理方面具备明显优势,因此本文基于Spark GraphX的开发平台设计并实现了 ADS的并行算法,同时设计实现了链路预测方法的并行算法,以及基于ADS技术的链路预测方法的并行算法,通过并行算法得出的实验结果进行对比分析,最后从算法运行时间和预测结果的准确性两方面分析验证了基于图勾勒技术的链路预测方法的有效性,实验结果表明基于ADS技术的链路预测算法可以保证一定预测精度,同时降低预测方法的时间复杂度,提升运算效率。