1、n二十一世纪涌现的新现象互联网是怎样“链”接的？从一个页面到另一个页面，平均需要点击多少次鼠标？美国航空网美国航空网城市公共交通网城市公共交通网为什么两者结构差异如此之大？这种差异是必然还是偶然的？城市交通涌堵的原因是什么？非典发现在广州，为什么却 在北京爆发呢？传染病是怎样扩散和消失的？计算机病毒是怎样传播的？为什么“好事不出门，坏事行千里”呢？互联网互联网病毒传播网病毒传播网神经网络生态网络电力网络电信网络社交网络航空网络Facebook全球友谊图n二十世纪科学研究方法：分析、还原论；当分析为主要的研究方法时，人类关注如何将系统“分析”、“分解”，揭开系统的细部，了解是什么元素或部件组成了
2、系统；忽视或破坏了这些元素是如何组合成系统的。n二十一世纪（二十世纪末），系统成为主要的研究对象，整合成为主要方法；整合的方法在于了解细部以后，研究“如何组合”的问题，这导致复杂网络结构的研究；如：普列高津的耗散结构理论、哈肯的协同学、混沌和复杂系统理论、系统生物学、n复杂系统与复杂网络的概念 系统：集合（具体元素）+结构+功能系统的结构是什么？n一切系统的基础结构都是网络；n一切系统的核心结构都是逻辑网络；n复杂系统的结构就是复杂网络。复杂网络是构成复杂系统的基本结构，每个复杂系统都可以看作是单元或个体之间的相互作用网络；复杂网络在刻画复杂性方面的重要性是由于结构决定功能的；复杂网络是研究复
3、杂系统的一种角度和方法，它关注系统中因子相互关联作用的拓扑结构，是理解复杂系统性质和功能的基础。具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络称为复杂网络。钱学森n1)开放性与环境和其它系统进行相互作用，交换物质、能量、信息，保持和发展系统内部的有序性与结构稳定性；在这种交换中，系统经历着从低级向高级、从简单到复杂、从无序向有序的不断优化的动态发展过程；虽然开放性是所有真实系统的基本属性，但这里的开放非指一般意义上的相互作用与交流，而开放的度量、性质、强度对复杂系统的性态、演化具有决定性的意义。例：人、城市网络簇。n2)涌现性即内部元素通过非线性相互作用，在宏观层次上产生出新
4、的、元素不具有的整体属性；虽然涌现同样是所有系统都具有的，但这里涌现意味着新的整体属性的产生。n“整体大于部分之和”，如：大脑的神经网络系统n3)演化性（不可逆性)即通过与所在环境中的其它系统的相互作用和内部的自组织，使系统发展到新的阶段，表现出阶段性、临界性，完成系统演化的生命周期。n社会网络中的人、生物群体的自组织系统（鸟群）n4）复杂性结构复杂性：表现为多元性，非对称性，非均匀性，非线性n分岔(Bifurcation)、混沌(Chaos)、分形Fractal；行为复杂性：表现为学习，自适应性，混沌同步，混沌边沿，随机性等等；认识复杂性：又称为主观复杂性，它表现为不确定性，描述复杂性与计算
5、复杂性等等。n例：神经网络中的突触有强有弱，可抑制也可兴奋网络复杂性：即系统内部和系统之间的相互作用可以看成由节点、边（连接）构成的体系，出现网络复杂性、小世界特征与无标度特征等。n（1）结构复杂性网络连接结构错综复杂、极其混乱，同时又蕴含着丰富的结构：社区、基序、聚集性、生成规律性等等，而且网络连接结构可能是随时间变化的。包括：静态结构的复杂性和结构动态演化的复杂性。例如：互联网上每天都不停地有页面和链接的产生和删除。n 例：神经系统由神经元互连形成，连接以“突触连接结构”实现，突触有强弱、兴奋与抑制、不同的神经递质；连接不断改变，形成连接结构变化。（重边，加权等）n（2）节点复杂性节点的独
6、立或固有特性n网络中的节点可能是具有分岔和混沌等复杂非线性行为的动力系统；n例如：基因网络中每个节点都具有复杂的时间演化行为；一个网络中可能存在多种不同类型的节点，比如控制哺乳动物中细胞分裂的生化网络就包含各种各样的基质和酶。关联引发的节点特性n当关联失去时这类特性会在节点处消失或改变；n例如：耦合神经元重复地被同时激活，那么它们之间的连接就会加强，这被认为是记忆和学习的基础。n（3）复杂网络之间相互影响的复杂性实际的复杂网络会受到各种各样因素的影响和作用。例如：电力网络故障会导致Internet网速变慢，运输系统失控等一系列不同网络间的连锁反应。n（4）网络分层结构的复杂性行政管理网络是具有
7、层结构的，多数网络都有节点的分层结构，只是在许多网络中没有意识到是一种造成复杂性的重要结构。n复杂网络是二十一世纪科学研究的思想和理念，它启发我们用什么观点理解这个世界：整个世界以及组成世界的任何细部都是由网络及其变化形成的；n复杂网络也是研究复杂系统的一种技术和方法，它关注系统中个体相互作用的拓扑结构，是理解复杂系统性质和功能的基本方法。n格尼斯堡七桥问题Euler（17071783），瑞士数学家，图论之父一笔画问题 n随机图理论20世纪60年代，由两位匈牙利数学家Erds和Rnyi建立的随机图理论（random graph theory）被公认为是在数学上开创了复杂网络理论的系统性研究。E
8、rds和Rnyi的最重要的发现：ER随机图的许多重要性质都是突然涌现的。即：对于任一给定的概率p，要么几乎每一个图都具有某个性质Q（比如说，连通性），要么几乎每一个图都不具有该性质。在20世纪的后40年中，随机图理论一直是研究复杂网络的基本理论n大多数人都过这样的经历：碰到一个陌生人，同他聊了一会后发现你认识的某个人居然他也认识，然后一起发出“这个世界真小”的感叹；n那么对于世界上任意两个人来说，借助第三者、第四者这样的间接关系来建立起他们两人的联系平均来说最少要通过多少人呢？哈佛大学美国社会心理学家斯坦利米尔格伦(Stanley Milgram)在1967年实验后得出结论：中间的联系人平均只
9、需要5个，他把这个结论称为“六度分离”（Six Degrees of Separation）；六度分离：平均只要通过5个人，你就能与世界任何一个角落的任何一个人发生联系。这个结论定量地说明了我们世界的”大小”，或者说人与人关系的紧密程度；六度分离理论一直被作为社会心理学的经典范例之一。n米尔格伦的实验过程：他计划通过人传人的送信方式来统计人与人之间的联系；n首先把信交给志愿者A，告诉他信最终要送给收信人S；n如果他不认识S，那么就送信到某个他认识的人B手里，理由是A认为在他的交集圈里B是最可能认识S的；n但是如果B也不认识S，那么B同样把信送到他的一个朋友C手中，就这样一步步最后信终于到达S那
10、里；n这样就ABCS连成了一个链；n斯坦利米尔格伦通过对这个链做了统计后做出了六度分离的结论。尽管如此，实际上这个理论并没有得到严格的证实；美国心理学教授朱迪斯克兰菲尔德（Judith Kleinfeld）对米尔格伦最初的实验提出不同意见，因为她发现实验的完成率极低（实际上只有三分之一的信送到了收信人那里）。n截止到最近，世界电影史上共产生了大约23万部电影，78多万名电影演员，Kavin Bacon在许多部电影中饰演小角色；nVirginia 大学的计算机专家Brett Tjaden设计了一个游戏，他声称电影演员Kevin Bacon是电影界的中心，定义了Bacon数：一个演员如果和Kavi
11、n Bacon一起演过电影，那么他（她）的Bacon数就为1；如果他（她）没有和Bacon演过电影，但是和Bacon数为1的演员一起演过电影，那么他的Bacon数就为2；依此类推。n网站http:/www.cs.virginia.edu/oracle/的数据库里总共存有有783,940个世界各地的演员的信息，以及231,088部电影信息；n通过简单地输入演员名字就可以知道这个演员的bacon数；比如输入Stephen Chow（周星驰）就可以得到这样的结果：周星驰在1991年的豪门夜宴(Haomen yeyan)中与洪金宝(Sammo Hung Kam-Bo)合作；而洪金宝又在李小龙的最后一部
12、电影，即1978年的死亡的游戏（Game of Death）中与 Colleen Camp 合作；Colleen Camp 在去年的电影Trapped 中与Kevin Bacon 合作；这样周星驰的Bacon数为3。对78万个演员所做的统计：演员的最大Bacon数仅仅为8，平均Bacon数仅为2.948。nPaul Erdos(1913-1996)：出生于匈牙利的犹太籍数学家，被公认为20世纪最伟大的天才之一；nErdos毕生发表的论文超过1500篇（在数学史上仅次于欧拉），超长的合作者名单，合作者超过450位，若加上别人所做但曾获他关键性提示之论文，则数万篇；n他的研究领域主要是数论和组合数
13、学，但他的论文中涵盖的非常多的学科；nMathematical Reviews 曾把数学划分为大约六十个分支，Erdos的论文涉及到了其中的40%.n定义Erdos数(Erdos number)的定义：Erdos本人之Erdos数为0；任何人若曾与Erdos合写过论文，则其Erdos数为1；任何人若曾与一位Erdos数为l(且不曾与有更少的Erdos数)的人合写过论文，则他的Erdos数为2n几乎每一个当代数学家都有一个有限的Erdos数，而且这个数往往非常小，小得出乎本人的预料；证明Fermat大定理的Andrew Wiles，他的研究方向与Erdos相去甚远，但他的Erdos数只有3，是通
14、过这个途径实现的：Erdos-Andrew Odlyzko-Chris M.Skinner-Andrew Wiles.nFields奖得主的Erdos数都不超过5（只有Cohen和Grothendieck的Erdos数是5）；n Nevanlinna奖得主的Erdos数不超过3（只有Valiant的Erdos数是3）；nWolf数学奖得主的Erdos数不超过6（只有V.I.Arnold是6，且只有Kolmogorov是5）；nSteele奖的终身成就奖得主的Erdos数不超过4；n其他领域的专家：比尔盖兹(Bill Gates)，他的Erdos数是4，通过如下途径实现：Erdos-Pavol
15、Hell-Xiao Tie Deng-Christos H.Papadimitriou-William H.(Bill)Gates；爱因斯坦的Erdos数是2。n两篇开创性的文章可以看作是复杂网络研究新纪元开始的标志：美国康奈尔（Cornell）大学理论和应用力学系的博士生Watts及其导师、非线性动力学专家Strogatz教授于1998年6月在Nature杂志上发表的“小世界”网络的集体动力学（Collective Dynamics of Small-World Networks）；美国Notre Dame大学物理系的Barabsi教授及其博士生Albert于1999年10月在Science
16、杂志上发表的随机网络中标度的涌现（Emergence of Scaling in Random Networks）。n这两篇文章分别揭示了复杂网络的小世界特征和无标度性质，并建立了相应的模型以阐述这些特性的产生机理。n1998，Watts和Strogatz：WS小世界网络 D.J.Watts,and S.H.Strogatz,Nature,393,440-442(1998).n60个节点组成的一个环每个节点与相邻的两个节点相连，计算网络的平均路径长度，即网络中所有节点对之间的路径长度的平均值。规则网络的平均路径长度为15，面对面的两个点之间的信息交流会需要较长时间。n将规则网络中少量与相邻节点
17、连接的边改成长距离连接对图中5%的边（3条）进行重连后得到的网络，重连时3条边的一端被解开，重新连接到一个随机选择的节点上；重连后的网络与原来的规则网络的边数量一样多，但平均路径长度降到了9左右；节点数量越多，这个效应越明显。如果是有1000个节点的规则网络，平均路径长度是250，如果5%的边重连，平均路径长度会降到20。n小世界性一个网络如果只有少量的长程连接，相对于节点数量来说平均路径却很短，则为小世界网络；自然、社会和技术演化产生的许多生物、群体和产品似乎都具有这种结构；这是为什么呢？有人认为至少有两种相互矛盾的选择压力导致了这种结果：n在系统内快速传播信息的需要，以及产生和维持可靠的远
18、程连接的高成本；n小世界网络具有较短的平均路径长度，同时又只需相对较少的长程连接，从而解决了这两个问题。反映到人类社会网络中，就是有一类人特别擅长交往，他们认识很多人，正是由于他们的存在，才使得六度分隔成为可能。n六度分隔告诉我们，人与人建立链接不是一个完全随机的过程；n“人以类聚，物以群分”，复杂网络中的节点往往也呈现出集群特性：例如，社会网络中总是存在熟人圈或朋友圈，其中每个成员都认识其他成员。一种网络聚集现象集群程度的意义是网络集团化的程度，这是一种网络的内聚倾向；连通集团反映的是一个大网络中各集聚的小网络分布和相互联系的状况。例如，它可以反映这个朋友圈与另一个朋友圈的相互关系。每个人认
19、识的人数分布符合二八定律n现实世界的网络大部分都不是随机网络，少数的节点往往拥有大量的连接，而大部分节点却很少，一般而言他们符合zipf（其普夫）定律，(即：80/20马太定律)；现实中的交通网，电话网和Internet都是无标度网络；在这种网络中，存在拥有大量连接的集散节点，比如交通枢纽就是这样的节点。n人们给具有这种性质的网络起了一个特别的名字无标度网络。这里的无标度是指网络缺乏一个特征度值（或平均度值），即节点度值的波动范围相当大。在一般的随机网络（如ER模型）中，大部分的节点的度都集中在某个特殊值附近，形成泊松分布。n真实社会化网络的建立是一个什么过程呢？nBarabsi,Albert
20、-Lszl提出了他们的方法，为了构造出符合幂律（Power Law）分布（即二八定律）的网络，他们给出了一个网络的构建过程，并把这种网络称之为无尺度网络：网络是动态增长的，不断有新的节点加入，而不是随机网络中那样所有节点都已给出，仅仅是随机建立连接；优先情结，新增的点并不是如随机网络中那样和其他点有相同的概率建立建立连接，它会有更大的概率和已有很多连接的节点建立连接。n从最初的两个点开始，每次新增的一个绿色节点有更高的概率和已经有很多连接的节点建立连接；n优先情节在现实中也是存在的，大多数的普通人总是期望和少数的活跃用户建立间接。一个随机网络和一个无尺度网络，右边的黑色点就是活跃用户。n无标度
21、网络的定义按生长方式定义n网络的每个节点的连接数与此节点产生新连接的概率成增函数关系；按分布定义n网络中有一定数量的连接的节点数与此连接数量成减函数。节点连接数的zipf分布符合zipf分布的无标度网络n1999，Barabasi和Albert：BA无标度网络A.-L.Barabasi and R.Albert,Science,286,509(1999).kkP)(幂律分布（一般是负指数）n网络称之为无尺度网络，是相对于有尺度网络来讲的；n随机网络中每个节点有的连接数符合正态分布（左图）因为有大多数节点的连接数居中，于是我们可以称这个中值为这个网络的尺度；n无尺度网络的分布符合幂律分布（右图）
22、大多数人只有很少的连接，而有少数人有很多的连接，这个网络没有一个尺度来衡量网络中节点的距离，于是称之为无尺度网络。n无尺度网络的意义新用户建立连接时候的有优先情节，它更倾向于与活跃用户建立连接；拥有有大量连接的活跃用户，随着网络规模的增加，连接会越来越多，也就是富者愈富；对于社交网站：建立一个完全草根化的SNS（社交网站）是不现实的，因为人们需要活跃用户，活跃用户对SNS的拉动不容忽视；SNS中20%的人产生了80%的连接，这些人是整个网络的核心，关注这部分人的行为、喜好、特点，设计有针对性的产品会产生更好的效果；另外80%的人在网络中处于失势的地位，虽然他们有出声的权利，但是他们的声音很难成
23、为主流。nInternet就是无尺度网络；n分析Internet的度分布，Internet连接有两种：入连接和出连接；如果我的网页有一个连接指向你的网页，而你却没有指向我，则我有一个出连接而你则有一个入连接；将网页的入连接数量称为网页的入度。n有几个研究团队都发现网页入度分布可以用非常简单的规则来描述：入度为k的网页数量正比于1/(k2.3)。n为了解释为何Internet是”无尺度“，用三种不同的尺度画出遵循上面的规则的入度分布；nx轴为入度，y轴为频率。入度1000-10000 频率0-0.000001入度10000-100000 频率0-0.00000001入度100000-100000
24、0频率0-1*10(-10)无尺度就是“在不同尺度下具有不变性”n在做实验之前，很多人都认为：连接数k应当服从泊松分布或正态分布，即每个网站的被访问量差异不会太大，就像人类身高差异不会太大那样；nBarabasi等人设计了一种软件，可以从一个节点跳到另一节点，收集并记录网上的所有连接。在对几十万个节点进行统计后发现：在绝大多数网站的连接数很少的情况下，却有极少数网站拥有高于普通网站百倍、千倍甚至万倍的连接数；就像在茫茫人海中突然发现若干身高数百尺的巨人那样，令人意外。巨人的身高之大，已不能用普通人高度的尺度来度量，于是想出了“无尺度”的一词，反映少数节点连接数超乎异常的事实。n实验结果用数学语
25、言表达为：出现连接数为k的概率 p(k)，反比于k的n次方；其中，n称为幂数，它是很接近于2的一个常数；也就是说，WWW巳成为无尺度网络（scale free network）。nBarabasi等人认为优先连接性和网络的成长性是两个起因n成长性是指网民网页急剧增加，优先连接性是指新网民总是优先选择前人经常访问的网站；n随着时间的演进，某些热门的网站愈加热门，不知名的网站愈加冷门。信息社会同时兼有“大世界”与“小世界”两种属性n网民、网页、带宽随时间快速成长，使互联网巳成为全球范围内的巨大网络；n互联网是为一个个人提供服务的，每个人一天之内所能接受的信息，受到生理带宽与生理精力的限制，又是一个
26、不随时间增长的有限世界；n大世界与小世界之间，技术世界与人文世界之间存在明显的差异与矛盾。n信息学家认为无尺度现象反映了信息共享和物质共享存在本质差异n信息共享的本质：信源母体不限数量（scale free）的复制（copy）；n物质共享的本质：只是资源母体有限量的瓜分（share）。随机网络与无尺度网络的抗毁性：随机网络如果有大量结点发生故障，可能导致系统分散成多个孤岛；无尺度网络承受随机故障后的抗毁性较强，但是对于协同式攻击则更加脆弱。n复杂网络研究的简史列表时间（年）人物事件173619591967197319981999ElerErds和RnyiMilgramGranovetterWa
27、tts和StrogatzBarabsi和Albert七桥问题随机图理论小世界实验弱连接的强度小世界模型无标度网络n社会网：演员合作网、友谊网、姻亲关系网、科研合作网、Email网n生物网：食物链网、神经网、新陈代谢网、蛋白质网、基因网络n信息网络：WWW、专利使用、论文引用、信息共享n技术网络：电力网、Internet、电话线路网n交通运输网：航线网、铁路网、公路网、自然河流网n1）复杂网络模型典型的复杂网络：随机网、小世界网、无标度网等；实际网络及其分类。n2）网络的统计量及与网络结构的相关性度分布的定义和意义，聚集性、连通性的统计量及其实际意义等。n3）复杂网络性质与结构的关系同步性、鲁棒
28、性和稳定性与网络结构的关系。n4）复杂网络的动力学信息传播动力学、网络演化动力学、网络混沌动力学。n5）复杂网络的复杂结构社团结构、层次结构、节点分类结构等。n6）网络控制关键节点控制、主参数控制和控制的稳定性和有效性。n7）复杂网络建模机理建模、数据建模和实际系统的复杂网络正向与逆向建模。n8）复杂逻辑网络逻辑与高阶逻辑定义、分类、判定算法，高阶逻辑的实际意义等等。n突破性进展的主要原因突破性进展的主要原因 越来越强大的计算设备和迅猛发展的Internet，使得人们开始能够收集和处理规模巨大且种类不同的实际网络数据；学科之间的相互交叉使得研究人员可以广泛比较各种不同类型的网络数据，从而揭示复
29、杂网络的共性；以还原理论和整体论相结合为重要特色的复杂性科学的兴起，也促使人们开始从整体上研究网络的结构与性能之间的关系。n主要研究主要研究目标目标发现：揭示刻画网络系统结构的统计性质，以及度量这些性质的合适方法；建模：建立合适的网络模型以及理解网络的统计性质的意义与产生机理；分析：基于单个节点的特性和整个网络的结构性质分析与预测网络的行为；控制：提出改善已有网络性能和设计新的网络的有效方法，特别是稳定性、同步和数据流通等方面。n度(degree)：节点 i 的度 ki 定义为与该节点连接的其他节点的数目；直观上看，一个节点的度越大就意味着这个节点在某种意义上越“重要”（“能力大”）；n网络的
30、平均度：网络中所有节点的度和的平均值；n度分布函数p(k)：随机选定节点的度为k的概率；n节点的聚类系数（簇系数）：简单图中，设节点v的邻集为N(v)，|N(v)|=ki，则节点v的聚类系数定义为这ki个节点之间存在边数Ei与总的可能边数ki(ki-1)/2之比，即：Ci=2Ei/ki(ki-1)节点v的邻点间关系的密切程度。在随机网络中，当P较小时(P0，如果c，疾病传染将一直持续下去达到一个稳定的范围，此时称染病节点数占总节点数的比例为疾病传染的波及范围；相反，如果c，疾病持续传染一段时间后最终将全部被治愈。SIR模型适合于染病者在治愈后可以获得终生免疫力，或者染病者几乎不可避免走向死亡的
31、情形；SIR模型中，节点还可以处于另一种“免疫”状态，这种状态下的节点既不会被感染也不会感染其它节点，相当于将它从传播网络中剔除掉。n传统模型的问题传统的基于微分方程的传染病模型假设人群是充分混合的，染病个体原则上有机会感染任何易感的个体；这种感染总是通过某种“接触”完成的，因此如果两个个体可能接触就在相应的节点之间连一条边，那么传统的模型可以看做是对疾病在一个完全连通的社会接触网络上传播行为的描述；但是，社会接触网络具有不同于完全连通网络的结构特点；特别地，由统计物理学家发展出来的一些分析技术，例如逾渗理论、生成函数方法、平均场近似等等，使得分析具有复杂结构特性的真实网络上的传播行为称为可能
32、；n事实上，社会接触网络（复杂网络的一种）一些公认的结构特征被证明对传播规律有重大影响。小世界、无尺度等n将疾病接触网络简单抽象为规则均匀连接网络并不符合实际情况；Moore等人研究了小世界网络中的疾病传播行为，发现疾病在小世界网络中的传播阈值明显比在规则网络中小，相同的传染强度下，经历相同时间后，疾病在小世界网络中的传染范围明显大于其在规则网络中的传染范围；即：相对于规则网络，疾病在小世界网络中更适宜传染；nPaster-Satorras等研究了在无标度网络上的传染行为，结果令人震惊：无论是规则网络还是小世界网络，总存在正的传染强度阈值；无标度网络中疾病传染的阈值却非常接近于零；规则网络、小
33、世界网络、无标度网络的疾病传播波及范围与传染强度关系示意图对SIR模型的分析也可以得到类似的结果n由于大量的实证研究表明真实世界网络既具有小世界性又具有无标度特性，上述结论是相当令人沮丧的；n所幸的是，生活中无论是疾病还是计算机病毒的传染强度都非常小（1），危害不至于太大；n然而，一旦疾病或病毒的传染强度较大时就必须高度重视其危害，对其的控制措施也不能完全依赖于医疗卫生条件的提高，而只能采取隔离保护某些节点、强行切断相关连接进而中断传染途径的方法来改变传播网络的拓扑结构；n事实上，我们也正是采用上述方法成功的战胜了03年春夏之交席卷全国的SARS灾害。n疾病传播机制的研究并非问题的全部，我们的
34、最终目的是研究如何有效控制疾病传播；nPastor-Satorras等的研究表明：在资源有限的情况下，优先保护节点度数比较大的节点比随机选择节点进行保护效果要好得多；n然而实际应用中，节点的度（传染期间与某个体有可能接触的个体数目）往往是很难统计的；在对性传播疾病的研究中，研究人员只能通过问卷和口头询问的方式获知患病者或高危人群的情况，但他们回答的可信度很低；有鉴于此，一些学者依据上述思想提出了一些具有实际意义的免疫策略。n随机免疫随机免疫是在网络中随机抽取一部分节点进行免疫；研究表明，采取这种策略的话，需要对网络中几乎所有的节点都进行免疫才能保证最终消灭传染病。n选择免疫选择免疫是在网络中抽
35、取度最大的节点进行免疫；针对BA模型，采取选择免疫策略，即使有效传播率变化，也可以只免疫很小一部分节点就保证消灭传染病。n熟人免疫由于选择免疫需要知道全局节点的度数情况，才能找到度数最大节点进行免疫，这在面对互联网等庞大的复杂网络时会导致难以操作；熟人免疫采取的是随机抽取一部分节点，然后对每个节点随机选一个与之相连的“邻居”节点来进行免疫；由于在无尺度网络中，度大的节点可以与非常多的节点相连，因此选择“邻居”免疫的话，碰到度大节点的概率会比碰到度小节点的概率大得多。所以熟人免疫要比随机免疫有效得多，只略差于选择免疫。n网络传播行为的研究不仅在于分析疾病传播现象，而且可以用来分析其它许多事物的传
36、播行为；例如，我们可以将其应用于社会网络上传播行为的研究，基本思路如下：首先从复杂网络理论出发抽象出社会网络的拓扑结构，然后按照一定的传播规则分析其传播机制，最后分析如何通过一定措施影响这种传播。如：知识或技术的扩散、网络新产品的扩散以及银行金融风险的传染等，它们既有联系又有区别，前两者的研究目的是为了促进传播；后者则是为了尽量避免传播。对复杂网络的认识，也可用于理解电脑病毒、疾病和时尚的传播。n社区检测（community detection）又被称为是社区发现，它是用来揭示网络聚集行为的一种技术；n社区检测实际就是一种网络聚类的方法，这里的“社区”可以将其理解为一类具有相同特性的节点的集合
37、。网络中的社区结构n近年来，社区检测得到了快速的发展，这主要是由于复杂网络领域中的大牛Newman提出了一种模块度（modularity）的概念，从而使得网络社区划分的优劣可以有一个明确的评价指标来衡量；n一个网络不通情况下的社区划分对应不同的模块度，模块度越大，对应的社区划分也就越合理；如果模块度越小，则对应的网络社区划分也就越模糊。nNewman提出的模块度计算公式：其中：m为网络中总的边数，A是网络对应的邻接矩阵，Aij=1代表节点i和节点j之间存在连边，否则不存在连边。ki为节点i的度数，Ci为节点i属于某个社区的标号，而(Ci,Cj)=1当且仅当Ci=Cj。模块度定义可以根据一个网络
38、的空模型去进行理解：网络的空模型可以理解为只有节点而没有边，这时候一个节点可以和图中的任意其他节点相连，并且节点i和j相连的概率可以通过计算得到；随机选择一个节点与节点i相连的概率为ki/2m，随机选择一个节点与节点j相连的概率为kj/2m，那么节点i和节点j相连的概率为pipj=kikj/(4m2)，边数的期望值Pij=2mpipj=kikj/(2m)；所以模块度其实就是指一个网络在某种社区划分下与随机网络的差异，因为随机网络并不具有社区结构，对应的差异越大说明该社区划分越好。nNewman提出的模块度具有两方面的意义：模块度的提出成为了社区检测评价一种常用指标，它是度量网络社区划分优劣的量化指标；模块度的提出极大地促进了各种优化算法应用于社区检测领域的发展。许多优化算法以模块度为优化的目标方程进行优化，从而使得目标函数达到最大时得到不错的社区划分结果。n常用的社区检测方法：基于图分割的方法，如Kernighan-Lin算法，谱平分法等；基于层次聚类的方法，如GN算法、Newman快速算法等；基于模块度优化的方法，如贪婪算法、模拟退火算法、Memetic算法、PSO算法、进化多目标优化算法等。模块度的概念也有弊端，比如分辨率限制问题等，国内有学者在模块度的基础上提出了模块度密度的概念，可以很好的解决模块度的弊端。
