1.1研究目的

本文的研究目的主要是对经典、前沿链接预测算法进行调研、对比和评估各个算法准确性和开销，对图数据进行降维预处理后进行链接预测，从而提高链接预测算法的性能和准确性。

1.2 研究意义

图数据是一类重要的数据，可以描述丰富的信息及信息之间的依赖关系，是一种经典的数据建模工具[1]。链接预测是复杂网络研究中的一个新兴的研究方向，是通过各种已知的网络信息，例如网络的节点信息，网络的拓扑结构信息等来预测复杂网络中节点之间存在链接的可能性，这种预测包含了两个方面：网络中未知/缺失链接(MissingLinks)的预测，即链接存在但无法直接观察到的情况;对网络中的未来链接(FutureLinks)的预测，即节点间未来可能产生的交互[2]。随着现代互联网技术的飞速发展，网络已经成为传播信息的主要载体，人们可以通过网络获取各种想要的信息和交流沟通分享各种信息[3]。近些年来互联网用户数量急剧增长，Internet为用户提供越来越多信息和服务的同时，其自身结构也变得更加复杂，在海量的信息中，对图中的两个节点进行链接预测变得越来越困难[4]。因此如何从一个具有大量节点和边的网络图中挖掘用户之间的链接关系已经成为一个重要问题。虽然现在已经有各种各样的链接预测的算法，但是其准确度和性能仍有待提高。通过对复杂网络图进行降维可以提高链接预测的性能和准确性。链接预测问题的应用领域十分广泛，不仅在社会网络分析中具有广泛的应用，在生物信息学、心理分析学等方面也可以广泛应用。

1.3 研究现状

近些年来链接预测问题因其具有重要的学术价值和潜在的应用价值而受到越来越多的科研工作者的关注，其算法由过去的基于马尔科夫链和机器学习的方法发展到现在的基于网络拓扑结构的预测算法[5]。最近几年随着科学技术的迅速发展，链接预测的研究取得了巨大的发展。目前已有的大量研究从不同角度切入链接预测这一课题，主要概括为以下几种：基于局部信息的链接预测算法主要包括共同邻居算法（Common Neighbor）、余弦相似度算法Salton算法、大度节点有利指标（Hub Promoted Index）、大度节点不利指标（Hub Depressed Index）、Jaccard算法、Adamic/Adar算法、优先增量法（PA）、Sorenson算法、LHN-I算法和资源分配算法（Resource Allocation）等，基于路径相似性的算法主要包括局部路径指标（LocalPath）和Katz算法指标，基于随机游走的相似性算法主要包括平均通勤时间指标（Average Commute Time）、基于随机游走的余弦相似性指标（Cos ）和重启的随机游走算法（RandomWalk with Restart）[6]。

2. 研究的基本内容与方案

2.1 研究目标

本文主要完成链接预测算法综合调研评测。设计并实现基于图数据降维的预处理技术，实现链接预测算法在时间上和准确性的提高。本文使用链接预测算法开始进行预测和预测结束两者之间的时间差T=t_end-t_start来评估链接预测算法在时间上的提高。本文通过对比data数组、indices数组和indptrs数组降维前后的长度来观察降维以后稀疏矩阵在存储性能上的提高。本文使用AUC（Area Under Curve）指标来评价链接预测算法的准确度。AUC是一种从整体上对链接预测算法的精确度来进行衡量的指标，它表示测试集中的边的相似性分数大于随机选择的不存在的边的概率。其计算公式如下：