点击“DataCastle数据城堡”即可轻松关注~

第一部分链接：http://blog.sciencenet.cn/home.php?mod=space&uid=3075&do=blog&id=1102268

网络中的链路预测是指如何通过已知的网络节点以及网络结构等信息预测网络中尚未产生连边的两个节点之间产生链接的可能性[14,15]。

这种预测既包含了对未知链接的预测也包含了对未来链接的预测。链路预测算法可以用以发现生物网络中可能未知的关系，从而指导我们进行更准确的生物实验；可以用来提高社交网络中朋友推荐精确度，从而提升用户体验；可以看作检测网络演化模型是否抓住网络生长机制的工具；可以用于发现已知药物原来尚未知道的治疗作用等等。

该问题的研究在理论和应用两个方面都具有重要的意义和价值，因此最近受到了广泛的关注。

我们在这方面的工作可以粗糙地分成以下五个方面。

提出了一系列算法复杂性低但预测精度不错的局部相似性指标，大幅度增加了链路预测在超大规模网络中的可应用性。

基于节点相似性的链路预测方法是目前最主流的方法，此方法的一个重要前提假设就是两个节点之间相似性(或者相近性)越大，它们之间存在链接的可能性就越大。

2009年，我们提出了两个现在广为应用的局部相似性指标：资源分配指数（Resource Allocation Index）[16]和局部路径指数（Local Path Index）[17]。前者模拟资源分配的过程，认为如果两个节点有一些度很小的共同邻居，其相似度应该显著大于两者具有一些度很大的共同邻居；后者认为共同邻居数（二阶路经数）尚不足以刻画两个节点的紧密程度，还需要考虑三阶路径数目。

进一步发展资源分配指数的思想，我们认为不同的共同邻居对于节点对产生链接的贡献应该是不同的。基于此，我们提出了一种局部朴素贝叶斯模型[18]，这个模型定义了一个角色函数可以较准确地揭示不同共同邻居的作用（通过分析以该节点为共同邻居的所有节点对是否连边的情况）。

在对美国航空网络的实证分析中发现，有些机场之间虽然共同邻居很多，但由于这些共同邻居大多数都是中枢节点，根据角色函数计算可以得出这些共同邻居机场倾向于抑制机场之间形成链接，因此这些机场之间不会形成直航航线而是建立与中枢机场链接的中转航线，这恰恰符合这些机场的实际航线建立情况。实证显示，局部朴素贝叶斯模型可以获得明显好于原有局部相似性指标的预测精度[18]。

资源分配指数的思想还可以和局部路径指数的思想结合，也就是连接小度节点的路径一般而言意味着更紧密的关系。基于此，我们提出了所谓的重要路径指数（Significant Path Index）[19]，可以进一步提高链路预测的精度。

最近，我们注意到节点更偏向连接具有局部群落结构的节点——假设路人甲认识一个社团内部的某个人，如果这个社团越紧密，路人甲越有可能和这个社团的其他人认识。这种机制和社交网络中的朋友推荐很类似，因此我们提出了名为朋友推荐模型的链路预测算法，可以获得明显好于资源分配指数的效果[20]。因为实际算法只需要考虑局部的连接紧密程度，而不需要获得整个网络的社团分解，因此我们依然把这个方法归为局部相似性指标。

提出了一系列精确度很高的全局算法。

2015年，我们提出了一种名为 “结构微扰法”（Structural Perturbation Method）的新的链路预测方法，其基本原理是如果网络满足某些特定的演化规律，那么未知链路的加入应该尽可能少地影响网络的谱性质[21]。

2016年，我们提出了一种似然分析的方法来预测网络链路[22]。我们假设可以对任意具体的网络计算其哈密顿量，这样原则上就可以得到该网络在网络系综中出现的似然，而我们预测的未知链路就是那些能够让网络似然增加最多（或者减少最少）的一组链路。

2017年，我们指出网络链路预测等价于为邻接矩阵中那些不为0的元素恢复它的原始值。基于现实世界中常见的网络的邻接矩阵往往是低秩且稀疏的事实，我们提出了一种新算法，通过求解满足最小化核范数的矩阵，来进行原始的网络临界矩阵的恢复，从而事实上解决了对应的链路预测问题[23]。

这三种方法具有共同的优点，就是预测精度非常高，都属于当前已知的精度最高的算法群。但也有共同的缺点，就是计算复杂性比较高，对于超大规模网络往往不适用——这也是全局算法普遍遭遇到的困难。

设计其他类型网络中的链路预测算法，包括有向网络和含权网络。

我们注意到不同权重的连边再链路预测算法中扮演的角色并不一样，事实上，权重较低的弱连接往往反而蕴含更多信息，这是因为强连接附近有很多冗余边，互相降低了各自的信息价值。基于此，我们将原来无权网络的相似性指标推广到含权网络中，并引入了“弱连接效应”，所得到的预测精度明显好于直接简单的推广[24]。该方法还可以进一步变形，以获得更佳的预测精度[25]。

我们还探索了如何预测有向网络中的链路的方向和存在性[26,27]。特别地，我们提出了有向网络的势能理论[27]。势能理论假设，给定一个有向图，节点的势能沿着边的方向降低一单位的能量；若一个子图中所有节点的势能都可确定，则称此图是可定义势的。可定义势的结构有很多，但将势能理论同聚类性和同质性联系起来，便可推断出由4个节点和4条有向边所组成的Bi-fan结构应是有向网络中最显著的。

文章基于链路预测模型在15个真实网络中验证了这一推断：Bi-fan对应的预测器的预测效果最准确也最稳定。

对链路预测算法的若干理论问题进行了深入的分析。

通过抽样在观察到的网络中选出一部分链路作为测试集，假装我们不知道测试集的信息，然后用剩下的数据来预测测试集，这是链路预测算法评估必然的一步。

一般而言，抽样的方法有两种：随机抽样（常见于未知边预测）和按时间选取最新的链接作为测试集（常见于未来边预测）。我们认为，生物网络中的未知边，往往是比较冷门的节点之间的连边，因为我们对这些节点的认识不充分。所以，或许能够更好预测这些冷门节点之间连边的算法更具有实用性。

基于此，我们提出了一种新的抽样算法，可以通过调节一个单参数控制测试集倾向于连接热门节点还是冷门节点，并设计了专门针对“冷边”的链路预测算法[28]。

迄今为止，让人遗憾的是，我们并不知道一个算法是否“足够精确”。针对一个完全随机的网络，“什么都预测不到”可能已经是最好的结果了，但是针对一个非常规则的网络，聪明的方法可能能够100%进行预测。知道了一个网络的链路在多大程度上“能够被预测出来”，就能够提供给我们很强大的工具，使得我们可以去判断算法是否已经接近甚至达到预测的上界，是否还有提升的空间。事实上，这个“可被预测的程度”，本身也可以看做是网络重要的一种性质。

为了衡量网络可被预测的难易程度，我们提出了一个假设：网络越是具有某些规律性，越是容易被预测。进一步地，我们认为，如果随机从网络中抽取出一小部分链路，网络的特征向量空间受到的影响很小，就说明网络是具有规律性的[21]。

在这种思路的基础上，我们应用类似于量子力学中对哈密顿量做一阶微扰的方法，假定减少或者加入少量链接所产生的微扰，只对特征值有影响，而对特征向量没有影响，这样可以观察微扰后通过这种办法重构的邻接矩阵和真实邻接矩阵的差异。

我们提出了一种度量这个差异的参数，叫做结构一致性，这个指标是网络的一个特征指标，被认为可以直接用来刻画网络的“可被预测的程度”。

将链路预测算法和相关思想应用于网络演化建模的理论分析中。

网络在演化生长的过程中表现出很多有趣的结构特征，比如集聚性、社团性、无标度性、小世界性等等。建立网络模型重现观察到的结构特性，是最常见的理解网络生长过程潜在驱动力量的方法。

针对同一类网络甚至同一个网络，往往有多个理论模型，每一个模型都声称能够捕捉真实网络某几个方面的特征。由于刻画网络结构的特征量成百上千，数不胜数，模型1可能在刻画特征A, B, C方面胜过其他模型，而模型2给出最符合特征D, E的结果——事实上，直到现在，我们没有一种本质上有效的方法，来判断不同模型的优劣。

我们认为每一个演化模型原则上都对应于一种链路预测的算法，因此，如果把当前网络的真实结构看作基于一段时间之前的网络在模型对应的链路预测算法下预测得到的，我们就可以分析当前网络出现的似然。

显然，让当前网络似然更大的算法所对应的演化模型更好——这实际上提供了一个评价网络模型优劣的不依赖于任何特定的结构特征或特征组的统一的平台。

利用这种思想和方法，基于大量真实网络的演化数据，我们对比分析了若干演化机制，获得了直接比较网络结构特征所得不到的深刻洞见[29-31]。

参考文献

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

[15] 吕琳媛, & 周涛. (2013). 《链路预测》..高等教育出版社.

[16] Zhou, T., Lü, L., & Zhang, Y. C. (2009). Predicting missing links via local information. The European Physical Journal B, 71(4), 623-630.

[17] Lü, L., Jin, C. H., & Zhou, T. (2009). Similarity index based on local paths for link prediction of complex networks. Physical Review E, 80(4), 046122.

[18] Liu, Z., Zhang, Q. M., Lü, L., & Zhou, T. (2011). Link prediction in complex networks: A local naïve Bayes model. EPL (Europhysics Letters), 96(4), 48007.

[19] Zhu, X., Tian, H., Cai, S., Huang, J., & Zhou, T. (2014). Predicting missing links via significant paths. EPL (Europhysics Letters), 106(1), 18008.

[20] Ma, C., Zhou, T., & Zhang, H. F. (2016). Playing the role of weak clique property in link prediction: A friend recommendation model. Scientific Reports, 6, 30098.

[21] Lü, L., Pan, L., Zhou, T., Zhang, Y. C., & Stanley, H. E. (2015). Toward link predictability of complex networks. PNAS, 112(8), 2325-2330.

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

[23] Pech, R., Hao, D., Pan, L., Cheng, H., & Zhou, T. (2017). Link prediction via matrix completion. EPL (Europhysics Letters), 117(3), 38002.

[24] Lü, L., & Zhou, T. (2010). Link prediction in weighted networks: The role of weak ties. EPL (Europhysics Letters), 89(1), 18001.

[25] Zhao, J., Miao, L., Yang, J., Fang, H., Zhang, Q. M., Nie, M., Holme, P. & Zhou, T. (2015). Prediction of links and weights in networks by reliable routes. Scientific Reports, 5, 12261.

[26] Guo, F., Yang, Z., & Zhou, T. (2013). Predicting link directions via a recursive subgraph-based ranking. Physica A, 392(16), 3402-3408.

[27] Zhang, Q. M., Lü, L., Wang, W. Q., & Zhou, T. (2013). Potential theory for directed networks. PLoS ONE, 8(2), e55437.

[28] Zhu, Y. X., Lü, L., Zhang, Q. M., & Zhou, T. (2012). Uncovering missing links with cold ends. Physica A, 391(22), 5769-5778.

[29] 刘宏鲲, 吕琳媛, & 周涛. (2011). 利用链路预测推断网络演化机制. 中国科学: 物理学 力学 天文学, 41(7), 816.

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

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