第41卷 第6期 电 子 科 技 大 学 学 报 Vol.41 No.6 复杂网络2012年度盘点
荣智海1，唐 明2，汪小帆3，吴枝喜4，严 钢5，周 涛2
(1. 东华大学信息科学与技术学院 上海 松江区 201620; 2. 电子科技大学互联网科学中心 成都 611731;
3. 上海交通大学电子信息与电气工程学院 上海 闵行区 200240; 4. 兰州大学计算物理与复杂系统研究所 兰州 730000;
5. 新加坡国立大学淡马锡实验室 新加坡 117411)
doi:10.3969/j.issn.1001-0548.2012.06.001
复杂网络是复杂性科学研究中受到最广泛关注的方向，在信息科学、物理学、生物学、数学乃至社会学、管理学等领域都产生了重大贡献和持续影响。十几年来，复杂网络的研究成果一直是《自然》、《科学》、《美国科学院院刊》等综合类顶级学术期刊的宠儿，每年均有数10篇相关论文发表。据不完全统计，仅在Review of Modern Physics、Physics Reports、Advance in Physics和SIAM Reviews这4个顶尖的综述性期刊就发表了17篇复杂网络的综述论文，今年又在Physics Reports上连续刊出两篇[1-2]。
于此同时，我们也注意到，在十几年的发展中，复杂网络研究的重点和焦点已经发生了较大的变化。可喜的是，以王文旭、严钢、吕琳媛、吴枝喜等人为代表的一群青年科学家，已经融入甚至影响着国际相关研究前沿发展的潮流。遗憾的是，国内相当一部分学者，还沉浸在老问题和老思路上，对于最激动人心的进展缺乏深入、完整的认识。基于这个现状，我们决定每年推出一期年末盘点栏目，邀请国内有代表性的青年科学家，主要就最近1~2年的国际重要进展进行介绍和评述。这个栏目从复杂网络起，将来也可能不限于复杂网络，而渗透进复杂性科学的其他方向，
譬如典型复杂系统分析、金融复杂性研究、群集动力学与社会计算、人类动力学分析等等。
本文重点关注网络功能方面的研究，邀请了荣智海、唐明、吴枝喜、严钢四位青年科学家就博弈、传播和控制展开介绍。希望各位读者能够通过阅读本文获得对复杂网络部分研究焦点的认识，开拓视野！
1 网络博弈：演化与合作涌现
合作现象在自然界和人类社会中普遍存在。最近一项研究表明化学物质转变为生命物质是通过分子间的协作完成的。自私的RNA通过自我复制只能形成短链，而文献[3]发现合适的策略可以促使不同的RNA自组织装配，搭建成合作的超循环回路，形成复杂的生命分子。
哈佛大学研究人员的实证性研究揭示了坦桑尼亚北部哈扎猎人(Hadza)之间的社会合作网络[4]。他们访问了17个营地的205名成年哈扎人(男性102名，女性103名)，在每个营地进行一轮多人公共品博弈，合作者(cooperator, C)的投入会使所有人受益，而背叛者(defector, D)会不劳而获。虽然背叛行为使得自私的人收益最大化，然而哈扎人之间更倾向于合作利他，且所形成的社会合作关
收稿日期：2012 11 07
基金项目：国家自然科学基金(61004098, 11005051, 11135001, 61273223, 11105025)；国家973项目(NCET-09-0317).
作者说明：本文由汪小帆、周涛筹划、组稿、修改、整理并联合撰写第一节，由荣智海和吴枝喜联系撰写第二节初稿，由唐明撰写第三节初稿，由严钢撰写第四节初稿。作者排名按照汉语拼音顺序，不分先后。
系具有现代社会网络的特征，如高聚类、同质性和互惠性等。这表明社会网络的一些结构特征以及合作机制可能在人类早期就已经形成。
由此可见，理解合作行为在个体间的涌现机制有助于人们认识从生命起源到人类社会组织等一系列重要课题。过去二十多年的理论研究表明网络互惠是一种重要的合作涌现机制，在网络上合作者通过与其他的合作邻居互助形成合作簇，可以有效抵御背叛者的入侵，从而促进合作行为的涌现。
最近一系列实证性研究试图揭示网络互惠是否在人类博弈中存在。研究人员基于著名的两人囚徒困境博弈，召集了近800名志愿者进行真人网络博弈实验[5]。他们将约20名志愿者分为一组，配对进行重复博弈，并考虑了随机交互、固定交互和动态演化三种作用方式。在随机交互中，每轮博弈结束后，个体以一定概率随机更新交互对象。在固定交互中，初始时刻群体随机连接，其后则保持交互对象不变。对于动态演化博弈，则在每轮博弈后，研究者随机选择k%对志愿者进行如下操作：对每对志愿者A和B，随机选择A并告知对手B之前的行为，若两者存在联系，则询问A是否要去掉其与B的连接，否则询问A是否愿意与B建立关系。通过考虑网络快速(k=30)和缓慢(k=10)演化的情况，发现合作行为只有在网络快速演化时能够维持。对其他情况，合作行为则随着重复博弈的递进呈明显下降趋势。此外，他们观察到快速动态演化的博弈网络的度分布更宽，C-C关系比C-D关系更稳固，D-D最脆弱，合作者因“得道”而容易吸引朋友，背叛者则因“失道”容易失去朋友。有意思的是，失去了朋友的背叛者接下来会倾向于合作。因此，连/断边可以看作奖励/惩罚措施，促使合作行为稳定维持于群体中。文献[6]做了类似的研究，也发现结构动态演化可以促进
合作和同配特性的涌现。他们将每组24名志愿者构成随机正则网络和六派系网络，采取12轮重复囚徒困境博弈，与文献[5]不同，在网络演化时，他们允许一方提出建立或者删除连接的请求，对手可以接受或拒绝该请求，若拒绝则两者保持原交互关系。通过引入该动态演化机制，在大量加减边时群体合作水平更高，而随着重复博弈接近尾声合作水平会递减。同时，他们发现C-C很容易建立联系，C-D间的联系最难建立，因此同配特性在合作者间容易涌现。
最近西班牙学者研究了更大规模网络上的人类博弈实验[7]。他们召集了1 200余名志愿者，分为两组放在平均度为4的规则格子和度分布异质的网络上。在网络固定和随机交互(每轮博弈后随机选择相同数目的邻居)的情况下进行约50轮的重复囚徒困境博弈，发现合作水平随着时间演化而递减，且不同结构的网络上合作水平相似，这与前期理论研究得到的异质网络结构促进合作的结论相悖。同时，他们也观察到个体合作倾向性与邻居合作数目(而不是邻居收益)相关。然而，需要指出的是，他们的研究没有考虑个体自愿连/断边的情况。因此，结合文献[5-6]的研究，笔者认为赋予个体合适的邻居选择机制，异质网络不促进合作的结论值得商榷，不同动态网络结构的作用会凸现。
在大多数研究中，博弈的收益矩阵往往是固定的，但实际系统的收益大小往往由组成系统的个体的集体状态决定(合作者密度越大，系统的效率越高)。文献[8]研究了一个多重适应的动态网络演化博弈模型：首先，囚徒困境博弈中个体采取背叛策略的诱惑量随系统中合作者的比例动态变化；其次，个体具有适应性，每轮博弈过后可以变更一定比例的博弈对象，在选择新交互对象时，个体更倾向和收益高的个体建立关系。在适当的
参数区间，研究发现系统能够演化到全合作者状态。此时个体间交互的连接度分布服从幂律形式，个体的聚类系数与其连接度成反比，即博弈动力学的多尺度演化导致了层次结构的涌现。
控制气候变暖可能是当前人类面临的最重要的公共资源博弈。只有各国投入足够的资金进行预防，才能有效阻止气候崩溃，否则人类有满盘皆输的可能。但困境在于虽然各国已经充分意识到维护气候这一公共资源的重要性，但仍然产生了哥本哈根的悲剧。研究人员通过改进公共品博弈模型，引入了集体投资阈值，如果参与者的投资低于该阈值，则所有人会冒一无所有的风险。通过演化博弈动力学分析，表明投资失败风险的引入可以让参与者意识到为了集体利益必须有所牺牲，从而与他人合作。研究发现无标度网络上参与博弈的群体规模多样性有利于全局协作，容易达到抑制气候变暖的目标[9]。
2 网络传播：从分析到干预
网络传播动力学研究已经发展了一系列重要的模型和理论用以描述各式各样的传播现象，例如革新扩散(innovation diffusion)、潮流发展(fad development)、疾病传播(epidemic spreading)、故障蔓延(failure propagation)等，探讨了许多重要因素(例如网络结构、连接权重和空间距离等)对于传播过程的影响，特别关注了许多真实传播过程的预测和控制研究。这些研究也为复杂系统中其他一些动力学行为(例如网络同步和网络博弈等)的研究提供了新的思路和方法。在过去的两年中，一些学者开始关注多层耦合网络的研究，而其上的传播研究将是一项极具挑战性的全新课题。最近，网络舆情、行为等传播研究越来越受到人们的关注，已成为当前最为热点的研究课题之一。更为重要的是，传播路径的还原和网络干预(例如
网络控制)可能成为未来十年之中最为热门的课题之一。以上研究热点可笼统地归为网络结构、行为规律、社会传播、路径还原和网络干预五个方面。
1) 网络结构。主要有多层/关系耦合网络传播动力学[10]、中尺度结构在传播过程中的作用[11-12]和节点影响力排序方法与稳定性分析[13-14]三个研究热点。对于多层/关系耦合网络，在大量实证的基础上，理解层间不同耦合关系(如依存、协作或抑制等作用)和耦合模式(如部分、一一或关联等匹配)对于单个或多个传播动力学行为的影响应是其首要任务，而关键节点与路径的定义及其在传播过程中的重要性等问题是其中的难点之一。考虑到真实多层耦合网络的复杂性和多样性，其上的动力学现象将会异常丰富多彩，可以预见的是围绕这一主题近期将会涌现大量的新工作。在网络的中尺度结构上，最近一些研究显示病毒可以被局限于那些高权重的边和节点[11]或是核心层[12]周围。非常自然地，其他一些中尺度结构如社区、派系、模体等在传播演化预测与防控中的作用如何将是值得深入研究的问题。对于节点影响力排序问题，自文献[13]利用K-CORE层次分解获得了比度更为准确的影响力指标之后，短短两年内其Google Scholar的引用已高达120余次，可谓当前炙手可热的研究课题。文献[14]改进了经典PageRank算法，提出了一种名为LeaderRank的快速算法，能够等到超大规模社会网络中影响力高端的排序。以这些人为源头进行信息传播，速度会比以PageRank或者朋友数目为标准确定的源头快很多。虽然几乎所有相关研究都致力于寻求一种快速而准确的普适排序方法，但是可能的关键问题是在网络结构和传播动力学确定的情况下给出一个快速而较为准确的排序方法，由此可以继续拓展和深化的空间还非常大。此外，节点排序
在噪声干扰下(如网络结构和动力学行为的变化)的稳定性分析也是一个值得关注的重要问题[15]。
2) 行为规律。自从2005年人类行为动力学研究兴起以来，基于人类行为规律的传播动力学研究便随之开展起来，主要集中于个体行为的接触时间[2]、空间迁移[16]和行为反应[17]等对于传播过程的影响。就目前研究现状来看，这类研究非常容易造成一些令人困惑的难题，根本原因在于个体行为动力学规律的多样性。例如大量实证研究表明，人类的行为在时间上具有阵发性，存在短暂的紧密爆发和长时间的静默，不能用传统的泊松过程刻画。目前的工作主要基于真实数据集展开研究，发现在有些情况下人类的阵发特性减慢了传播动力学过程，而在有些情况下却加快了传播动力学过程，急需从本质上探究人类的各种阵发特性(如发送时延和响应时延等)对传播动力学的影响。对于以上三个问题的研究，最近都有一些重要的实证和理论工作发表，例如时变网络[2]
和人口迁移模式
[16]
的研究，鉴于人类行为动力学
研究仍是当前研究热点之一，基于人类行为规律的传播动力学研究将会具有较为持久的生命力。
3) 社会传播。网络传播动力学研究不仅仅局限于流行病传播，还关注其他一系列的社会传播现象，例如谣言、时尚、政治意见、新技术的采纳、金融决策以及健康行为等等。对于传统的病毒传播，一个易感个体被感染的概率仅依赖于与其接触的那个感染邻居，而社会感染概率还取决于其他邻居的当前或历史状态[18-22]。这种感染的差异可能产生一些反直观的有趣现象，例如由于协同加强效应的存在，规则网络上的谣言(或行为)传播将会明显快于随机网络上的情况[18]。最近几个月，社会传播的实证工作越来越多，档次也非常之高，大都发表于Science、Nature和PNAS等顶级期刊上[23-25]。由此可见，目前社会传播研究是
当之无愧的热点之中的热点。除了必要的在线实证研究之外，抓住关键的传播机制，构建合理的传播模型用以描述这些有趣的传播现象也是当前亟需开展的工作。
4) 路径还原。相对于传播路径的预测，路径还原应是一个相反的问题，早先一直被计算机科学家和流行病学家所关注，而最近的一篇物理评论快报开始了关于扩散源点的定位研究[26]。毫无疑问地，传播路径的还原研究有助于传播过程的控制，其应用也非常广泛，例如舆情和疫情的防控。然而，这一研究在很大程度上受限于传播机理研究的进展，单单凭借利用数学统计方法和计算机技术很难发展出一套行之有效的还原方法。因而，如同社区检测研究一样，这类问题缺少一些物理的机制，更侧重于数学方法和实际应用，可能将成为数学家和计算机科学家所偏爱的研究课题，此时进入正当时！
5) 网络干预。网络干预是有目的的运用社会网络或社会网络数据来产生社会影响、加速行为的改变、改进性能，从而达到对个人、社团、组织以及群体的影响[27]。作为复杂网络研究的终极目标，这一研究课题自然是非常重要的。文献[27]描述了四种网络干预的策略，每种策略又有多种替代策略。许多策略综合了不同的数学算法。因此，研究者对干预可以有许多选择，选择合适的网络干预取决于可用的网络数据、行为的特征、已有的流行程度和项目的社会背景。鉴于网络干预涉及范围之广泛、面临情况之复杂以及可选策略之多样，其研究必将博大精深，源远流长。文献[28]对于有向网络的控制研究更是激起了研究学者们对于这类问题的极大兴趣。对于这类研究，虽然控制理论的应用当然地成为重头戏，但是如何将网络动力学研究融入其中，应该是控制理论
学家和物理学家们共同面临的一大挑战。下一节将更深入剖析网络控制的进展和问题。
3 控制复杂网络：面朝下一站，蜿
蜒前行
回顾网络科学过去十多年的发展，人们的主要兴趣和精力大多放在对网络自身的结构和网络上的动力学过程进行建模、分析乃至预测；朝前看，我们将触及复杂网络研究的下一篇章中的核心内容，即，对复杂网络系统进行定性调控乃至精确控制。
在这方面，牵制控制是大家较为熟悉的，其目标在于控制复杂网络到某个同步态。有关牵制控制的研究已经相当可观，在此不再赘述。最近，文献[28]研究了对复杂网络的完全能控性，即在有限时间内将网络节点的状态从任意初态控制到任意终态(不必是一致状态或同步态)。他们发现需要直接控制的驱动节点与图论中的最大匹配存在着等价关系，并解析得到了使一个具有泊松或幂律度分布的随机化网络完全结构能控所需的最少的驱动节点的数目。在此基础上，文献[29]提出了对网络结构进行微扰以减少所需的驱动节点的数目的方法；文献[30]则运用点边互换的思想研究了对网络的边的状态进行控制的问题，其结论如果从网络的点边对偶性的角度来看是很明了的。当谈及控制时，我们除了关心一个网络能否被控制，同时也需要思考这么个无法回避的问题：为了控制一个网络需要付出多大的代价？实际上，在网络节点的整个状态空间中，一些状态容易被控制而另一些则较难。这就好比距离您住处十公里远的圆周上，有些地方可经笔直通畅的大道很便捷地到达，而有些则可能需要在颠簸崎岖的小径上蜿蜒前行。出于这种考虑，文献[31]研究了控制复杂网络所需要付出的能量代价的上界和下界，并
指出了控制的难易程度与网络结构的对等性之间的关系。
控制理论尤其是线性系统控制是一个历史悠久且较为成熟的领域，这为复杂网络的控制提供了一些基本的思想和方法。然而，当考虑对一个复杂网络系统进行控制时，我们的兴趣主要在于揭示网络结构与控制之间的关系。如前文中提到的完全控制一个网络最少需要直接控制哪些节点，哪些网络需要的驱动节点较少、付出的能量代价较低，如何对网络结构进行微扰从而降低驱动节点的数目等等都属于这个范畴。这些研究中的一些结果可以较为方便地推广到含权、时变、延时的网络上。当然，也得清晰地看到，这仅限于理想的线性情况(包括节点动力学和节点之间的耦合关系)。在这方面，一个很有意义但尚未被解决的问题是：对于一个给定的网络，如何选择驱动节点使得控制的能量代价最低？
稍往远一点看，控制复杂网络的最终目标是对网络上的各类动力学过程进行控制，包括信息或疾病的扩散、耦合个体的集群行为、通信或交通网络的拥塞、网络博弈的策略演化、基因网络对应的细胞分裂[32]等。在处理这些问题时，我们将无可避免地涉及到非线性的情况。而对一般的耦合非线性系统进行完全控制是非常困难甚至是不可能的。为此，大体上有两种思路可供参考。其一是将复杂网络控制到某个有实际意义的状态区域，而不必是整个状态空间[33]。例如，牵制控制是将网络控制到某个同步态，这样处理起来会方便很多。其二是考虑控制网络系统中的某个关键的参量，例如网络扩散的传播阈值、网络集群的耦合阈值等。如果能够在控制论的框架下，通过输入外界的干扰信号使得网络能够容忍的阈值得以提高或者降低，那将是非常有现实意义的 工作。
总而言之，尽管通往复杂网络控制的道路蜿蜒盘亘，但从最近发表的相关论文可以看出“控制”正成为重要的关键词、正激起人们极大的研究兴趣和热情。期待诸位，站在建模、分析和预测等前期工作的基石上，迈入“控制”——网络科学研究的下一站的核心领域。
参 考 文 献
[1] LU L, MEDO M, YEUNG C H, et al. Recommender systems[J]. Phys Rep, 2012, 519(1): 1-49.
[2] HOLME P, SARAMAKI J. Temporal Networks[J]. Phys Rep, 2012, 519(3): 97-125. [3] VAIDYA N, MICHAEL M L, CHEN I A ,et al. Spontaneous network formation among cooperative RNA replicators[J]. Nature, 2012(491): 72-77.
[4] APICELLA C L, MARLOWE F W, FOWLER J H, et al. Social networks and cooperation in hunter-gatherers[J]. Nature, 2012, 481(7382): 497-501.
[5] RAND D G, ARBESMAN S, CHRISTAKIS N A. Dynamic social networks promote cooperation in experiments with humans[J]. Proc Natl Acad Sci USA, 2011, 108(48): 19193- 19198.
[6] WANG J, SURI S, WATTS D J. Cooperation and assortativity with dynamic partner updating[J]. Proc Natl Acad Sci USA, 2012, 109(36): 14363-14368.
[7] GRACIA-LAZARO C, FERRER A, RUIZ G, et al. Heterogeneous networks do not promote cooperation when humans play a Prisoner’s Dilemma[J]. Proc Natl Acad Sci USA, 2012, 109(32): 12922-12926.
[8] LEE S, HOLME P, WU Z-X. Emergent hierarchical structures in multiadaptive games[J]. Phys Rev Lett, 2011(106): 028702.
[9] SANTOS F C, PACHECO J M. Risk of collective failure provides an escape from the tragedy of the commons[J]. Proc Natl Acad Sci USA, 2011, 108(26): 10421-10425. [10] GAO J-X, BULDYREV S V, STANLEY H E, et al. Networks formed from interdependent networks[J]. Nature Phys, 2012, 8(1): 40-48. [11] GOLTSEV A V, DOROGOVTSEV S N, OLIVEIRA J G, et
al. Localization and spreading of diseases in complex networks[J]. Phys Rev Lett, 2012, 109(12): 128702.
[12] CASTELLANO C, PASTOR-SATORRAS R. Competing
activation mechanisms in epidemics on networks[J]. Sci Rep, 2012, 2(4): 371.
[13] KITSAK M, GALLOS L K, HAVLIN S, et al.
Identification of influential spreaders in complex networks [J]. Nature Phys, 2010, 6(11): 888-893.
[14] LÜ L, ZHANG Y-C, YEUNG C H, et al. Leaders in social
networks, the delicious case[J]. PLoS ONE, 2011, 6(6): e21202.
[15] GHOSHAL G, BARABÁSI A-L. Ranking stability and
super-stable nodes in complex networks[J]. Nature
Commun, 2011, 2(7): 394.
[16] SIMINI F, GONZÁLEZ M C, MARITAN A, et al. A
universal model for mobility and migration patterns[J]. Nature, 2012, 484(7392): 96-100.
[17] SAHNEH F D, CHOWDHURY F N, SCOGLIO C M. On
the existence of a threshold for preventive behavioral responses to suppress epidemic spreading[J]. Sci Rep, 2012, 2(9): 632.
[18] CENTOLA D. The spread of behavior in an online social
network experiment[J]. Science, 2010, 329(5996): 1194-1197. [19] LÜ L, CHEN D-B, ZHOU T. The small world yields the
most effective information spreading[J]. New J Phy, 2011, 13(12): 123005.
[20] PEREZ-RECHE F J, LUDLAM J J, TARASKIN S N, et al,
Synergy in spreading processes: from exploitative to explorative foraging strategies[J]. Phys Rev Lett, 2011, 106(21): 218701.
[21] CENTOLA D. An experimental study of homophily in the
adoption of health behavior[J]. Science, 2011, 334(6060): 1269-1272.
[22] UGANDER J, BACKSTROM L, MARLOW C, et al.
Structural diversity in social contagion[J]. Proc Natl Acad Sci USA, 2012, 109(16): 5962-5966.
[23] ARAL S, WALKER D. Identifying influential and
susceptible members of social networks[J]. Science, 2012, 337(6092): 337-341.
[24] BOND R M, FARISS C J, JONES J J, et al. A 61-
million-person experiment in social influence and political mobilization[J]. Nature, 2012, 489(7415): 295- 298.
[25] LEWIS K, GONZALEZ M, KAUFMAN J. Social
selection and peer influence in an online social network[J]. Proc Natl Acad Sci USA, 2012, 109(1): 68-72.
[26] PINTO P C, THIRAN P, VETTERLI M. Locating the
source of diffusion in large-scale networks[J]. Phys Rev Lett, 2012, 109(6): 068702. [27] VALENTE T W. Network Interventions[J]. Science, 2012,
337(6090): 49-53. [28] LIU Y-Y, SLOTINE J-J, BARABÁSI A.-L. Controllability
of complex networks[J]. Nature, 2011, 473(7346): 167- 173. [29] WANG W X, NI X, LAI Y-C, et al. Optimizing
controllability of complex networks by minimum structural perturbations[J]. Phys Rev E, 2012, 85(2): 026115. [30] NEPUSZ T, VICSEK T. Controlling edge dynamics in
complex networks[J]. Nature Phys, 2012, 8(7): 568-573. [31] YAN G, REN J, LAI Y-C, et al. Controlling complex
networks: how much energy is needed?[J]. Phys Rev Lett, 2012, 108(21): 218703.
[32] RAJAPAKSE I, GROUDINEAND M, MESBAHI M.
Dynamics and control of state-dependent networks for probing genomic organization[J]. Proc Natl Acad Sci USA, 2011, 108(42): 17257-17262.
[33] MÜLLER F-J, SCHUPPERT A. Few inputs can reprogram
biological networks[J]. Nature, 2011, 478(7369): E4.
编 辑 蒋 晓
第41卷 第6期 电 子 科 技 大 学 学 报 Vol.41 No.6 复杂网络2012年度盘点
荣智海1，唐 明2，汪小帆3，吴枝喜4，严 钢5，周 涛2
(1. 东华大学信息科学与技术学院 上海 松江区 201620; 2. 电子科技大学互联网科学中心 成都 611731;
3. 上海交通大学电子信息与电气工程学院 上海 闵行区 200240; 4. 兰州大学计算物理与复杂系统研究所 兰州 730000;
5. 新加坡国立大学淡马锡实验室 新加坡 117411)
doi:10.3969/j.issn.1001-0548.2012.06.001
复杂网络是复杂性科学研究中受到最广泛关注的方向，在信息科学、物理学、生物学、数学乃至社会学、管理学等领域都产生了重大贡献和持续影响。十几年来，复杂网络的研究成果一直是《自然》、《科学》、《美国科学院院刊》等综合类顶级学术期刊的宠儿，每年均有数10篇相关论文发表。据不完全统计，仅在Review of Modern Physics、Physics Reports、Advance in Physics和SIAM Reviews这4个顶尖的综述性期刊就发表了17篇复杂网络的综述论文，今年又在Physics Reports上连续刊出两篇[1-2]。
于此同时，我们也注意到，在十几年的发展中，复杂网络研究的重点和焦点已经发生了较大的变化。可喜的是，以王文旭、严钢、吕琳媛、吴枝喜等人为代表的一群青年科学家，已经融入甚至影响着国际相关研究前沿发展的潮流。遗憾的是，国内相当一部分学者，还沉浸在老问题和老思路上，对于最激动人心的进展缺乏深入、完整的认识。基于这个现状，我们决定每年推出一期年末盘点栏目，邀请国内有代表性的青年科学家，主要就最近1~2年的国际重要进展进行介绍和评述。这个栏目从复杂网络起，将来也可能不限于复杂网络，而渗透进复杂性科学的其他方向，
譬如典型复杂系统分析、金融复杂性研究、群集动力学与社会计算、人类动力学分析等等。
本文重点关注网络功能方面的研究，邀请了荣智海、唐明、吴枝喜、严钢四位青年科学家就博弈、传播和控制展开介绍。希望各位读者能够通过阅读本文获得对复杂网络部分研究焦点的认识，开拓视野！
1 网络博弈：演化与合作涌现
合作现象在自然界和人类社会中普遍存在。最近一项研究表明化学物质转变为生命物质是通过分子间的协作完成的。自私的RNA通过自我复制只能形成短链，而文献[3]发现合适的策略可以促使不同的RNA自组织装配，搭建成合作的超循环回路，形成复杂的生命分子。
哈佛大学研究人员的实证性研究揭示了坦桑尼亚北部哈扎猎人(Hadza)之间的社会合作网络[4]。他们访问了17个营地的205名成年哈扎人(男性102名，女性103名)，在每个营地进行一轮多人公共品博弈，合作者(cooperator, C)的投入会使所有人受益，而背叛者(defector, D)会不劳而获。虽然背叛行为使得自私的人收益最大化，然而哈扎人之间更倾向于合作利他，且所形成的社会合作关
收稿日期：2012 11 07
基金项目：国家自然科学基金(61004098, 11005051, 11135001, 61273223, 11105025)；国家973项目(NCET-09-0317).
作者说明：本文由汪小帆、周涛筹划、组稿、修改、整理并联合撰写第一节，由荣智海和吴枝喜联系撰写第二节初稿，由唐明撰写第三节初稿，由严钢撰写第四节初稿。作者排名按照汉语拼音顺序，不分先后。
系具有现代社会网络的特征，如高聚类、同质性和互惠性等。这表明社会网络的一些结构特征以及合作机制可能在人类早期就已经形成。
由此可见，理解合作行为在个体间的涌现机制有助于人们认识从生命起源到人类社会组织等一系列重要课题。过去二十多年的理论研究表明网络互惠是一种重要的合作涌现机制，在网络上合作者通过与其他的合作邻居互助形成合作簇，可以有效抵御背叛者的入侵，从而促进合作行为的涌现。
最近一系列实证性研究试图揭示网络互惠是否在人类博弈中存在。研究人员基于著名的两人囚徒困境博弈，召集了近800名志愿者进行真人网络博弈实验[5]。他们将约20名志愿者分为一组，配对进行重复博弈，并考虑了随机交互、固定交互和动态演化三种作用方式。在随机交互中，每轮博弈结束后，个体以一定概率随机更新交互对象。在固定交互中，初始时刻群体随机连接，其后则保持交互对象不变。对于动态演化博弈，则在每轮博弈后，研究者随机选择k%对志愿者进行如下操作：对每对志愿者A和B，随机选择A并告知对手B之前的行为，若两者存在联系，则询问A是否要去掉其与B的连接，否则询问A是否愿意与B建立关系。通过考虑网络快速(k=30)和缓慢(k=10)演化的情况，发现合作行为只有在网络快速演化时能够维持。对其他情况，合作行为则随着重复博弈的递进呈明显下降趋势。此外，他们观察到快速动态演化的博弈网络的度分布更宽，C-C关系比C-D关系更稳固，D-D最脆弱，合作者因“得道”而容易吸引朋友，背叛者则因“失道”容易失去朋友。有意思的是，失去了朋友的背叛者接下来会倾向于合作。因此，连/断边可以看作奖励/惩罚措施，促使合作行为稳定维持于群体中。文献[6]做了类似的研究，也发现结构动态演化可以促进
合作和同配特性的涌现。他们将每组24名志愿者构成随机正则网络和六派系网络，采取12轮重复囚徒困境博弈，与文献[5]不同，在网络演化时，他们允许一方提出建立或者删除连接的请求，对手可以接受或拒绝该请求，若拒绝则两者保持原交互关系。通过引入该动态演化机制，在大量加减边时群体合作水平更高，而随着重复博弈接近尾声合作水平会递减。同时，他们发现C-C很容易建立联系，C-D间的联系最难建立，因此同配特性在合作者间容易涌现。
最近西班牙学者研究了更大规模网络上的人类博弈实验[7]。他们召集了1 200余名志愿者，分为两组放在平均度为4的规则格子和度分布异质的网络上。在网络固定和随机交互(每轮博弈后随机选择相同数目的邻居)的情况下进行约50轮的重复囚徒困境博弈，发现合作水平随着时间演化而递减，且不同结构的网络上合作水平相似，这与前期理论研究得到的异质网络结构促进合作的结论相悖。同时，他们也观察到个体合作倾向性与邻居合作数目(而不是邻居收益)相关。然而，需要指出的是，他们的研究没有考虑个体自愿连/断边的情况。因此，结合文献[5-6]的研究，笔者认为赋予个体合适的邻居选择机制，异质网络不促进合作的结论值得商榷，不同动态网络结构的作用会凸现。
在大多数研究中，博弈的收益矩阵往往是固定的，但实际系统的收益大小往往由组成系统的个体的集体状态决定(合作者密度越大，系统的效率越高)。文献[8]研究了一个多重适应的动态网络演化博弈模型：首先，囚徒困境博弈中个体采取背叛策略的诱惑量随系统中合作者的比例动态变化；其次，个体具有适应性，每轮博弈过后可以变更一定比例的博弈对象，在选择新交互对象时，个体更倾向和收益高的个体建立关系。在适当的
参数区间，研究发现系统能够演化到全合作者状态。此时个体间交互的连接度分布服从幂律形式，个体的聚类系数与其连接度成反比，即博弈动力学的多尺度演化导致了层次结构的涌现。
控制气候变暖可能是当前人类面临的最重要的公共资源博弈。只有各国投入足够的资金进行预防，才能有效阻止气候崩溃，否则人类有满盘皆输的可能。但困境在于虽然各国已经充分意识到维护气候这一公共资源的重要性，但仍然产生了哥本哈根的悲剧。研究人员通过改进公共品博弈模型，引入了集体投资阈值，如果参与者的投资低于该阈值，则所有人会冒一无所有的风险。通过演化博弈动力学分析，表明投资失败风险的引入可以让参与者意识到为了集体利益必须有所牺牲，从而与他人合作。研究发现无标度网络上参与博弈的群体规模多样性有利于全局协作，容易达到抑制气候变暖的目标[9]。
2 网络传播：从分析到干预
网络传播动力学研究已经发展了一系列重要的模型和理论用以描述各式各样的传播现象，例如革新扩散(innovation diffusion)、潮流发展(fad development)、疾病传播(epidemic spreading)、故障蔓延(failure propagation)等，探讨了许多重要因素(例如网络结构、连接权重和空间距离等)对于传播过程的影响，特别关注了许多真实传播过程的预测和控制研究。这些研究也为复杂系统中其他一些动力学行为(例如网络同步和网络博弈等)的研究提供了新的思路和方法。在过去的两年中，一些学者开始关注多层耦合网络的研究，而其上的传播研究将是一项极具挑战性的全新课题。最近，网络舆情、行为等传播研究越来越受到人们的关注，已成为当前最为热点的研究课题之一。更为重要的是，传播路径的还原和网络干预(例如
网络控制)可能成为未来十年之中最为热门的课题之一。以上研究热点可笼统地归为网络结构、行为规律、社会传播、路径还原和网络干预五个方面。
1) 网络结构。主要有多层/关系耦合网络传播动力学[10]、中尺度结构在传播过程中的作用[11-12]和节点影响力排序方法与稳定性分析[13-14]三个研究热点。对于多层/关系耦合网络，在大量实证的基础上，理解层间不同耦合关系(如依存、协作或抑制等作用)和耦合模式(如部分、一一或关联等匹配)对于单个或多个传播动力学行为的影响应是其首要任务，而关键节点与路径的定义及其在传播过程中的重要性等问题是其中的难点之一。考虑到真实多层耦合网络的复杂性和多样性，其上的动力学现象将会异常丰富多彩，可以预见的是围绕这一主题近期将会涌现大量的新工作。在网络的中尺度结构上，最近一些研究显示病毒可以被局限于那些高权重的边和节点[11]或是核心层[12]周围。非常自然地，其他一些中尺度结构如社区、派系、模体等在传播演化预测与防控中的作用如何将是值得深入研究的问题。对于节点影响力排序问题，自文献[13]利用K-CORE层次分解获得了比度更为准确的影响力指标之后，短短两年内其Google Scholar的引用已高达120余次，可谓当前炙手可热的研究课题。文献[14]改进了经典PageRank算法，提出了一种名为LeaderRank的快速算法，能够等到超大规模社会网络中影响力高端的排序。以这些人为源头进行信息传播，速度会比以PageRank或者朋友数目为标准确定的源头快很多。虽然几乎所有相关研究都致力于寻求一种快速而准确的普适排序方法，但是可能的关键问题是在网络结构和传播动力学确定的情况下给出一个快速而较为准确的排序方法，由此可以继续拓展和深化的空间还非常大。此外，节点排序
在噪声干扰下(如网络结构和动力学行为的变化)的稳定性分析也是一个值得关注的重要问题[15]。
2) 行为规律。自从2005年人类行为动力学研究兴起以来，基于人类行为规律的传播动力学研究便随之开展起来，主要集中于个体行为的接触时间[2]、空间迁移[16]和行为反应[17]等对于传播过程的影响。就目前研究现状来看，这类研究非常容易造成一些令人困惑的难题，根本原因在于个体行为动力学规律的多样性。例如大量实证研究表明，人类的行为在时间上具有阵发性，存在短暂的紧密爆发和长时间的静默，不能用传统的泊松过程刻画。目前的工作主要基于真实数据集展开研究，发现在有些情况下人类的阵发特性减慢了传播动力学过程，而在有些情况下却加快了传播动力学过程，急需从本质上探究人类的各种阵发特性(如发送时延和响应时延等)对传播动力学的影响。对于以上三个问题的研究，最近都有一些重要的实证和理论工作发表，例如时变网络[2]
和人口迁移模式
[16]
的研究，鉴于人类行为动力学
研究仍是当前研究热点之一，基于人类行为规律的传播动力学研究将会具有较为持久的生命力。
3) 社会传播。网络传播动力学研究不仅仅局限于流行病传播，还关注其他一系列的社会传播现象，例如谣言、时尚、政治意见、新技术的采纳、金融决策以及健康行为等等。对于传统的病毒传播，一个易感个体被感染的概率仅依赖于与其接触的那个感染邻居，而社会感染概率还取决于其他邻居的当前或历史状态[18-22]。这种感染的差异可能产生一些反直观的有趣现象，例如由于协同加强效应的存在，规则网络上的谣言(或行为)传播将会明显快于随机网络上的情况[18]。最近几个月，社会传播的实证工作越来越多，档次也非常之高，大都发表于Science、Nature和PNAS等顶级期刊上[23-25]。由此可见，目前社会传播研究是
当之无愧的热点之中的热点。除了必要的在线实证研究之外，抓住关键的传播机制，构建合理的传播模型用以描述这些有趣的传播现象也是当前亟需开展的工作。
4) 路径还原。相对于传播路径的预测，路径还原应是一个相反的问题，早先一直被计算机科学家和流行病学家所关注，而最近的一篇物理评论快报开始了关于扩散源点的定位研究[26]。毫无疑问地，传播路径的还原研究有助于传播过程的控制，其应用也非常广泛，例如舆情和疫情的防控。然而，这一研究在很大程度上受限于传播机理研究的进展，单单凭借利用数学统计方法和计算机技术很难发展出一套行之有效的还原方法。因而，如同社区检测研究一样，这类问题缺少一些物理的机制，更侧重于数学方法和实际应用，可能将成为数学家和计算机科学家所偏爱的研究课题，此时进入正当时！
5) 网络干预。网络干预是有目的的运用社会网络或社会网络数据来产生社会影响、加速行为的改变、改进性能，从而达到对个人、社团、组织以及群体的影响[27]。作为复杂网络研究的终极目标，这一研究课题自然是非常重要的。文献[27]描述了四种网络干预的策略，每种策略又有多种替代策略。许多策略综合了不同的数学算法。因此，研究者对干预可以有许多选择，选择合适的网络干预取决于可用的网络数据、行为的特征、已有的流行程度和项目的社会背景。鉴于网络干预涉及范围之广泛、面临情况之复杂以及可选策略之多样，其研究必将博大精深，源远流长。文献[28]对于有向网络的控制研究更是激起了研究学者们对于这类问题的极大兴趣。对于这类研究，虽然控制理论的应用当然地成为重头戏，但是如何将网络动力学研究融入其中，应该是控制理论
学家和物理学家们共同面临的一大挑战。下一节将更深入剖析网络控制的进展和问题。
3 控制复杂网络：面朝下一站，蜿
蜒前行
回顾网络科学过去十多年的发展，人们的主要兴趣和精力大多放在对网络自身的结构和网络上的动力学过程进行建模、分析乃至预测；朝前看，我们将触及复杂网络研究的下一篇章中的核心内容，即，对复杂网络系统进行定性调控乃至精确控制。
在这方面，牵制控制是大家较为熟悉的，其目标在于控制复杂网络到某个同步态。有关牵制控制的研究已经相当可观，在此不再赘述。最近，文献[28]研究了对复杂网络的完全能控性，即在有限时间内将网络节点的状态从任意初态控制到任意终态(不必是一致状态或同步态)。他们发现需要直接控制的驱动节点与图论中的最大匹配存在着等价关系，并解析得到了使一个具有泊松或幂律度分布的随机化网络完全结构能控所需的最少的驱动节点的数目。在此基础上，文献[29]提出了对网络结构进行微扰以减少所需的驱动节点的数目的方法；文献[30]则运用点边互换的思想研究了对网络的边的状态进行控制的问题，其结论如果从网络的点边对偶性的角度来看是很明了的。当谈及控制时，我们除了关心一个网络能否被控制，同时也需要思考这么个无法回避的问题：为了控制一个网络需要付出多大的代价？实际上，在网络节点的整个状态空间中，一些状态容易被控制而另一些则较难。这就好比距离您住处十公里远的圆周上，有些地方可经笔直通畅的大道很便捷地到达，而有些则可能需要在颠簸崎岖的小径上蜿蜒前行。出于这种考虑，文献[31]研究了控制复杂网络所需要付出的能量代价的上界和下界，并
指出了控制的难易程度与网络结构的对等性之间的关系。
控制理论尤其是线性系统控制是一个历史悠久且较为成熟的领域，这为复杂网络的控制提供了一些基本的思想和方法。然而，当考虑对一个复杂网络系统进行控制时，我们的兴趣主要在于揭示网络结构与控制之间的关系。如前文中提到的完全控制一个网络最少需要直接控制哪些节点，哪些网络需要的驱动节点较少、付出的能量代价较低，如何对网络结构进行微扰从而降低驱动节点的数目等等都属于这个范畴。这些研究中的一些结果可以较为方便地推广到含权、时变、延时的网络上。当然，也得清晰地看到，这仅限于理想的线性情况(包括节点动力学和节点之间的耦合关系)。在这方面，一个很有意义但尚未被解决的问题是：对于一个给定的网络，如何选择驱动节点使得控制的能量代价最低？
稍往远一点看，控制复杂网络的最终目标是对网络上的各类动力学过程进行控制，包括信息或疾病的扩散、耦合个体的集群行为、通信或交通网络的拥塞、网络博弈的策略演化、基因网络对应的细胞分裂[32]等。在处理这些问题时，我们将无可避免地涉及到非线性的情况。而对一般的耦合非线性系统进行完全控制是非常困难甚至是不可能的。为此，大体上有两种思路可供参考。其一是将复杂网络控制到某个有实际意义的状态区域，而不必是整个状态空间[33]。例如，牵制控制是将网络控制到某个同步态，这样处理起来会方便很多。其二是考虑控制网络系统中的某个关键的参量，例如网络扩散的传播阈值、网络集群的耦合阈值等。如果能够在控制论的框架下，通过输入外界的干扰信号使得网络能够容忍的阈值得以提高或者降低，那将是非常有现实意义的 工作。
总而言之，尽管通往复杂网络控制的道路蜿蜒盘亘，但从最近发表的相关论文可以看出“控制”正成为重要的关键词、正激起人们极大的研究兴趣和热情。期待诸位，站在建模、分析和预测等前期工作的基石上，迈入“控制”——网络科学研究的下一站的核心领域。
参 考 文 献
[1] LU L, MEDO M, YEUNG C H, et al. Recommender systems[J]. Phys Rep, 2012, 519(1): 1-49.
[2] HOLME P, SARAMAKI J. Temporal Networks[J]. Phys Rep, 2012, 519(3): 97-125. [3] VAIDYA N, MICHAEL M L, CHEN I A ,et al. Spontaneous network formation among cooperative RNA replicators[J]. Nature, 2012(491): 72-77.
[4] APICELLA C L, MARLOWE F W, FOWLER J H, et al. Social networks and cooperation in hunter-gatherers[J]. Nature, 2012, 481(7382): 497-501.
[5] RAND D G, ARBESMAN S, CHRISTAKIS N A. Dynamic social networks promote cooperation in experiments with humans[J]. Proc Natl Acad Sci USA, 2011, 108(48): 19193- 19198.
[6] WANG J, SURI S, WATTS D J. Cooperation and assortativity with dynamic partner updating[J]. Proc Natl Acad Sci USA, 2012, 109(36): 14363-14368.
[7] GRACIA-LAZARO C, FERRER A, RUIZ G, et al. Heterogeneous networks do not promote cooperation when humans play a Prisoner’s Dilemma[J]. Proc Natl Acad Sci USA, 2012, 109(32): 12922-12926.
[8] LEE S, HOLME P, WU Z-X. Emergent hierarchical structures in multiadaptive games[J]. Phys Rev Lett, 2011(106): 028702.
[9] SANTOS F C, PACHECO J M. Risk of collective failure provides an escape from the tragedy of the commons[J]. Proc Natl Acad Sci USA, 2011, 108(26): 10421-10425. [10] GAO J-X, BULDYREV S V, STANLEY H E, et al. Networks formed from interdependent networks[J]. Nature Phys, 2012, 8(1): 40-48. [11] GOLTSEV A V, DOROGOVTSEV S N, OLIVEIRA J G, et
al. Localization and spreading of diseases in complex networks[J]. Phys Rev Lett, 2012, 109(12): 128702.
[12] CASTELLANO C, PASTOR-SATORRAS R. Competing
activation mechanisms in epidemics on networks[J]. Sci Rep, 2012, 2(4): 371.
[13] KITSAK M, GALLOS L K, HAVLIN S, et al.
Identification of influential spreaders in complex networks [J]. Nature Phys, 2010, 6(11): 888-893.
[14] LÜ L, ZHANG Y-C, YEUNG C H, et al. Leaders in social
networks, the delicious case[J]. PLoS ONE, 2011, 6(6): e21202.
[15] GHOSHAL G, BARABÁSI A-L. Ranking stability and
super-stable nodes in complex networks[J]. Nature
Commun, 2011, 2(7): 394.
[16] SIMINI F, GONZÁLEZ M C, MARITAN A, et al. A
universal model for mobility and migration patterns[J]. Nature, 2012, 484(7392): 96-100.
[17] SAHNEH F D, CHOWDHURY F N, SCOGLIO C M. On
the existence of a threshold for preventive behavioral responses to suppress epidemic spreading[J]. Sci Rep, 2012, 2(9): 632.
[18] CENTOLA D. The spread of behavior in an online social
network experiment[J]. Science, 2010, 329(5996): 1194-1197. [19] LÜ L, CHEN D-B, ZHOU T. The small world yields the
most effective information spreading[J]. New J Phy, 2011, 13(12): 123005.
[20] PEREZ-RECHE F J, LUDLAM J J, TARASKIN S N, et al,
Synergy in spreading processes: from exploitative to explorative foraging strategies[J]. Phys Rev Lett, 2011, 106(21): 218701.
[21] CENTOLA D. An experimental study of homophily in the
adoption of health behavior[J]. Science, 2011, 334(6060): 1269-1272.
[22] UGANDER J, BACKSTROM L, MARLOW C, et al.
Structural diversity in social contagion[J]. Proc Natl Acad Sci USA, 2012, 109(16): 5962-5966.
[23] ARAL S, WALKER D. Identifying influential and
susceptible members of social networks[J]. Science, 2012, 337(6092): 337-341.
[24] BOND R M, FARISS C J, JONES J J, et al. A 61-
million-person experiment in social influence and political mobilization[J]. Nature, 2012, 489(7415): 295- 298.
[25] LEWIS K, GONZALEZ M, KAUFMAN J. Social
selection and peer influence in an online social network[J]. Proc Natl Acad Sci USA, 2012, 109(1): 68-72.
[26] PINTO P C, THIRAN P, VETTERLI M. Locating the
source of diffusion in large-scale networks[J]. Phys Rev Lett, 2012, 109(6): 068702. [27] VALENTE T W. Network Interventions[J]. Science, 2012,
337(6090): 49-53. [28] LIU Y-Y, SLOTINE J-J, BARABÁSI A.-L. Controllability
of complex networks[J]. Nature, 2011, 473(7346): 167- 173. [29] WANG W X, NI X, LAI Y-C, et al. Optimizing
controllability of complex networks by minimum structural perturbations[J]. Phys Rev E, 2012, 85(2): 026115. [30] NEPUSZ T, VICSEK T. Controlling edge dynamics in
complex networks[J]. Nature Phys, 2012, 8(7): 568-573. [31] YAN G, REN J, LAI Y-C, et al. Controlling complex
networks: how much energy is needed?[J]. Phys Rev Lett, 2012, 108(21): 218703.
[32] RAJAPAKSE I, GROUDINEAND M, MESBAHI M.
Dynamics and control of state-dependent networks for probing genomic organization[J]. Proc Natl Acad Sci USA, 2011, 108(42): 17257-17262.
[33] MÜLLER F-J, SCHUPPERT A. Few inputs can reprogram
biological networks[J]. Nature, 2011, 478(7369): E4.
编 辑 蒋 晓