文献综述（或调研报告）：
随着互联网行业的高速发展，近些年来，越来愈多的社交网络出现，例如Facebook和Wechat等等，它们使人们之间的联系变得越来越紧密。在形形色色的网络中，链接预测一直是一个非常普遍的问题，在各种领域中都有重要的应用意义。链接预测主要指的是对网络中节点对之间是否产生链接进行预测。2007年，KelienBerg等人提出了社交网络中的链接预测问题[1]，在这之后，越来越多的研究者参与到这个问题中。然而，社交网络具有高度的动态性，因此，预测当前社交网络没有观测到的链接和未来新生成的链接是一个具有挑战性的任务[2]。
十几年来，研究者们提出了许多链接预测的方法，包括利用节点信息、网络拓扑结构、社会学理论和机器学习的方法。其中最为主流的，就是基于网络拓扑结构中的邻居结构的链接预测指标。
在一个社交网络中，每个节点都倾向于与在结构上最邻近的节点建立链接，而邻居节点便能很好地表示这一信息，因此，研究者们定义了很多指标通过节点的邻居结构进行链接预测。Common Neighbors指标定义为节点对之间的共同邻居数，其大小衡量了节点对之间建立链接的可能性[3]；Jaccard Coefficient指标定义为节点对之间共同邻居数和各自拥有的邻居数之和的比值，比值越大，则代表节点对之间建立链接的可能性越大；Leicht-Holme-Nerman指标定义为节点对之间共同邻居数和各自拥有的邻居数的乘积的比值，类似的，通过其值的大小衡量节点之间的相似度[4]；Adamic-Adar Coefficient定义为节点对共同邻居的倒对数之和[5]；Resource Allocation定义为节点对共同邻居的倒数之和[6]；Preferential Attatchment定义为节点对各个节点的邻居树的乘积[7]。这些指标都思路都比较简单，在静态网络中能达到不错的预测效果，时间复杂度大约为O(n2)。
除了通过邻居节点表征拓扑结构以外，有一类通过节点对之间的路径计算得到节点相似度的方法。Kats指标基于节点对之间所有路径的叠加，给不同路径赋予了不同的权重，表现不同路径对节点相似度的影响，一般来说，越短的路径会有更大的权重[8]；Local Path指标利用了长度为2和3的附近路径的信息描述节点对的相似性[9]。另外，节点间的关系也可以通过随机游走来表示，通过赋予节点到邻居节点的转移概率，设置一次随机游走可以表示节点间发生联系的概率。Hitting Time记录了在一次随机游走中从节点对的一个节点出发到达另一个节点的预期步数[10]。
近年来，机器学习学科迅速发展，在各个领域都有良好的表现，社交网络本身的海量数据也正好与机器学习的应用场景相适应。因此，越来越多基于机器学习的方法相继提出。链接预测的本质是对节点对之间是否产生链接进行预测，是一个典型的二分类问题，因此，大量的机器学习方法如支持向量机、决策树、贝叶斯、神经网络等都可以应用在链接预测问题中。
为了构建一个合适的分类器，我们可以基于之前所得到的各种基于邻居结构、路径、随机游走等方法获得的指标作为特征，也可以基于不同类型网络的具体结构的某些性质构造指标特征。Generic kernel-based machine learning方法将随机游走路径作为拓扑结构特征，用户选择作为节点特征，利用一类基于核函数的支持向量机学习用户项的二部图[11]；Chiang等人输入长循环得到的特征，利用逻辑回归训练符号网络[12]；Lu等人同样使用逻辑回归，将带有多个辅助网络的社交网络中的基于路径的指标作为特征[13]。除了直接应用传统的机器学习方法，还有通过概率图模型和矩阵分解的思路。在社交网络中，可以给节点对之间生成链接赋予一个概率，类似于随机游走中的转移概率，这就是概率图模型。通过研究这样一个概率图模型，应用概率论和机器学习的方法，帮助我们进行链接预测。矩阵分解的思路主要是把网络表示为邻接矩阵的形式，再应用矩阵分解的方法帮助我们进行链接预测。最早由Menon等人提出其在链接预测领域的应用，他们通过这样一种思路将链接预测转化为了矩阵问题[14]。在这之后，也有不少研究者延续这个思路提出了很多新的方法。
然而，显然，上述方法主要集中于静态网络的链接预测，而忽略了社交网络固有的时序性。在各个领域，时序数据的处理一直是一个具有挑战性的任务。相对于静态网络，时序社交网络增加了一个时间的维度，构成了一个更复杂的数据结构。这里我们给时序社交网络的链接预测问题一个简单的定义：已知1到T时刻的某社交网络，预测T 1时刻网络的链接。Dunlavy等人引入了Collapsed tensor的概念，将复杂网络降维转化为单一的矩阵，通过基于矩阵和基于张量方法的结合进行时序的链接预测[15]；Gao等人构造了一个统一了潜在矩阵分解方法和图的正则化技术的模型，这能将网络的内容和结构信息相融合并捕获网络的演化模式[16]；Tylenda等人将时序信息引入了基于图的链接预测技术，他们将时序特征融入了图中边的权重，代入前沿的链接预测方法[17]；Munasinghe and Ichise定义了一个新的特征Time score，它利用链接发生的时间戳和当前时间，表示链接的强度是随着时间不断变化的，这个特征可以用于有监督的机器学习方法中以提高预测的效果[18]；Triad Transition Matrix预测方法利用了一个网络中三个节点组成的三元节点组之间的转移概率，在短时间段的稀疏网络中有良好的表现[19]。对于时序网络，大多数方法使用了一些小技巧，从而帮助我们能合理地捕获到网络的时序信息。可见，我们也需要采取合理的办法获取到时序信息，时序信息对我们的预测效果至关重要。
2017年，Yu等人提出了一种基于时间和空间一致性的时序链接预测方法——LIST模型[20]。这个模型同时考虑了网络传播和时序矩阵分解技术，通过精心构造的目标函数，最小化网络传播损失和时序网络重构损失。因此，一方面从网络传播中合理考虑网络结构信息，一方面获取时序网络的演化模式，同时融入时空信息从而进行链接预测。
