文献综述（或调研报告）：
近几年，随着计算机科学技术的发展，数据挖掘技术、图论、概率论、以及各种统计学的发展和完善，社会网络分析中的链接预测方法的应用越来越广泛，这个方向的研究也得到了越来越多的关注。
- 国外发展现状
在计算机领域内，早期的链接预测研究主要是基于马尔科夫链和机器学习进行分析。利用马尔科夫链及马尔科夫模型进行链接预测和访问路径分析，在这类模型中，状态集是用户访问的网页集合，预测的依据是由访问记录计算出的网页转移概率[1]。后来，基于马尔科夫链的方法得到了进一步的扩展，用其来进行预测自适应性网站（Adaptive Websites）中的内容[2,3]。还有利用关系特征（Relational Features）的结构逻辑回归模型（Logistic Regression Model）可以预测链接的存在[4]。基于节点属性的预测方法有很多，其中最简单的算法就是定义节点间的相似性，然后直接利用节点相似性（Similarity-based Algorithms）进行链接预测[5]；另外，利用构造基于节点属性和网络拓扑结构特征的模型来进行链接预测，例如局部条件概率模型[6]。从某种意义上来说，现实网络中的链接关系可以理解为网络的深层层次结构反映，基于最大似然估计的链接预测正是基于这种思想设计的方法。该方法是基于网络结构而提出，适合处理层次结构明显的网络，而且在预测错误链接（Spurious Link）和未知链接时都有较高的准确率。但是预测过程中需要生成多个网络样本，导致该方法的计算复杂度比较高，不适合处理规模大的网络[7]。
以上的研究方法中，基于相似性的链接预测方法是现在研究的一个热点。该方法的重点是相似性的定义，定义方法可以是基于网络拓扑结构或基于节点属性。前者可分为基于节点和基于路径两类，不同相似性定义算法在不同社会网络中的预测结果不同[8]。经典的基于局部信息的算法共同邻居（Common Neighbors）最具代表性，其具有计算简单、可扩展性良好等优点，如在合著网络中，节点之间链接的存在与否与共同邻居节点数量相关，简单的共同邻居算法对社会网络的链接预测有很好的效果。基于共同邻居的算法 Adamic-Adar、Jaccard 算法用于信息检索和网页分析，具有良好的预测效果[9]；FOAF更适合预测在线社交网络中的链接[10]；Preferential Attachment 适用预测潜在的链接，只需要计算两个节点的度数乘积，是需要信息量最小的算法[11]。Random Walk with Restart（RWR），最短路径算法，SimRank，Katz几种算法基于全局信息进行链接预测，其中RWR是基于马尔科夫链模型的一种方法；Shortest Path适合用来进行朋友推荐；SimRank是根据网络结构环境计算全局相似性的方法，Katz[12]涉及到节点间所有的路径情况，为了调节不同距离的路径对节点间相似度的影响，在计算时对不同阶段的路径加上不同的分数值，该算法具有很好的预测准确率，但计算复杂度比较高。
目前在线社交网络的研究受到广泛关注，也是一个具有挑战性的问题，在线网络中的数据量（节点数）庞大，另外一点就是网络中实时性强，可以利用基于节点相似性方法进行链接预测。根据已知信息采用信息扩散（增殖）方法，改进随机游走算法进行预测[13]；利用经验数据，构造相似矩阵，采用proximity sketch、proximity embedding对稀疏矩阵进行降维。在线社交网络中，不同相似性方法的效率依赖于网络中部分相关边节点的度数的最大值，使用机器学习软件包的多重相似性预测有很高的准确度[14]。
“社交平衡理论”可以用来预测网络中的正负（敌友）链接。在线网络中链接预测的大多数利用正关系，但是负的关系对预测也有帮助。根据该理论，利用全局状态相似性，进行在线网络中的标记预测（Sign Prediction）。把节点之间的关系标记为 Positive 或 Negative，即把社会网络中个体之间的情感因素考虑进来。例如，一个人朋友的敌人是这个人的敌人，一个人的敌人的朋友是这个人的敌人，根据这种正负关系把节点排序。这是最近比较新的研究方向，对链接类型进行预测[15,16]。将相似性和社交平衡理论结合进行链接预测也是一种思路，结合局部信息和全部信息预测在线社交网络[17]。另外一种新方法冷启动链接预测（Cold Start Link Prediction），该方法的研究工作有待进一步研究[18]。
随着研究的深入，链接预测问题由最简单的无权无向网络逐渐向加权和有向的方向发展。无权无向网络的研究只是关注节点对之间是否存在相互作用关系，并没有考虑送种相互作用的强度和类型，也没有考虑到相互作用的方向性。相对于无权无向网络，拥有更多信息的加权网络或者有向网络为真实网络提供了一种更为细致､准确的描述，也为构建加权和有向网络模型提供了可靠的依据[19]。例如，吕琳媛和周涛[20]发现了权重小的链接有时候反而比权重大的节点能起到更大的作用，这与社会网络理论中的弱连接理论[21]有十分紧密的联系。另外，通过分析有向网络模体的统计性质，Milo等人[22]揭示了复杂网络的组织原理，我们可以借此进一步研究有向网络的链接预测。许多实证研究结果已经充分证实了加权和有向网络描述真实体系的合理性，现实中很多网络的链接都是有方向和权重的，而不仅仅是简单的无向无权网络。所以对复杂网络链接预测的研究不仅仅是预测链接的存在性，还应当考虑链接的方向与强弱，这对实现复杂网络的全面预测有十分重要的意义。
- 国内发展现状
国内的研究相对落后，一般都是对一些技术方法改进更新。
例如，仅考虑网络的局部信息，其计算量远远小于基于全局信息的算法，特别是在网络规模较大且稀疏的情况下，局部路径算法在计算复杂度上的优势更加明显，因此其应用前景相当可观。周涛等人系统地比较了9种已有的基于局域信息的相似度指标，并进一步提出了两种准确率更高的相似度指标局域路径指标(Local path Index)和资源配置指标(Resource Allocation Index) [23]。资源分配算法，一种新的基于节点相似性方法，从资源分配的角度考虑，利用了最近邻居的下一个节点信息。LP算法是对基于全局信息 Katz 的一种改进，综合局部信息和全局信息的优点，这种考虑计算复杂度和预测准确率。
还有在网络链接预测中考虑时间因素，将链接预测的方法应用到链接稳定性的预测。t时刻网络存在的链接在t 1时刻中可能消失，也有可能 t时刻不存在链接的两个节点间t 1时刻有新的链接产生，即链接稳定性预测研究[24]。稳定性预测的前提是已知两个节点之间是否存在链接，关心下一时刻两者之间链接的变化情况；链接预测只是判断两个节点之间在将来是否会有新的链接产生，没有已知链接的前提。但是链接预测的各种方法可以用来预测网络链接的稳定性，是链接预测方法应用的一种扩展[25]。
以上是毕业论文文献综述，课题毕业论文、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。
