复杂网络链路预测的研究现状及展望
吕琳媛
前言:做链路预测这个方向有一年多的时间了,有一些收获和体会。一直想写一个综述进
行总结,总是希望这个综述尽可能的包括更多更全面的信息,但是新的思想和结果源源不断
的涌现,所谓的综述也就无限期的搁置了下来。前不久刚刚和伟平合作发表了一篇关于利用
网络局部随机游走进行链路预测的文章,借此文发表之动力,总结一下链路预测这个方向的
研究进展以及展望。希望该文能对那些正奋战在这个方向上和希望在此领域有所建树的科研
工作者有所帮助和启迪。
(本文中所提到的具体的技术方法以及实验结果将在另一篇中文综述中详细介绍。)
1.链路预测及其研究意义
网络中的链路预测(Link Prediction)是指如何通过已知的网络节点以及网络结构等信
息预测网络中尚未产生连边的两个节点之间产生链接的可能性[1]。这种预测既包含了对未
知链接(exist yet unknown links)的预测也包含了对未来链接(future links)的预测。
该问题的研究在理论和应用两个方面都具有重要的意义和价值。
近年来,随着网络科学的快速发展,其理论上的成果为链路预测搭建了一个研究的平台,
使得链路预测的研究与网络的结构与演化紧密联系起来。因此,对于预测的结果更能够从理
论的角度进行解释。这也是我们相比计算机专业的人研究链路预测的优势所在。与此同时,
链路预测的研究也可以从理论上帮助我们认识复杂网络演化的机制。针对同一个或者同一类
网络,很多模型都提供了可能的网络演化机制[2, 3]。由于刻画网络结构特征的统计量非常
多,很难比较不同的机制孰优孰劣。链路预测机制有望为演化网络提供一个简单统一且较为
公平的比较平台,从而大大推动复杂网络演化模型的理论研究。另外,如何刻画网络中节点
的相似性也是一个重大的理论问题[4],这个问题和网络聚类等应用息息相关[5]。类似地,
相似性的度量指标数不胜数,只有能够快速准确地评估某种相似性定义是否能够很好刻画一
个给定网络节点间的关系,才能进一步研究网络特征对相似性指标选择的影响。在这个方面,
链路预测可以起到核心技术的作用。链路预测问题本身也带来了有趣且有重要价值的理论问
题,也就是通过构造网络系综并藉此利用最大似然估计的方法进行链路预测的可能性和可行
性研究。这方面的研究对于链路预测本身以及复杂网络研究的理论基础的建立和完善,可以
起到推动和借鉴的作用。
链路预测研究不仅具有如上所述的理论价值,其更重要的意义还是体现在应用方面。很
多生物网络,例如蛋白质相互作用网络和新陈代谢网络,节点之间是否存在链接,或者说是
否存在相互作用关系,是需要通过大量实验结果进行推断的。我们已知的实验结果仅仅揭示
了巨大网络的冰山一角。仅以蛋白质相互作用网络为例,酵母菌蛋白质之间 80%的相互作用
不为我们所知[6],而对于人类自身,我们知道的仅有可怜的 0.3%[7,8]。由于揭示这类网
络中隐而未现的链接需要耗费高额的实验成本。那么如果能够事先在已知网络结构的基础上
设计出足够精确的链路预测算法,再利用预测的结果指导试验,就有可能提高实验的成功率
从而降低试验成本并加快揭开这类网络真实面目的步伐!实际上,社会网络分析中也会遇到
数据不全的问题,这时候链路预测同样可以作为准确分析社会网络结构的有力的辅助工具
[9,10]。除了帮助分析数据缺失的网络,链路预测算法还可以用于分析演化网络,即对未来
Edited by Foxit Reader
Copyright(C) by Foxit Corporation,2005-2010
For Evaluation Only.
评论1