链路预测（Link Prediction）是网络科学中一个重要而有趣的基本问题[1][2]，其最简单的数学形式是给定了已经观察到了网络结构，来预测可能被我们观察漏掉的，或者未来会出现的一些链路（Links）。精准的预测结果既可以指导生物学的实验——因为大部分我们观察到的生物网络，只是真实网络中很小的一部分，需要通过大量实验来确定其他的部分，还可以用来进行社交网络的好友预测——如果我们能够猜到你未来交友的趋势，这种“猜你要关注”的推荐就会变得非常精准。好的预测算法本身，还给出了很多网络演化可能机制的暗示。

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

困难的是，链路可预测性的上界，并不像移动轨迹可预测性的上界[3]，可以通过柯尔莫洛夫熵与Fano不等式的结合来进行刻画。从自同构群的角度来看，待预测的链路（真实存在但是不在观测集合中）与实际不存在的链路总是可以区分的，所以一个真实网络的链路可预测性，原则上应该都是1——这种上界是没有价值的。

为了衡量网络可被预测的难易程度，我们提出了一个假设：网络越是具有某些规律性（regularities），越是容易被预测。进一步地，我们认为，如果随机从网络中抽取出一小部分链路，网络的特征向量空间受到的影响很小，就说明网络是具有规律性的。在这种思路的基础上，我们应用类似于量子力学中对哈密顿量做一阶微扰的方法，假定减少或者加入少量链接所产生的微扰，只对特征值有影响，而对特征向量没有影响，这样可以观察微扰后通过这种办法重构的邻接矩阵和真实邻接矩阵的差异。我们提出了一种度量这个差异的参数，叫做结构一致性（structural consistence），这个指标是网络的一个特征指标，被认为可以直接用来刻画网络的“可被预测的程度”。

大量的模拟网络和真实网络实验都支持了我们的结论：结构一致性越强的网络越容易被准确预测丢失的链路。我们利用结构一致性，提出了一种新的名为“结构微扰法”（structural perturbation method）的新的链路预测方法。这个方法在预测丢失的链路，以及甄别网络中添加的噪音边两方面都明显超过了当前主流的方法，包括知名的层次结构法[4]和随机分块法[5]，等等。

这个工作不仅提供了一种链路预测的方法，还提供了我们刻画网络的新的参数，对于理解网络有很大的帮助。举个例子来说，如果我们一直测量网络的结构一致性，当网络背后的演化机制发生变化的时候，我们就能够立刻观察到结构一致性的变化。

参考文献：

[1]L. Lü, T. Zhou, Link Prediction in Complex Networks:A Survey, Physica A 390 (2011) 1150-1170.

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

[3]C. Song, Z. Qu, N. Blumm, A.-L. Barabasi, Limits of predictability in humanmobility, Science 327 (2010) 1018-1021.

[4]A. Clauset, C. Moore, M. E. J. Newman, Hierarchical structure and theprediction of missing links in networks, Nature 453 (2008) 98-101.

[5]R. Guimera, M. Sales-Pardo, Missing and spurious interactions and thereconstruction of complex networks, PNAS 106 (2009) 22073-22078.

论文信息：

L.Lü, L. Pan, T. Zhou, Y.-C. Zhang, H. E. Stanley, Toward link predictability ofcomplex networks, PNAS 112 (2015) 2325-2330.

全文下载链接（免费）：

http://www.pnas.org/content/112/8/2325.abstract