统计物理处理网络的一个笨笨的方法就是分析网络系综（network ensemble）的结构[1]，看看在系综中不同网络出现的概率，或者叫似然（likelihood）。我们可以把这种方法叫做学院派的方法，因为我们在大学物理中学到的统计力学就是这个样子。最近，我们尝试把这种方法应用到链路预测中[2]，获得了迄今为止我们尝试过的所有方法中最高的精确度。

   学院派方法的思路是很简单的，大家权且当作回忆一下我们大学物理的课本：（1）为网络A定义一个哈密顿量（能量），H(A)，这个量越小，网络出现的可能性（似然）越大；（2）一个网络A出现的似然被定义为P(A)=1/Z* exp[-H(A)]，这里Z就是配分函数，是对给定的网络系综（一群网络的集合，根据需要定义）中所有网络A对应的exp[-H(A)]求和。对于非统计物理出身的朋友，不妨把Z简单看成归一化因子。

   接下来就回到了链路预测的老路子上面了。我们把网络分成两部分，一部分是训练集，不妨记为A1，一部分是测试集，不妨记为A2，我们要做的事情，就是看能够多大程度上利用A1的信息预测A2 中的边——如何定义算法的精确度，可以参考链路预测的综述[3]和专著[4]。下面我们就可以给每一条未在A1中出现的链路打分，然后认为得分越高的链路，实际存在的可能性越高（越有可能在A2中）。一条链路e的得分是：S(e)=exp[-H(A1+e)]/{ exp[-H(A1+e)]+exp-[H(A1)]}。

   虽然出发点和应用场景不一样，但是这套方法和社会科学中的指数网络模型[5]是类似的，这也说明了不同学科绕着同一个问题走啊走，是容易形成近似的解决方案的，尽管方法论、理念和路径可能都不一样（有从北峰上的，有从南峰上的，还有坐缆车的……）。类似的例子很多，例如pLSA和矩阵特征值分解的迭代寻优，又如麦克斯韦-波尔兹曼的最可几分布与计算机科学里面的最大熵方法等等。

   最后回到一个问题上，就是怎么定义H？这个可能的选择很多，根据不同类型网络生长组织的特性，可以有不同的定义方法。我们选择了一个大部分网络都具备的特征，就是集聚性或者同质性[6-8]（clustering or homophily），作为定义H的唯一考量。在此条件下，H被定义为：H(A)=-[b₃ln(TrA³)+b₄ln(TrA⁴)+ b₅ln(TrA⁵)+...]，显然这个式子是和subgraph centrality等指标[9]有关系的（考虑的是三阶圈、四阶圈、五阶圈……），而且可以写成特征值的形式（细节见[2]）。其中b3, b4, b5, ...这些量的确定可以用最大伪似然方法（maximum pseudo-likelihood method），细节可以参考[2,10]。

   结局可能大家都知道了，这种学院派的简单方法，并且只考虑了homophily一个特性，就完胜了很多经典的方法层次模型法[11]、随机分块模型法[12]、结构微绕法[13]等等，以及各种常见的相似性方法[3]。特别地，在甄别伪造的噪音边方法，这个方法的表现也是最好的。

   这个方法的缺陷就是很慢！很慢很慢！很慢很慢很慢！但是绝对要比[11][12]快！五十步笑笑百步。

参考文献：

[1] Bianconi, G.(2009). Entropy of network ensembles. Physical Review E, 79(3), 036114.

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

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

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

[5] Robins, G.,Pattison, P., Kalish, Y., & Lusher, D. (2007). An introduction toexponential random graph (p*) models for social networks. Social Networks, 29(2),173-191.

[6] McPherson, M.,Smith-Lovin, L., & Cook, J. M. (2001). Birds of a feather: Homophily insocial networks. Annual Review of Sociology, 415-444.

[7] Szabó, G.,Alava, M., & Kertész, J. (2004). Clustering in complex networks. In Complexnetworks (pp. 139-162). Springer Berlin Heidelberg.

[8] Kossinets, G.,& Watts, D. J. (2006). Empirical analysis of an evolving social network. Science,311(5757), 88-90.

[9] Estrada, E.,& Rodriguez-Velazquez, J. A. (2005). Subgraph centrality in complexnetworks. Physical Review E, 71(5), 056103.

[10] Anderson, C.J., Wasserman, S., & Crouch, B. (1999). A p* primer: Logit models forsocial networks. Social Networks, 21(1), 37-66.

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

[12] Guimerà, R.,& Sales-Pardo, M. (2009). Missing and spurious interactions and thereconstruction of complex networks. PNAS, 106(52), 22073-22078.

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

相关论文：

L. Pan, T. Zhou, L. Lu, C.-K. Hu,Predicting missing links and identifying spurious links via likelihoodanalysis, Scientific Reports 6 (2016) 22955.

免费下载链接：

http://www.nature.com/articles/srep22955