网络结构数据的链路预测问题综述
宋熙卓然，中央财经财经大学统计学专业在读本科生。
今天我们分享一篇关于网络结构数据链路预测领域的综述文章，发表于2020年。Kumar A, Singh S S, Singh K, et al. Link prediction techniques, applications, and performance: A survey[J]. Physica A: Statistical Mechanics and its Applications, 2020, 553: 124289.
背景介绍
在社交网络中，节点代表个人或社会实体，而连边代表人或社会实体之间的关联或协作。由于个体之间的关系是不断变化的，因此网络会增加新的连边，同时原有的连边也可能消失。它导致社交网络高度动态和复杂。而寻找未来可能会出现的新的连边，就是链路预测的目的。
Liben-Nowell et al. 对链路预测问题进行了定义。假设图表示时间间隔内网络的快照；是这个网络快照的连边组成的集合。链路预测的任务在于寻找内的,并且。链路预测在很多领域都发挥了作用，例如Facebook上的好友推荐、电商中的推荐系统、生物信息学中蛋白质间相互作用的预测等。
现有的链路预测方法
作者在这一章节中介绍了常用的链路预测方法，并将其分成similarity-based, probabilistic and maximum likelihood-based, dimensionality reduction-based以及other approaches四类。具体可参考下图：
接下来我们依次介绍这几种方法。
similarity-based methods
基于相似度的度量是链路预测中最简单的方法，对于每一对节点对x和y，此方法计算相似度得分。得分较高的节点对会被预测为可能出现的新链接。相似性指标可以利用网络中的各种性质计算，如结构性质。基于结构性质的相似性指标可以分为几个类别，如局部和全局（local and global）、节点依赖和路径依赖（node-dependent and path-dependent）、参数依赖和无参数（parameter-dependent and parameter-free）等。
作者以局部、全局和准局部的分类为例，介绍了常用的相似性指标。其中局部相似性指标通常使用公共邻居和节点度的信息来计算。只考虑节点的局部信息。如共同邻居（CN）、PA、Adamic-Adar指数、资源分配等。
共同邻居（Common Neighbors, CN）在一个网络图中，共同邻居的数量可以代表两个节点领域重叠程度的大小。
其中，和分别是节点和的邻居的集合。和之间存在连边的可能性随着它们之间共同邻居的数量的增加而增加。
雅可比系数（Jaccard Coefficient, JC）这个指标与共同邻居类似，是共同邻居指标的标准化形式：
Adamic-Adar（AA）系数：Adamic和Adar提出了一个基于共享特征的指标来计算两个网页间的相似度得分，在Liben-Nowell等人进行了一些修改后，该指标进一步用于链接预测。
其中，是节点的度。从定义可看出，具有较低的度的共同邻居被赋予更大的权重。这一想法在现实场景中也较为直观，例如，与朋友数量较少的人相比，朋友数量较多的人花在单个朋友身上的时间/资源更少。
Preferential Attachment（PA）：这一指标的想法是，节点产生新链接的可能性与节点的度数成正比。两个节点和之间的PA指标定义为：
这个指标的效果通常较差，但优势在于简单和计算复杂度低。当拥有较高度的节点间连接密集，而低度节点间很少有连接时，PA能显示出更好的结果。
另外，作者还介绍了包括Resource Allocation(RA)、Salton Index (SI)、Sorensen Index、Hub Promoted Index (HPI)、 Leicht–Holme–Newman Local Index (LHNL)等一系列的相似性指标，具体定义和使用场景可参考综述原文。
全局相似性指标（global indices）是利用网络的整个拓扑信息来计算的。这种方法的计算复杂度较高，对于大规模网络来说可行性不高。接下来介绍一些常用的全局指标。
1、Katz指标：这个指标可以被认为是最短路径的一个变体。它聚合了节点和之间的所有路径，并以指数方式进行赋权。它可以表示为：
其中，表示节点和之间，所有长度为的路径的集合，用来控制路径权重。这一指标的计算复杂度较高。
2、Random Walk with Restart (RWR)：这一指标的构造运用了随机游走的想法。考虑为一个随机游走者，从节点出发，并在节点处于稳态的概率。为了使指标具有对称性，节点和的相似性指标RWR计算方法如下：
3、Average Commute Time (ACT)：该指标同样基于随机游走的概念。ACT由Gobel和Jagers首创，后来被应用于链路预测。它定义为一个随机游走者到达目标节点，然后返回起始节点所需的平均步数。令表示随机游走者从到达所需的步数，下面的定义即表达了这样的概念：
其余全局相似性指标还包括Shortest Path, Leicht–Holme–Newman Global Index (LHNG), Cosine based on , Normalized Average Commute Time (NACT), Matrix Forest Index (MF)，SimRank以及Rooted Pagerank (RPR)等，具体定义可参考综述原文。
准局部相似性指标在预测精度和复杂度之间进行权衡。其中一些指标提取了网络的整个拓扑信息，且这些时间复杂性仍低于基于全局的方法。例如本地路径索引、本地随机漫步索引、本地有向路径(LDP)等。
1、Local Path Index (LP)
其中，为参数。显然，当时，这一指标收敛于共同邻居。如果节点和之间没有连边，等于和之间长度为3的路径数量。该指标也可以扩展为广义形式：
其中，n是最大阶数。随着n增大，该指标的计算变得更加复杂。LP优于RA、AA和CN等指标。
其余准局部相似性指标还包括Path of Length 3 (L3)，Similarity based on Local Random Walk and Superposed Random Walk (LRW and SRW)等，具体定义可参考综述原文。
在这部分最后，作者在表1中对这三类方法进行了简单比较。
Probabilistic and maximum likelihood models
对于给定的网络，概率模型优化一个目标函数，以建立一个由多个参数组成的模型。该模型可以很好地估计给定网络的观测数据。在这种情况下，一条不存在的连边形成的可能性用条件概率表示。概率模型通常需要除了网络的结构信息以外更多的信息，如节点或连边的属性。得到关于属性的信息并不容易；此外，在这些模型中，参数调优也是一个大问题。极大似然方法复杂且耗时，因此这些模型不适用于实际的大型网络。一些开创性的概率和极大似然模型如表2所示。
Link prediction using dimensionality reduction
近年来，许多学者在研究网络嵌入（network embedding）和矩阵分解技术，这些技术也被认为成是降维的方法。
网络嵌入通过保留节点邻域结构，将图中较高的维节点映射到较低的维表示(嵌入)空间。换句话说，找到节点的较低d维的嵌入，使相似的节点(在原始网络中)具有相似的嵌入(在表示空间中)。最近，一些网络嵌入技术被提出并成功应用于链路预测问题，表3列出了网络嵌入方面的一些开创性工作。
从过去十年到现在，很多关于链路预测和推荐系统的论文都使用了矩阵分解。通常，潜在特征被提取并使用，每个节点都在潜在空间中被表示，这种表示在一个监督或非监督框架中用于链接预测。为了进一步改进预测结果，可以使用一些附加的节点/链接或其他属性信息。大多数工作都采用了非负矩阵分解，一些研究还应用了奇异值分解技术。
Other approaches
在这一部分中，作者介绍了基于学习的链路预测框架（Learning-based frameworks for link prediction）、基于信息论的链路预测（Information theory-based link prediction）、基于聚类的链路预测（Clustering-based link prediction）以及Structural perturbation method (SPM)。以第一种方法为例介绍其大致思路。
基于学习的链路预测框架
链接预测问题也可以建模为基于学习的模型，以利用图的拓扑特征和属性信息。从而可以将这个问题转换为一个监督分类模型，其中一个训练数据对应于网络中的一个节点对，节点对的标签表示它们之间是否存在链接。也就是说，考虑图中的顶点对，分类模型中对应数据点的标签为。那么：
这通常是一个二元分类任务，可以使用分类器(如决策树、朴素贝叶斯、支持向量机等)来预测可能产生的链接。该模型的主要挑战之一是选择适当的特征集。现有的大部分研究工作从网络的拓扑信息中提取特征集。其他一些工作集中于提取节点和连边的特征，它们对提高链接预测的性能起着至关重要的作用。
实验分析
在这一部分，作者使用多种方法在八个常见数据集上进行链路预测，并进行结果的评价。
评价指标
链路预测问题被视为一个二元分类任务，因此二元分类任务的大部分评价指标都可以用于链路预测评价。在本文中，作者基于混淆矩阵，使用了四个评价指标：Area under the ROC curve (AUROC) , Area under the precision–recall curve (AUPR) , Average precision 以及 Recall@k .
数据集
作者使用的数据集的信息如下表所示：
结果
对于每个数据集，作者使用相似性指标方法和其他方法进行链路预测，并使用四个指标进行评价。下面两张表分别展示了使用相似性指标和其他方法的进行链路预测的结果，使用AUROC来评价。
链路预测的拓展
前文所考虑的网络是无向且无权的。然而，若想在有向加权的网络上进行链路预测，还需要对方法进行修改。在有向加权网络中，连边被赋予一定的权重，代表了此条连边的强度；同时，连接一个节点的边存在两种类型，对于一个节点，就有两种类型的邻居，即in-neighbors 和out-neighbors 。那么相似性指标可以扩展到适用于有向加权网络的场景。
在有向网络中，共同邻居可表示为：
在有向加权网络中，
通过类似的方式，其他方法也可以修改并适用于有向和加权网络。这里需要注意的是，首先要在加权有向网络中定义几个拓扑特征(如度、路径、聚类系数等)，并应用这些特征实现几种链路预测算法。
此外，作者对于链路预测在时变网络（temporal networks）、双模网路（bipartite networks）和异构网络（heterogeneous networks）上的研究做了简要地回顾与讨论。
链路预测的应用
作者在这一节中介绍了链路预测的应用，分别是网络重构（network reconstruction），推荐系统，网络补全，垃圾邮件检测，社交网络中的隐私控制以及识别出版物的缺失引用等。例如，推荐系统已广泛应用于社交媒体(如Facebook, Twitter)和在线购物网站(如Flipkart, Amazon等)。这种系统根据用户以前的浏览历史(如兴趣、偏好、评分等)，在社交网络平台上推荐新朋友和关注者，以及在网上购物门户网站上推荐新产品。尽管协同过滤（CF）是一种成功的推荐范式，但受到数据稀疏性问题的极大限制。二部网络中的推荐系统可以映射到链接预测问题。Huang等和Li等提出了将推荐系统(用户-商品推荐)表示为双模网络的方法，并使用链接预测方法进行商品推荐。Sadilek等人提出了FLAP(友谊+位置分析与预测)系统，该系统实现了友谊和位置预测任务。
结论与未来方向
虽然本文中已经探索了几种链路预测方法，但它仍然是一个开放的研究问题。还有一些问题有待探索，例如，哪种网络的结构特性在每种方法上表现得更好，如何处理大规模网络数据，以及在预测新链接时，能否设计出一种方法来预测强度/权重随时间变化的链接。由于离群值的概念对检测垃圾邮件很有用，所以离群值检测可能是链接预测方法可以做出卓有成效的贡献的另一个框架。大多数现实世界的网络都是高度稀疏的，与负实例相比，正实例的数量非常少，因此在链接预测中处理不平衡的数据集也是一个待研究的问题。关于多层网络的研究还相对有限，可以在未来进行更多的探索。现代通信常常包含多于两个收件人，这将研究的重点从一对一的通信转移到一对多和多对多。在这种情况下，链路预测可能很有用。
参考文献
[1]Liben-Nowell D, Kleinberg J. The link prediction problem for social networks[C]//Proceedings of the twelfth international conference on Information and knowledge management. 2003: 556-559.
[2]Göbel F, Jagers A A. Random walks on graphs[J]. Stochastic processes and their applications, 1974, 2(4): 311-336.
[3]Huang Z, Li X, Chen H. Link prediction approach to collaborative filtering[C]//Proceedings of the 5th ACM/IEEE-CS joint conference on Digital libraries. 2005: 141-142.
[4]Li J, Zhang L, Meng F, et al. Recommendation algorithm based on link prediction and domain knowledge in retail transactions[J]. Procedia Computer Science, 2014, 31: 875-881.
[5]Sadilek A, Kautz H, Bigham J P. Finding your friends and following them to where you are[C]//Proceedings of the fifth ACM international conference on Web search and data mining. 2012: 723-732