- 文献综述（或调研报告）：
随着信息革命的推进，各种形态的网络，特别是社交网络，在我们的生活中正占据越来越重要的地位。特别是互联网的诞生，使得社交网络已经成为人们生活不可或缺的一部分。因此，对社交网络的分析也越来越受研究者的关注。该领域一个有意思的问题是，如何基于网络中各节点的属性和已被探知的网络中的链接来预测网络中各节点间新的链接、或者各节点间尚未探明的链接。这个问题被定义为链接预测[1]。对该问题的研究有利于抽取网络中的隐性信息和对网络的演进进行建模。
现有的链接预测方法可分为四类，分别为基于节点的链接预测、基于网络拓扑的链接预测、基于机器学习的链接预测和基于社交理论的链接预测方法。
基于节点的链接预测方法认为如果两个节点的特征越相似，则这两个节点越有可能形成链接。这一类方法的代表工作有：Anderson等人通过计算用户兴趣的重合度来衡量相似度[2]；Bhattacharyya等人通过用户简历中关键字的距离来衡量相似度[3]。这一类方法由于需要有节点的元信息，而大部分网络数据集并不含有各节点的元信息或元信息不全，因此应用场景比较有限。
基于网络拓扑的链接预测方法又可以分为三种，分别是基于局部信息的链接预测方法、基于全局信息的链接预测方法和基于半局部信息的链接预测方法[4]。
基于局部信息的链接预测方法使用网络节点邻居相关的结构信息来计算网络中各节点之间的相似度。这一类方法的代表工作有：共同邻居法（Common Neighbors），两个节点的相似度以其拥有的共同邻居数衡量[1]；Adamic-Adar指标法（Adamic-Adar Index），两个节点的相似度以其各共同邻居所拥有的邻居数的倒指数之和来衡量[5]；资源分配指标法（Resource Allocation Index），两个节点的相似度以其各共同邻居所拥有的邻居数的倒数之和来衡量[6]；Jaccard指标（Jaccard Index），两个节点的相似度以其共同邻居数和两节点各自拥有的不重复邻居节点总数之比来衡量等[7]。基于局部信息的链接预测方法优点在于效率较高，并且可以适应高度动态的网络。这类方法的缺点在于对节点与邻居的邻居之间的是否会生成新链接预测效果较差。
基于全局信息的链接预测方法使用全局网络拓扑信息来计算网络中各节点之间的相似度。这一类方法的代表工作有：Katz指标（Katz Index），两个节点的相似度以其之间所有可能的路径的影响力之和来衡量[8]；随机游走（Random Walk），将Pearson于1905年提出的[9]随机游走应用于链接预测领域的方法[10]。这类方法克服了基于局部信息的链接预测方法的缺点，但是这些方法的时间复杂度普遍较高，使得它们的实用范围受限。
基于半局部信息的链接预测方法综合了基于局部信息的链接预测方法和基于全局信息的链接预测方法，它的性能和基于局部信息的链接预测方法相近，而又考虑了全局的信息。这一类方法的代表工作有：局部路径指标（Local Path Index），这个指标和Katz指标相近，但是只考虑有限长度的路径，因此降低了时间复杂度[11]；局部随机游走（Local Random Walks），比起基于全局信息的随机游走，这个方法只考虑有限次随机游走，因此也降低了时间复杂度[12]。
基于机器学习的链接预测方法的要点在于先获得各节点的特征向量，然后使用机器学习的算法对特征向量进行学习，从而进行链接预测。基于机器学习的链接预测方法也可分为三类，分别为基于特征的方法、概率图模型和矩阵分解。基于特征的方法一般是根据利用相似度方法计算出的节点对相似度值或者从社交网络中提取的拓扑特征来进行链接预测；概率图模型认为两个节点之间产生链接的可能性可以以概率值来表示，进而可以利用概率理论对链接预测进行研究；矩阵分解是将网络使用邻接矩阵进行表示，然后对邻接矩阵进行矩阵分解，利用分解后的矩阵进行链接预测。
