经过两年多的努力《链路预测》这本小书终于和大家见面了！在这两年多的准备过程中，可谓痛并快乐着，第一次的出版经历让我兴奋激动的同时也常常纠结忧愁，相比之下，拥有多次出书经历的本书的合作者周涛老师就显得从容淡定许多，在本书的撰写过程中他对于我的帮助是巨大的，这些都将成为我一生的财富！

要感谢的人太多太多，特别是我的家人，没有他们的悉心照料我是无法有足够的信心和精力完成本书的。这里特别要感谢一位女士Mrs. Yang。你给我的勇气的鼓励成为我前进的无限动力，你和蔼的面容和阳光般的微笑让我充满力量。在这里我要和你一起分享我此刻的喜悦，希望我的快乐也能够使你充满力量，永远的健康快乐！

前言

预测是一切可称之为科学的学科所不能回避的问题。一切不能转化为某种预测的理论都是不值得信赖的, 与此同时, 一切坐在神坛上不可一世的理论都时时刻刻战战兢兢地接受着预测的挑战, 一旦它的预测被证明是不正确的,固若金汤的神坛就轰然崩塌了。

亲爱的读者, 你现在看到的, 是一本专门讲预测的书。和大家以前经常遇到的股价预测、水文预测等不同, 本书不关注从一个时间序列的历史中预测未来; 与量子力学中对微观粒子状态和运动的预测也不同, 本书并不依赖于某种第一性原理。本书所关心的问题, 是在一个网络中, 如何通过已经观察到的节点之间的连接, 来重现因为数据缺失尚未观察到的连接, 或者预测未来将要出现的连接。

网络已经成为描述形形色色复杂系统最重要的工具之一。来自物理学、生物学、信息学、经济学、管理学等越来越多学科的学者, 都已经认识到, 真实系统的复杂行为,包括演化方向、标度涌现、脆弱性和鲁棒性、群集协同行为等, 都不仅根植于个体的行为, 还源于个体与个体之间的相互作用。网络中的链路预测问题, 得益于学术界对网络科学本身重要性的认识, 也成为横跨多个学科的核心科学问题。链路预测算法, 可以帮助提高生物实验的效率,可以用于微博中的关注对象推荐和电子商务中的个性化产品推荐, 甚至可以用来预测美国联邦最高法院法官的投票。链路预测是一大类普适问题的抽象, 在未来的科学和工程中将扮演越来越重要的角色。

我们和很多同行与高等教育出版社共同力推“网络科学与工程丛书”, 正是因为看到了网络将在未来的多学科交叉中起到中枢的作用。网络科学自身的发展, 就像其他一切成熟和正在成熟的科学一样, 需要经历预测和控制的检验。一切的演化模型和动力学分析, 最终都需要视其能否给出更精确的预测和更高效的控制来判断价值。尽管本书不奢求也不可能解决有关网络预测中的所有问题, 但是我们相信, 它必将对“网络科学与工程”发展成为一个成熟学科贡献自己的匹砖片瓦。

本书共分为九章, 第一章介绍了关于网络的基本概念,可以将本套丛书中另外两本——《网络度分布理论》和《网络科学导论》作为参考阅读。第一章并不是《网络科学导论》的一个子集, 相反, 我们从网络分类和网络刻画方面给出了更宏观更全面的叙述。从第二章开始我们就进入了链路预测的世界。我们首先给出链路预测的基本概念, 包括问题的背景和意义, 问题的数学描述, 数据集划分的方法和预测精度的评价方法。第三章, 我们介绍了链路预测中最简洁的框架———基于相似性的链路预测, 给出目前的20 余种相似性指标的定义。最后给出了这些指标在8 个真实网络中的预测精度比较结果, 据我们所知, 这应该是目前最全面的一次比较。第四章, 我们将介绍关于链路预测最复杂的框架———基于似然分析的链路预测模型。这一章体现了链路预测的繁复之美, 如同一件艺术品值得细细品味。第五章至第七章, 我们将分别针对含权网络、有向网络和二部分网络进行更加有针对性的方法介绍。对于关注特定类型网络的读者来说, 你一定能在这些章节中找到适合自己的武器。链路预测在理论上的研究已经是极富挑战而又充满乐趣的事情了, 但是相比较其应用价值的开发还只是冰山一角, 且略显平凡。幸运的是, 我们意识到这一点并在这个方向上持续努力, 已经取得一些成果。在第八章中,我们将结合一些实际的应用场景来进一步展现链路预测的意义和价值所在。希望这一章的内容可以起到抛砖引玉的作用, 激发更多有价值的应用研究出世, 并产生越来越多真正的社会经济贡献, 这才是这个研究方向生机勃发的基本动力。第九章给出了一个小结, 我们想说的是, 这虽然是本书的结束, 但是在链路预测研究的道路上我们一直在前行———任重而道远。

对于大部分读者来说这可能并不是一本有趣的读物, 但是我们相信它绝对称得上是一本有用的小书。如果书中能有一句话、一幅图, 或者仅仅是一个短语、一个公式能够让大家有所启发或带来灵感, 这就是我们最大的成功。这本书有很多出众的地方, 比如说读者从这本书中看到的绝不仅仅是链路预测的理念和方法, 还包括了对于各种类型复杂网络结构和功能的全方位的认识———我们特别注意兼顾了内容的“深”和“广”。但是, 这本书仍有很多不足之处, 比如说链路预测中很重要的一部分内容, 是机器学习的方法, 我们都没有讲———不是不重要, 而是以我们的背景和能力, 不足以把这一部分写好。与其拼凑文献写两章“看起来很美”的文字, 不如留白。

很多学生, 特别是刚刚入门或者说正准备迈入科学研究行列的青年学者经常发来邮件询问一些基本的概念。我想这本书正是你们所期待的。书中, 我们详细地给出有关链路预测这个研究方向相关概念的定义和描述, 同时为了帮助理解还给出很多示例。此外, 在本书的附录C 中, 我们将一些经典算法的程序也整理出来, 以方便读者阅读、理解和使用, 我想这应该是本书的一大特色。这些程序代码也将在链路预测小组的网站上公布(www. linkprediction.org), 可供大家直接下载使用。

我们要感谢为本书做出巨大贡献的几位同学, 他们是张千明、朱郁筱、王文强和潘黎明。千明在社交网络分析和应用方面很有研究, 他的一些建议和帮助给予本书增色不少。郁筱系统地整理了本书附录C 的Matlab 程序代码,并细心地添加了对重要语句或较难语句的解释。文强对于本书第八章应用部分和附录的梳理都有相当贡献。黎明帮助整理了关于书中极大似然模型的部分, 目前他主要从事链路预测方面的研究工作, 已取得一些成果, 例如本书第四章中介绍的闭路模型就是他的成果。此外, 黎明还非常认真地帮助我们整理和规范了全书600 条参考文献的格式,这真的不是一件容易的事情, 需要拿出绣花之耐心, 对于他的一丝不苟再次表示感谢!

除此之外, 来自汪小帆、陈关荣、史定华教授的建议使得本书在行文上更加严谨。还有一些朋友给予的意见使得我们的工作得以不断地完善和提高, 这里无法一一列出他们的名字。与他们的讨论与交流让我们颇受启发, 受益良多。

作者还要感谢家人和朋友在精神上的支持和生活上的照顾, 以及对作者持续忙碌的理解! 他们永远是我们坚强的后盾!

特别感谢高等教育出版社刘英女士对本书的持续关注和大力支持。她专业的指导和帮助让我们在撰写的过程中更加得心应手, 使得本书最终能以最好的形态呈现在大家面前。

最后, 作者特别感谢每一位读者, 是你们的阅读, 使得我们两年以来精心的准备和辛苦的撰写变得有价值! 我们相信, 你们也是未来和我们一道努力将“网络科学与工程”从一个前沿热点方向建设成为理论体系完善、应用场景丰富的一门成熟学科的战友。

希望有更多的有志之士加入我们的队伍, 在这条路上, 一直走下去。

                                            吕琳媛　周涛