链接预测是分析社交网络的一项重要任务，社交网络在信息检索、生物信息学和电子商务等其他领域也有应用。链接预测技术多种多样，从基于功能的分类和基于内核的方法到矩阵因子化和概率图形模型。这些方法在模型复杂性、预测性能、可扩展性和通用性方面各有不同。通过按模型类型对一些具有代表性的链接预测方法进行分类，从而对它们进行调查。我们主要考虑三种类型的模型：第一，传统的（非贝叶斯）模型，它提取了一组功能来训练二元分类模型。其次，通过贝叶斯图形模型对网络中实体之间的联合概率进行建模的概率方法。最后，线性代数方法通过排名减少的相似性矩阵计算网络中节点之间的相似性。我们讨论属于这些广泛类别的各种现有链路预测模型，并分析其强弱。在调查结束时，我们讨论了最近的事态发展和未来的研究方向。
社交网络是模拟群体或社区中人们之间互动的流行方式。它们可以可视化为图形，其中顶点对应于某个组中的人员，边缘表示相应人员之间的某种形式的关联。这些关联通常由群体固有的共同利益驱动。但是，社交网络非常动态，因为随着时间的推移，新的边缘和顶点被添加到图表中。由于大量的可变参数，了解推动社交网络演变的动态是一个复杂的问题。但是，一个相对容易的问题是理解两个特定节点之间的关联。例如，可以提出的一些有趣的问题是：关联模式如何随着时间而改变？驱动这些协会的因素是什么？两个节点之间的关联如何受其他节点的影响？我们在本文中讨论的规格问题实例是预测两个节点之间未来关联的可能性，因为我们知道该节点在图形当前状态下没有关联。此问题通常称为链接预测问题。更正式的是，链接预测任务可以按照如下（基于利本-诺威尔和克莱因伯格中的去鳍）：给定社交网络
在本文中，我们介绍了一项有关现有方法的链接预测调查，主要侧重于社交网络图形。我们将目前的方法分为几个组。一组算法计算一对节点之间的相似性分数，以便采用受监督的学习方法。在此类中，我们还包括使用内核基质，然后使用最大边际分类器的方法。另一类算法包括基于贝叶斯概率模型和概率关系模型的算法。除此之外，还有基于图形演化模型或线性代数公式的算法。几种方法跨越上述类的多个类的寓言方案。在简要概述后，我们将在下面详细讨论每组方法。
利本-诺威尔和克莱因伯格提出了最早的链接预测模型之一，明确在社交网络上工作。图表中的每个顶点都代表一个人，两个顶点之间的边缘代表人之间的相互作用。可以通过允许平行边缘或采用适合边缘的加权方案来明确模拟交互的多重性。此设置中的学习范式通常通过基于图形的相似度指标提取一对顶点之间的相似性，并使用相似性分数的排名来预测两个顶点之间的联系。它们主要侧重于链接预测任务中基于图形的各种相似度指标的性能。后来，哈桑等人al.以两种方式扩展了这项工作。首先，他们表明，在图形拓扑范围之外使用外部数据可以显著改善预测结果。其次，他们使用各种相似度指标作为受监督学习设置中的特征，其中链接预测问题被假定为二进制类假说任务。从那时起，受监督的分类方法在链接预测的其他作品中很流行。链接预测问题以前也曾在关系数据和互联网域中研究过，其中未使用明确的图形表示。在这些作品中提出的预测系统可以接受任何关系数据集，其中数据集中的对象以任何复杂的方式相互关联，系统的任务是预测数据集中一对对象之间的存在和链接类型。概率关系模型，图形模型，随机关系模型，这些不同的变体是这些作品中使用的主要建模范式。这些方法的优势包括通用性和易用性，它们可以将实体的属性纳入模型。在下侧，它们通常很复杂，并且有太多的参数，其中许多参数对用户可能不太直观
关于社交网络演化的研究与链接预测问题非常相似。一个进化模型预测了网络的未来边缘，考虑到社交网络的一些 众所周知的属性，如权力法度分布和小世界现象。这仍然是进化模型和链接预测模型之间的主要区别。前者侧重于网络的全球属性 ，后者对网络的局部状态进行建模，以预测网络中特定结节之间存在链接的概率。然而，这些模型的想法有助于一些直接解决链接预测任务的研究工作。链接预测的主要挑战之一是互联网规模社交网络的演变，如脸谱、mySpace、ickr等。这些网络规模庞大，具有高度动态性，早期算法可能无法扩展和适应更直接的方法来解决这些限制。例如，泰伦达等人。al.表明，利用过去交互的时间戳（明确使用交互的血统）可以明显提高链接预测性能。最近，宋等人al.使用矩阵因子化来估计现实生活中具有大约 200 万节点和 9000 万边的现实生活中的节点之间的相似性。任何旨在计算如此大图形的顶点之间对的相似性的传统算法都注定要失败。最近，基于矩阵的因子化工作已扩展到更丰富的高阶模型，如张力。在概述了背景方法之后，我们现在回顾了现有的将预测联系起来的方法。我们从基于功能的方法开始，这些方法构建了对对功能，以便用于类的浮证任务。接下来，我们考虑贝叶斯的方法，其次是概率关系模型。在回顾了基于线性代数的方法之后，我们提出了一些近期趋势和未来工作的方向。表示法。通常，我们将使用小字母（如 x、y、z）表示社交网络中的节点，边缘由字母 e 表示。对于节点 x，Γ （x） 表示 x. 度 （x） 的邻家集是Γ （x） 的大小。我们使用字母 A 表示图形的邻存矩阵。
我们可以将链接预测问题建模为受监督的分类任务，其中每个数据点对应于社交网络图中的一对顶点。为了训练学习模式，我们可以使用培训间隔（[$t0，t0'$]）中的链接信息。根据此模型，可以预测测试间隔中的未来链接（[$t1，t1’$]）。更正式的是，假设$ u、v ∈ V$ 是图
$$ y=\begin{cases} +1 &if� u, v ∈ E \ -1 & if �u, v\notin E \
\end{cases} $$ 使用上述标签进行一组培训数据点，我们构建了一个分类模型，可以预测一对顶点的未知标签<$u，v$ >并且<$u, v\notin E$>在图表 G[$t1，t1'$] 。这是一个典型的二元分类任务，任何流行的监督分类工具，贝叶斯，神经网络，支持矢量机（SVM）和k最近的邻居，都可以使用。
链接预测假定图形$G（V,E）$。 让$e（u,v）∈E $表示节点 u 和 v 之间的相互作用 （边缘）， 让t （e） 表示交互的时间。让$G[t1，t2] $表示 G 的子图，这样所有边缘都在t1和 t2 之间创建（即，对于此中的所有边缘 e） 子图，$t1 < t（e）<t2）$。 现在给四个时间戳t1 < t1^'^' < t2 <t2^'^'， 链接预测算法被赋予子图 G [t1， t1^'^]train） 间隔），并预计预测边缘在G[t2，t2^'^]测试间隔）。 请注意，就像新边缘一样，社交网络中可以引入新的节点：因此，G [t2 ， t2^'^]'可能包含 G [t1， t1‘]中不存在的节点。因此，链接预测算法通常只能针对培训期间存在的对节点进行预测边缘。人们可以添加额外的限制，例如仅预测事件节点到至少 k 边缘的链接（即具有更大或相等的程度）在测试和培训间隔期间为 k)。
让$G（ Vtrain, Etrain ）$成为我们的例图。然后，一个链接预测算法生成各种列表最可能的吉辛 $Vtrain× Vtrain + Etraintrain× Vtrain Etrain
节点基于邻里的方法 以下方法利用邻里信息计算两个节点之间的相似性。
在此方法中，人们假设两个节点共享的常见邻居越多，它们就越相似。让
这种共同使用的测量计算了一个节点的相似性， 该节点是 x 或 y 的邻居， 是一个共同的邻居。它可以按共同邻居的数量除以 x 或 y 的邻居总数：
与杰卡德类似的措施，这项措施是由拉达·阿达米奇和艾坦·阿达尔[AA]提出的。它背后的直觉衡量的是，如果两个人共享一个邻居，而邻居是一个罕见的邻居，它应该对他们的相似性产生更高的影响。例如，我们可以根据节点的稀有性（即节点的程度越小，其稀有性越高）来定义节点的稀有性。该措施的原始版本是根据网页功能定义的。基于邻里的修改版本
在取消的优惠附件模型中，人们假设更高程度的节点与传入节点连接的可能性更高。因此，就连接概率而言，较高的度节点是同位素。优先附件措施的定义是捕捉这种相似性：
个人在社交媒体上表现出不同的行为，可以分为个人行为和集体行为。个人行为是单个个体行为，即（1）另一个个体行为（个人-个人行为）、（2）实体（个体实体行为）或（3）社区（个人-社区行为）。我们讨论了如何分析和预测个人行为。要分析个体行为，有步骤程序，有大纲指导。首先，在社交媒体上应该清楚地观察到这种行为。其次，人们需要设计与社交媒体中的行为相关有意义的特征。第三步旨在查找特征与行为之间的相关性和关系。最后一步是验证找到的这些重新确定的转运。我们讨论了社区加入作为个人行为的一个例子。通过级联或阈值模型可以对单个行为进行建模。行为通常以链接的形式导致相互作用;因此，链接预测技术在预测行为方面非常有效。我们讨论了基于邻里和基于路径的链接预测技术。
集体行为是当一组有或没有协调的个人以一致的方式行事时。 集体行为分析要么通过个人行为分析完成，然后进行平均分析，要么进行集体分析。当分析集体，人们普遍看人口一般模式。我们在社交媒体上讨论了用户迁移问题 集体行为分析的示例。建模集体行为可以通过网络模型进行，并且可以通过使用人口属性来预测结果进行预测。以预测电影票房收入为例，它利用人口属性，如个人发微博的速度来证明这种方法的有效性。 评估行为分析结果以确保这些发现不是由于外部因素而发现的，这一点非常重要。我们讨论了因果关系测试、随机化测试以及用于评估行为分析结果的监督学习评估技术。然而，根据背景，研究人员可能需要设计其他信息丰富的技术，以确保结果的有效性。