几天前，涛兄写了一篇关于为什么研究链路预测的博文，从三个方面阐述了研究链路预测的意义和价值。这里我想从另外一些方面谈一谈复杂网络的链路预测。其实链路预测（link prediction）作为数据挖掘（data mining）的一个研究方向已经不是什么新问题了，尤其是对搞计算机的人来说（CS）。他们提出了一系列基于马尔科夫链以及机器学的方法和概率模型。在实际应用中已经能够得到很好的预测效果。这使得这些方法在工程上得到很多应用。但是从科学研究的角度看虽然CS的算法精度高，但是没有更多的insight。看CS的文献你会发现他们常常将不同的算法组合起来已得到更好的精度，但是很难解释出精度提高的原因（我本人看的文献有限，这里谨代表个人观点），并且很难说出为什么这个网络用这种方法好，而那个网络用这种方法不好。这些问题对谁来说都是很难回答的，CS也好PH也好，但正是这些问题的存在使得研究LP变得更加有意义。试想如果我们可以做到在预测前根据目标网络的拓扑结构以及统计性质选择相应的算法已得到较好的预测结果，这在实际应用中将节省多少时间和计算的成本。不仅如此，如涛兄所说，在研究这个问题的过程中也会对于我们理解网络的演化机制有所帮助。

我们当前对于LP的研究是基于节点相似性的。这种相似性可以根据节点的属性进行定义。例如，如果两个人具有相同的年龄，性别，职业，兴趣，等等，我们说他俩很像。但是在实际应用中这些节点的真实属性信息很难获得。比如在线友谊网络中，一个用户的注册信息是可以编造的，比如一个老男人为了能够找到更多的年轻mm朋友可以假装为一个年轻小帅哥。另外，就算获得了真实信息，我们也会遇到另外一个问题：在预测中我们应该选择哪些属性，以及他们在衡量相似性的时候所占的比例如何确定。另外一种定义相似性的算法是完全基于网络结构的。它可以进一步分为基于节点的和基于路径的。基于节点的一共有十种，包括：common neighbors，Salton，Sorensen，Adamic-Adar，Jaccard，HPI，HDI，LHN-I，Preferential Attachment和我们提出的Resource Allocation。他们都可以看作是基于局部信息的指标。关于这十种指标的定义以及表现的比较可参见文章（EPJB 71，623，2009）。基于路径的有三种，包括我们提出的Local path指标以及Katz和LHN-II（PRE 73，026120，2006）。Local path算法是在CN的基础上考虑了次级邻居的算法，可以算是一种半local的算法。而Katz和LHN-II都是基于网络全局信息的。在文章（PRE 80，046122，2009）中，我们比较了三种算法CN（考虑长度为2路径），LP（考虑长度为2和3的路径）和Katz（考虑所有路径）。结果显示，LP作为一种半local算法具有较低的计算复杂度，同时可以达到较好的预测精度。除了上述两类定义外，还有一类相似性是基于网络上的随机游走的，可参见（IEEE Trans. Knowl. Data. Eng. 19，355，2007）。此外，还有一些比较复杂的定义，例如基于矩阵森林理论的方法，可传递的相似性定义（PRE 80，017101，2009）以及基于网络层次结构的方法（Nature 453，98，2008）。

到目前为止，虽然已经有一些关于链路预测的研究，但是对这个问题还没有一个很清楚的图景。很多问题尚存在。比如，含权网络的预测。我们做了一些较初步的工作（见附件），发现权重在预测的时候并不好把握。在有些网络中，如航空网络和科学家合作网，我们发现了链路预测的弱连接效应，即小权边起到更重要的作用。但对于为什么有些网络有weak ties效应而有些没有，我们还不能给出很好的解释。除了含权网络的问题之外，还有一个重要的问题就是time。对于sampling的网络，如食物链网络和蛋白质相互作用网络，对他们的预测更倾向于一种知识挖掘。而对于随时间演化的网络，时间因素是很重要的，不可忽略。最简单的方法是我们可以根据时间给网络的边赋予一定的权重，然后这个问题就又回到含权网络的预测了。

总之，链路预测有意义，有前景，值得关注！