师说 | 网络名师博客群 of 电子科技大学

复杂网络链路预测11075031进展报告[完整版]!!

周涛 | 2011-12-29 | 科学网 | 464次阅读

1. 年度计划要点及调整

总计按照申请书计划执行。申请人认为多网络（Multi-Networks）将会成为社会网络分析研究的未来热点，故有意开展这方面的相关工作。除存在性外，下一步将更多强调对于链路方向性、权重和角色的预测，亦将在海量数据集上测试我们的方法。

2. 研究工作主要进展和阶段性成果

在项目执行的头一年，研究小组共完成科研论文9篇，除两篇预印本尚在审稿中外，其余7篇已经发表，其中4篇英文论文均发表于SCI期刊，包括一篇Physical Review E，一篇EPL，两篇Physica A。特别值得强调的是，我们2011年初在Physica A发表了链路预测领域最完整的综述，至撰写此报告时不到一年，在Google Scholar上已经获得了29次引用，一大半来自海外研究单位，包括一流的期刊和顶尖的会议，并被Steve Gregory [JPA2011] 在引用时赞誉为“Excellent Review”。该文章在结题时应该能够获得超过100次的引用，并将有助于提高本项目小组在国际上相关研究中的话语权。于此同时，我们搜集了国际上关于链路预测的几乎所有发表的论文，已经作了一个静态网页公布，并正在建立学术网站，国际国内很多学者对我们在推动和宣传链路预测研究的努力表示赞赏。我们还将在2012年底完成一本名为《链路预测》的专著，在高等教育出版社出版。本项目总体进展良好，籍由基金委的支持，项目完成后当形成一支国际一流的链路预测研究团队。

在本项目的支持下，研究团队22人次参加海内外各种会议或学术访问并作大会报告、特邀报告、交流报告等，此处不再赘述。特别地，本项目负责人于今年4月在镇江担任主席，举办《网络结构与拓扑识别学术研讨会》，在会上作了名为“复杂网络链路预测”的大会报告；于今年10月在成都担任主席，举办《第七届全国复杂网络学术会议》，与会68个报告中，有两个是关于复杂网络链路预测的。这两次会议都是国内相关研究领域的学术盛会。本项目负责人还与12月在首尔的韩国统计物理会议上作为两个特邀演讲者之一，报告了有关链路预测的研究工作。

本项目对于青年教师和研究生起到了重要的培养和支撑作用！

三位青年教师直接受到了本项目的支持下，包括电子科技大学的刘震老师、周涛老师和西南财经大学的刘宏鲲老师。三位老师不仅在高水平期刊发表了直接相关的研究论文，而且学术生涯有了长足发展，其中刘宏鲲老师和刘震老师获评副教授，周涛老师入选“教育部新世纪优秀人才计划”并获得第十二届中国青年科技奖。

五位博士生，包括瑞士弗里堡大学的吕琳媛（博三）和刘伟平（博三），电子科技大学的张千明（博一）、曾伟（博一）、朱郁筱（博一），以及一名硕士生，电子科技大学的王文强（硕一）受到了本项目的支持。其中，吕琳媛博士在读期间，就已经成为本项目的领袖，并且在国际相关研究领域有相当的知名度和影响力。本项目为研究生提供了丰富的学术交流机会，其中曾伟在香港浸会大学访问，王文强在香港城市大学访问，张千明和朱郁筱在北京计算科学研究中心访问。

尚有一批学生和老师在从事本项目相关研究工作，但还没有形成研究论文，无法在本进展报告中体现出来，明年当有所体现。以本年度有所贡献的9位成员观之，一个特别可喜的现象是，六位学生表现出了明显强于三位老师的能力和成果，譬如在王文强尚是本科生的时候，就和当时研究生二年级的张千明合作撰写论文发表，没有与任何老师合作；吕琳媛博士不仅以单独作者身份发表综述论文，还与刘伟平博士在Physical Review E发表13页长文，亦未与任何老师合作。

主要学术成果包括以下四个方面。

一、完成链路预测中英文综述各一则。

去年底和今年初在《电子科技大学学报》和《Physica A》各出版链路预测综述一则，其中后者为国际上最完整的链路预测的综述，今年发表后，Google Scholar已经引用29次。在该文中，我们介绍了链路预测研究的背景、现状和存在的主要挑战，详细陈述了基于相似性的链路预测、链路预测的概率模型和基于最大似然分析的链路预测三种方法，最后对各种可能的应用进行了介绍和讨论。这两篇文章的发表，对于推动国内国外链路预测的研究，增加本小组的话语权，具有重要的意义。

二、提出了利用链路预测方法评估网络演化模型的方法。

以往研究网络演化机制的常用方法是直接建立演化模型推测影响网络演化的因素。这类主流建模方法的基本思路是，对基于某些因素构建出的网络分析其统计特征，如果具有和真实网络接近的统计性质，那么就认为这些因素对网络的结构影响显著，也即这些因素是网络演化的重要机制。但是，由于刻画网络特征的统计量众多，分别由不同因素驱动的演化模型很难全面符合所有统计量的特征，有些满足其中一部分，有些满足另外一部分，因此很难客观的定量化的比较哪些模型更能刻画网络特征，哪些才是影响网络演化的主导因素，以及这些主导因素在网络演化过程中分别起到了多大的作用等。

链路预测其本质是挖掘网络产生连边的原因和驱动力。实际上，一个演化模型原则上都可以对应于一种链路预测的算法。因此，借助链路预测的理论框架和评价方法可以定量化地对不同演化模型所对应的链路预测算法进行评价，从而间接地对演化模型的表现进行定量比较。本项目组2011年在《中国科学G》上撰文介绍基于节点接近性的链路预测方法，讨论利用链路预测推测网络演化机制的基本框架，最后以中国城市航空网络为例验证此方法的有效性。研究结果发现，在影响航空网络的四个外在因素：人口、距离、GDP和第三产业产值中，以第三产业为驱动的模型能够产生最佳效果。这些结论与偏相关分析和因果分析的结论一致。实际上，在所有的外部因素中, 只有以第三产业为驱动因素的模型可以再现航空网独特的双段幂律分布。

进一步地，本项目组2011年在《电子科技大学学报》直接用链路预测和网络系综的办法，建立了一套量化比较的机制，在这个机制下面，比较了有代表性的互联网演化模型的优劣（以真实的互联网数据为基准），并发现通过链路预测的评价机制得出的模型的“最佳参数”在仅仅考虑表达新增节点的性质的时候，要明显好于通过其他办法得到的“最佳参数”。我们从链路预测的框架中跳出，尝试用似然分析这个更普遍的思路来解释同样的问题，刚刚提交了预印本文章(arXiv: 1112.4597)，目前在《欧洲物理快报》评审中。

这些工作包含了一个重要的思想，就是以前的研究，总是关注网络从无到有的过程，希望找到一个普适的模型，一股脑刻画网络一生的行为。实际上，网络初始的增长和中后期的增长机制可能是完全不一样的！链路预测更像是关注网络从少到多，从当前到未来的短期行为，这可能更加重要！即便是在一个模型下，通过与真实网络对比，不同增长时期的“恰当的参数值”也会不一样。这个问题在以前的研究中罕有讨论，但是可以通过我们提出的办法进行分析、挖掘。尽管这些工作远非成熟，技术上还有很多值得斟酌的地方，但是其中蕴含的想法，对于复杂网络建模研究，有重要的借鉴意义。如果有一天，复杂网络的研究真正被纳入了统计力学的理论框架下，那么一定得益于网络系统的理论，其中链路预测是一个重要的推动力量。

三、提出了基于共同朋友的朴素贝叶斯模型。

链路预测是网络数据挖掘中最基本的问题，从指导系统生物学实验到在线社交网络朋友推荐等多方面有广泛应用。共同邻居方法假设两个节点对拥有的共同邻居越多它们越倾向于链接，这一方法在很多实证网络中都证明是有效的。本项目组认为不同的共同邻居对于节点对产生链接的贡献应该是不同的，比如两个人的共同朋友可能很多，但这些朋友可能是益友或者是损友，它们各自对于促进这二人成为朋友的作用（影响力）应该是不同的；而传统共同邻居方法的缺陷在于没有对不同共同邻居的作用进行区分。基于此，我们提出了一种局部朴素Bayes模型，这个模型定义了一个角色函数可以较准确地揭示不同共同邻居的作用。在对美国航空网络的实证分析中发现，有些机场之间虽然共同邻居很多，但由于这些共同邻居大多数都是Hub节点，根据角色函数计算可以得出这些共同邻居机场倾向于抑制机场之间形成链接，因此这些机场之间不会形成直航航线而是建立与Hub机场链接的中转航线，这恰恰符合这些机场的实际航线建立情况。因此相对于共同邻居方法，局部朴素Bayes模型的确可以更好地刻画美国航空网络的网络特征。我们提出的思路和方法在如食物链网络等其他网络中也得到了证实。相关文章于今年10月在《欧洲物理快报》上发表。

四、量化分析了信息挖掘中的凸透镜和凹透镜效应。

以前链路预测大多考虑缺失边的挖掘问题，没有考虑算法的自适应动态发展。如果我们把链路预测应用到社会网络的朋友推荐（譬如新浪已经利用共同邻居进行微博好友关注的推荐），那么就可以假设用户以一定的比例接受了系统的推荐。在此之后，我们会继续进行推荐，这实际上是一个迭代演化的过程。类似地，如果考虑二部分图（用户-商品网络）上基于链路预测的推荐，可以假设用户以一定的比例接受系统推荐，之后我们需要继续推荐。

在这个过程中，一个很重要的问题就是，我们的推荐到底是帮助用户拓广视野，还是让用户视野变得越来越狭窄——总是阅读类似的新闻，购买相似的商品，结交同一个社区内的朋友……本项目组2011年在Physical Review E撰文提出了一种改进的有偏扩散那算法，可以更好进行信息挖掘，特别重要的是，文章指出，一个挖掘算法在系统层面可能产生名为“凸透镜”或者“凹透镜”的两种不同效应，前者让用户视野愈发狭窄，后者让用户视野开阔。

3. 下一年度工作计划

除了具体的研究问题进度上有或快或慢的参差，整体计划没有变动。下面仅特别强调2012年度可能的重点。

1. 会出版《链路预测》专著，作者为：吕琳媛、周涛。

2. 会在链路预测的Ising Model及变体方面做出系列成果。

3. 会将部分重心转移到多网络的链路预测上（原申请书未涉及此问题）。

4. 会更多考虑对方向性、权重、角色属性的预测。

会继续支持学术会议和学术交流，但尚未形成成熟具体的计划。

4. 当年经费使用情况和下一年度经费预算

[请傅老师尚老师填写]

5. 存在的问题、建议和其他需要说明的地方

[暂无]

6. 标注基金号的论文目录