圈子成立了，都说话了写博文支持，但是实在是忙，拖了一天又一天。

 

从最近的东西往回写，总是要容易一些，所以先说说复杂网络上的链路预测(link prediction)吧。这个方向我从09年才开始做，还算比较新。印象中我还从来没有正式讲过这方面的题目，倒是吕琳媛在成都香港都讲过。那就捡重要的说说吧。

 

链路预测这个问题非常简单，就是给定一个网络，让你根据现在已知的链接情况，预测未知的链接。当然，测试算法是否准确，一般来说都是随机取出一些边，假设是不知道的，再看预测的结果是否准确。

 

为什么要研究这个问题了，我觉得有三点。第一是研究链路预测问题可以帮助我们理解网络演化的内在机制。比如针对一个特定的含时演化网络，七七八八的人提出了若干模型（若干机制），都可以生成一些人工网络。里面有一些簇系数接近，有一些平均距离接近，有一些模块结构类似，有一些度分布更像（模块结构和度分度哪个更像，还真不是个简单问题），那么怎么办呢，什么机制更可信呢，直接从网络拓扑特征来看不好比较。链路预测提供了一种比较简单的方法（而且只有一个指标，这个是关键，比如你要找老婆只看胸大胸小，这个就容易了；还要贤惠聪明漂亮体贴——一旦综合考虑，就麻烦了），只需要根据时间先后，把最后M条边移走不要（一般是几百到几千），然后根据各自的机制从M条边以前演化生长，看看谁能把那M条边长出来，至少谁能长得最准确，就是个判断标准了。

 

第二就是这个咚咚可以用来评估各种节点相似性的度量指标。节点相似性是个基本问题，聚类啊，群落啊，都和这个有关系。在很多情况下，可以假设越相似的节点越容易相连（不完全，比如性关系网络，男的和男的连，毕竟是少数），那么利用这个相似性指标进行链路预测，有的效果好有的效果坏，优劣就出来了（当然不是绝对的，但是有参考价值）。举个例子说吧，今年我写了篇狗屎文，讨论了9个比较有名的只考虑公共邻居的相似性指标，比较他们的链路预测精度。然后我提出一个也只考虑公共邻居的指标，把那9个都灭了。这个文章写完也就算了。后来又出了一篇Physica A的论文，在实际系统中发现用我那个指标做加权，效果好；最近又审到一篇论文，重新比较了9+1个指标做群落划分，发现还是我那个好。说明这个链路预测还是能够经得住考验的。

 

第三就是应用起来有前景。比如说蛋白质折叠网络、新陈代谢网络、基因调控网络等等生物网络，一条边是否存在，完全靠实验。由于实验很贵，如果能够在实验前先作预测，而且预测精度还行，好歹能够省两个钱。这个就叫做missing link prediction——预测本来存在但是我们还不知道的。还有比如在线的社区网络，可以通过这个方法进行预测，根据预测结果推荐朋友。这个叫做link prediction for evolving networks——预测将来可能存在的连接。这两种应用研究都大有可为。

 

现在主流的方法是基于相似性的方法，因为很多复杂的方法都可以归根到底落入相似性的圈子里面。当然，机器学习也是主流，关系模型也是主流，但是我都搞不懂，而且这些工作一般需要知道一些其它信息，比如每个点的内容、属性等等，物理上不简洁。至于这个方向会如何发展，我们准备怎么做下去，限于水平（毕竟所涉不深），就不在这里谈了。

 

------5篇推荐文献------

[1] L. Getoor, C. P. Diehl, Link Mining: A Survey, ACM SIGKDD Explorations Newsletter 7 (2005) 3.

[2] D. Liben-Nowell, J. Kleinberg, The Link-Prediction Problem for Social Networks, J. Am. Soc.

Inform. Sci. Technol. 58 (2007) 1019.

[3] A. Clauset, C. Moore, M. E. J. Newman, Hierarchical structure and the prediction of missing links in networks, Nature 453 (2008) 98.

[4] T. Zhou, L. Lü, Y.-C. Zhang, Predicting missing links via local information, Eur. Phys. J. B 71 (2009) 623.

[5] L. Lü, C.-H. Jin, T. Zhou, Similarity index based on local paths for link prediction of complex networks, Phys. Rev. E 80 (2009) 046122.

 

 

------相关链接------

 

相关博文 http://www.sciencenet.cn/m/user_content.aspx?id=265536  

                  http://www.sciencenet.cn/m/user_content.aspx?id=276418

会议论文 ACM-CIKM-CNIKM-2009 Hong Kong