链路预测是网络挖掘中的一个基本问题[1]。链路预测本质上是在动态、含有噪声的数据集上进行知识发现和拓扑重构[2]。 良好的链路预测模型还可以用来对复杂网络的演化模式进行刻画[3][4]。在已有的链路预测模型中，很多是基于局部信息的相似性算法[5][6]。虽然这些基于局部信息的模型简洁精炼且时间复杂度较低，但是准确性却往往受到限制。其原因是：网络中大量的全局拓扑信息被忽略了，而这些全局信息却影响甚至决定了网络的生长模式。网络的全局拓扑信息可以由邻接矩阵来表示——在邻接矩阵中，0值所出现的位置即可以表征不存在的连边，也可以表征那些由于干扰而缺失的或者在将来有可能出现的隐含连边。 所以在本质上，基于全局信息的链路预测可以被视为为矩阵中那些不为0的元素恢复它的原始值。

        我们尝试对复杂网络的链路预测问题建模，并将其一般化成为一个矩阵恢复问题。基于现实世界中常见的网络的邻接矩阵往往是低秩且稀疏的事实，我们利用Robust Principal Component Analysis这一数学工具[7]，在训练集网络数据的限定之上，通过求解满足最小化核范数的矩阵，来进行原始的网络临界矩阵的恢复。通过对网络的采样进行分析，在该样本下所恢复的矩阵实际上刻画了网络中连边增加和消失的机制。而我们主要对连边增加的部分进行分析，最终预测新链路的生成。由于该算法依赖于矩阵的低秩特性，我们将其称为LR(low rank)链路预测算法。我们发现LR算法的综合素质较为优秀且稳定，其预测准确率相较局部信息链路预测算法有良好的提升，且其计算复杂度显著低于其他高准确率的全局信息链路预测算法（用于比较的代表性算法除文献[6]外，还有[8-12]）。尤其在网络密度较大时，LR算法相较基于局部信息的预测算法有较为明显的优势。

[1]Lü, L., & Zhou, T. (2011). Link prediction in complex networks: Asurvey. Physica A: Statistical Mechanics and itsApplications, 390(6), 1150-1170.

[2]Getoor, L., & Diehl, C. P. (2005). Link mining: a survey. ACM SIGKDDExplorations Newsletter, 7(2), 3-12.

[3]Wang, W. Q., Zhang, Q. M., & Zhou, T. (2012). Evaluating network models: Alikelihood analysis. EPL (Europhysics Letters), 98(2), 28004.

[4]Zhang, Q. M., Xu, X. K., Zhu, Y. X., & Zhou, T. (2015). Measuring multipleevolution mechanisms of complex networks. Scientific Reports, 5,10350.

[5]Liben-Nowell, D., & Kleinberg, J. (2007). The link‐prediction problem for socialnetworks. journal of the Association for Information Science andTechnology, 58(7), 1019-1031.

[6]Zhou, T., Lü, L., & Zhang, Y. C. (2009). Predicting missing links via localinformation. The European Physical Journal B-Condensed Matter and ComplexSystems, 71(4), 623-630.

[7]Candès, E. J., Li, X., Ma, Y., & Wright, J. (2011). Robust principalcomponent analysis?. Journal of the ACM (JACM), 58(3), 11.

[8]Clauset, A., Moore, C., & Newman, M. E. (2008). Hierarchical structure andthe prediction of missing links in networks. Nature, 453(7191), 98-101.

[9]Guimerà, R., & Sales-Pardo, M. (2009). Missing and spurious interactionsand the reconstruction of complex networks. Proceedings of the NationalAcademy of Sciences, 106(52), 22073-22078.

[10]Lü, L., Pan, L., Zhou, T., Zhang, Y. C., & Stanley, H. E. (2015). Towardlink predictability of complex networks. Proceedings of the NationalAcademy of Sciences, 112(8), 2325-2330.

[11]Pan, L., Zhou, T., Lü, L., & Hu, C. K. (2016). Predicting missing links andidentifying spurious links via likelihood analysis. Scientific Reports, 6, 22955.

[12]Cannistraci, C. V., Alanis-Lobato, G., & Ravasi, T. (2013). Fromlink-prediction in brain connectomes and protein interactomes to thelocal-community-paradigm in complex networks. Scientific reports, 3, 1613.

论文信息：RathaPech, Dong Hao, Liming Pan, Hong Cheng and Tao Zhou, Link prediction via matrixcompletion.  EPL, 117 (2017)38002.

论文链接: http://iopscience.iop.org/article/10.1209/0295-5075/117/38002

全文免费下载：

epl18385-offprints.pdf