链路预测（Link Prediction）问题是指通过对已知网络结构的分析，包括一些可能的节点的其他信息，来评估尚不相连的两个点之间产生链接的可能性，进而实现预测[1][2]。链路预测的目标大体上可以分为两类：一类是预测真实存在但我们还不知道的边（missing links），多与生物网络相关；另一类是预测现在尚未存在但未来很可能出现的边（future links），多与社交网络和技术网络相关。

最近十余年的研究，已经让“链路预测”从网络科学中一个“有趣的问题”，逐渐变成了中心性、基础性的问题。原则上讲，如果我们真正了解网络组织和生长的机制（规律），我们就应该能够设计更精确的链路预测算法，而一个精确简洁的链路预测算法背后，往往代表了对于网络组织和生长的机制的重要洞见！

文献[1]正式出版到现在，已经整整十年了，这个领域发展也非常快。我最近专门写了一篇短综述（只有17页），特别介绍了最近十年链路预测方面特别需要关注的进展和挑战[3]。这篇短综述主要讨论了六个专题：如何评价一个算法；局部相似性指标；链路可预测性；网络嵌入；矩阵填充；集成学习。这篇短综述虽然不长，但是写得很紧凑，内容非常丰富（某种意义上讲，可以算稠密），所以我建议各位感兴趣的读者下载打印后细读，我也无法用一篇博文做完整的介绍。下面我摘录一些该综述讨论到的可能大家感兴趣的问题，希望这些问题能够帮助大家快速直观地感受这篇短文的关注点。这些问题中的一部分，文献[3]给出了答案；同时还有很多重要的问题，目前还没有形成共识的答案。更有趣的是，这些看起来似乎风马牛不相及的问题，竟然有着千丝万缕而又神秘的联系。

示例问题1[4][5]：AUC是否足够评价链路预测算法的好坏？它有没有什么缺陷，如果有，怎么克服？AUC、AUPR、Precision等指标评价的结果一致吗？怎么判断哪个指标更合适？

示例问题2[6][7][8]：基于二阶路径的相似性指标（基于共同邻居的相似性指标）和基于三阶路径的相似性指标哪个更精确？是否在很多网络中直接用高阶路径指标反而效果更好？这里面根本的原因是什么？

示例问题3[6][9]：节点相似性的线性展开[6]和网络的自表示[9]，是同一个公式。前者的优化结果如果做一个截断，可以得到直接用三阶路径数作为相似性的理论依据；后者的优化结果可以用来评价网络的链路可预测性。其间有什么潜在而深刻的联系吗？

示例问题4[9][10]：一个网络的结构如果很有规律，那么对应的邻接矩阵应该是低秩的[9]。一个真实网络的结构如果包含噪音（缺失边和虚假边），那么噪音对应的邻接矩阵应该是非常稀疏的。这两个说法都是非常直观的，但是如果我们反过来，毫无根据地（通过优化算法）把一个邻接矩阵拆成一个低秩矩阵和一个稀疏矩阵（范数小），会发生什么？为什么通过这种毫无道理可言的方式得到的低秩矩阵竟然可以用来很好地预测缺失链路[10]？这里面有没有什么深刻的数学？

示例问题5[11][12][13][14]：网络嵌入[11]、集成学习[12][13]和深度神经网络[14]用于链路预测，到底能不能显著提高预测的精度？支持[12][14]和反对[11][13]的结果都很多，是否有必要开展更大规模的实验研究？

链路预测中有意思的问题当然远不只是上面那几个。我有一个很强烈的感觉，就是链路预测的研究正在引导我们接近一些非常本质和非常重要的数学问题，特别是如何分离一个结构中有规律和无规律的部分。相信十年以后再看这个领域，一定会有更多精彩的篇章。

参考文献：

[1] L. Lü, T. Zhou, Link prediction in complex networks: A survey, Physica A 390 (2011) 1150-1170.

[2] 吕琳媛，周涛，《链路预测》，高等教育出版社，2013。

[3] T. Zhou, Progresses and challenges in link prediction, iScience 24 (2021) 103217.

[4] T. Saito, M. Rehmsmeier, The precision-recall plot is more informative than the ROC plot when evaluating binary classifiers on imbalanced datasets, PLoS ONE 10 (2015) e0118432.

[5] Y. Yang, R. N. Lichtenwalter, N. V. Chawla, Evaluating link prediction methods, Knowl. Inf. Syst. 45 (2015) 751-782.

[6] R. Pech, et al., Link prediction via linear optimization, Physica A 528 (2019) 121319.

[7] I. A. Kovács, et al., Network-based prediction of protein interactions, Nat. Commun. 10 (2019) 1240.

[8] T. Zhou, Y.-L. Lee, G. Wang, Experimental analyses on 2-hop-based and 3-hop-based link prediction algorithms, Physica A 564 (2021) 125532.

[9] X. Xian, et al., NetSRE: link predictability measuring and regulating, Knowl.-Based Syst. 196 (2020) 105800.

[10] R. Pech, et al., Link prediction via matrix completion, EPL 117 (2017) 38002.  

[11] A. C. Mara, J. Lijffijt, T. De Bie, Benchmarking network embedding models for link prediction: are we making progress? The 7th International Conference on Data Science and Advanced Analytics (IEEE Press, pp. 138-147).

[12] A. Ghasemian, A. Galstyan, E. M. Airoldi, A. Clauset, Stacking models for nearly optimal link prediction in complex networks, PNAS 117 (2020) 23393-23400.

[13] A. Muscoloni, C. V. Cannistraci, Short note on comparing stacking modelling versus Cannistraci-Hebb adaptive network automata for link prediction in complex networks, Preprints: 202105.0689.

[14] X.-W. Wang, Y. Chen, Y.-Y. Liu, link prediction through deep generative model, iScience 23 (2020) 101626.

论文信息：

T. Zhou, Progresses and challenges in link prediction, iScience 24 (2021) 103217.

论文免费下载链接：

https://www.cell.com/iscience/fulltext/S2589-0042(21)01185-8?_returnURL=https%3A%2F%2Flinkinghub.elsevier.com%2Fretrieve%2Fpii%2FS2589004221011858%3Fshowall%3Dtrue#secsectitle0010