复杂网络-课件

复杂网络

ComplexNetwork复杂网络

ComplexNetwork为什么研究复杂网络？二十一世纪涌现的新现象互联网是怎样“链”接的？从一个页面到另一个页面，平均需要点击多少次鼠标？为什么研究复杂网络？二十一世纪涌现的新现象互联网是怎样“链美国航空网城市公共交通网为什么两者结构差异如此之大？这种差异是必然还是偶然的？城市交通涌堵的原因是什么？美国航空网城市公共交通网为什么两者结构差异如此之大？非典发现在广州，为什么却在北京爆发呢？传染病是怎样扩散和消失的？计算机病毒是怎样传播的？为什么“好事不出门，坏事行千里”呢？……互联网病毒传播网非典发现在广州，为什么却在北京爆发呢？计算机病毒是怎样传神经网络生态网络电力网络电信网络社交网络神经网络生态网络电力网络电信网络社交网络航空网络Facebook全球友谊图航空网络Facebook二十一世纪科学研究的特点二十世纪科学研究方法：分析、还原论；当分析为主要的研究方法时，人类关注如何将系统“分析”、“分解”，揭开系统的细部，了解是什么元素或部件组成了系统；忽视或破坏了这些元素是如何组合成系统的。二十一世纪（二十世纪末），系统成为主要的研究对象，整合成为主要方法；整合的方法在于了解细部以后，研究“如何组合”的问题，这导致复杂网络结构的研究；如：普列高津的耗散结构理论、哈肯的协同学、混沌和复杂系统理论、系统生物学、…二十一世纪科学研究的特点二十世纪科学研究方法：分析、还原论；复杂系统与复杂网络复杂系统与复杂网络的概念系统：集合（具体元素）+结构+功能系统的结构是什么？一切系统的基础结构都是网络；一切系统的核心结构都是逻辑网络；复杂系统的结构就是复杂网络。复杂网络是构成复杂系统的基本结构，每个复杂系统都可以看作是单元或个体之间的相互作用网络；复杂网络在刻画复杂性方面的重要性是由于结构决定功能的；复杂网络是研究复杂系统的一种角度和方法，它关注系统中因子相互关联作用的拓扑结构，是理解复杂系统性质和功能的基础。复杂系统与复杂网络复杂系统与复杂网络的概念复杂网络是构成复具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络称为复杂网络。

——钱学森具有自组织、自相似、吸引子、小世界、无标度中部复杂系统与复杂网络的主要特性1)开放性与环境和其它系统进行相互作用，交换物质、能量、信息，保持和发展系统内部的有序性与结构稳定性；在这种交换中，系统经历着从低级向高级、从简单到复杂、从无序向有序的不断优化的动态发展过程；虽然开放性是所有真实系统的基本属性，但这里的开放非指一般意义上的相互作用与交流，而开放的度量、性质、强度对复杂系统的性态、演化具有决定性的意义。例：人、城市网络簇。复杂系统与复杂网络的主要特性1)开放性2)涌现性即内部元素通过非线性相互作用，在宏观层次上产生出新的、元素不具有的整体属性；虽然涌现同样是所有系统都具有的，但这里涌现意味着新的整体属性的产生。“整体大于部分之和”，如：大脑的神经网络系统3)演化性（不可逆性)即通过与所在环境中的其它系统的相互作用和内部的自组织，使系统发展到新的阶段，表现出阶段性、临界性，完成系统演化的生命周期。社会网络中的人、生物群体的自组织系统（鸟群）2)涌现性4）复杂性结构复杂性：表现为多元性，非对称性，非均匀性，非线性分岔(Bifurcation)、混沌(Chaos)、分形Fractal；行为复杂性：表现为学习，自适应性，混沌同步，混沌边沿，随机性等等；认识复杂性：又称为主观复杂性，它表现为不确定性，描述复杂性与计算复杂性等等。例：神经网络中的突触有强有弱，可抑制也可兴奋网络复杂性：即系统内部和系统之间的相互作用可以看成由节点、边（连接）构成的体系，出现网络复杂性、小世界特征与无标度特征等。4）复杂性网络系统的复杂性（1）结构复杂性网络连接结构错综复杂、极其混乱，同时又蕴含着丰富的结构：社区、基序、聚集性、生成规律性等等，而且网络连接结构可能是随时间变化的。包括：静态结构的复杂性和结构动态演化的复杂性。例如：互联网上每天都不停地有页面和链接的产生和删除。

例：神经系统由神经元互连形成，连接以“突触连接结构”实现，突触有强弱、兴奋与抑制、不同的神经递质；连接不断改变，形成连接结构变化。（重边，加权等）网络系统的复杂性（1）结构复杂性（2）节点复杂性节点的独立或固有特性网络中的节点可能是具有分岔和混沌等复杂非线性行为的动力系统；例如：基因网络中每个节点都具有复杂的时间演化行为；一个网络中可能存在多种不同类型的节点，比如控制哺乳动物中细胞分裂的生化网络就包含各种各样的基质和酶。关联引发的节点特性当关联失去时这类特性会在节点处消失或改变；例如：耦合神经元重复地被同时激活，那么它们之间的连接就会加强，这被认为是记忆和学习的基础。（2）节点复杂性（3）复杂网络之间相互影响的复杂性实际的复杂网络会受到各种各样因素的影响和作用。例如：电力网络故障会导致Internet网速变慢，运输系统失控等一系列不同网络间的连锁反应。（4）网络分层结构的复杂性行政管理网络是具有层结构的，多数网络都有节点的分层结构，只是在许多网络中没有意识到是一种造成复杂性的重要结构。（3）复杂网络之间相互影响的复杂性对复杂网络的理解复杂网络是二十一世纪科学研究的思想和理念，它启发我们用什么观点理解这个世界：整个世界以及组成世界的任何细部都是由网络及其变化形成的；复杂网络也是研究复杂系统的一种技术和方法，它关注系统中个体相互作用的拓扑结构，是理解复杂系统性质和功能的基本方法。对复杂网络的理解复杂网络是二十一世纪科学研究的思想和理念，它复杂网络研究简史格尼斯堡七桥问题Euler（1707~1783），瑞士数学家，图论之父一笔画问题复杂网络研究简史格尼斯堡七桥问题Euler（1707~178随机图理论20世纪60年代，由两位匈牙利数学家Erdǒs和Rényi建立的随机图理论（randomgraphtheory）被公认为是在数学上开创了复杂网络理论的系统性研究。Erdǒs和Rényi的最重要的发现：ER随机图的许多重要性质都是突然涌现的。即：对于任一给定的概率p，要么几乎每一个图都具有某个性质Q（比如说，连通性），要么几乎每一个图都不具有该性质。在20世纪的后40年中，随机图理论一直是研究复杂网络的基本理论随机图理论Erdǒs和Rényi的最重要的发现：ER随机图的小世界实验大多数人都过这样的经历：碰到一个陌生人，同他聊了一会后发现你认识的某个人居然他也认识，然后一起发出“这个世界真小”的感叹；那么对于世界上任意两个人来说，借助第三者、第四者这样的间接关系来建立起他们两人的联系平均来说最少要通过多少人呢？哈佛大学美国社会心理学家斯坦利•米尔格伦(StanleyMilgram)在1967年实验后得出结论：中间的联系人平均只需要5个，他把这个结论称为“六度分离”（SixDegreesofSeparation）；六度分离：平均只要通过5个人，你就能与世界任何一个角落的任何一个人发生联系。这个结论定量地说明了我们世界的”大小”，或者说人与人关系的紧密程度；六度分离理论一直被作为社会心理学的经典范例之一。小世界实验大多数人都过这样的经历：碰到一个陌生人，同他聊了一小世界实验米尔格伦的实验过程：他计划通过人传人的送信方式来统计人与人之间的联系；首先把信交给志愿者A，告诉他信最终要送给收信人S；如果他不认识S，那么就送信到某个他认识的人B手里，理由是A认为在他的交集圈里B是最可能认识S的；但是如果B也不认识S，那么B同样把信送到他的一个朋友C手中，……，就这样一步步最后信终于到达S那里；这样就A→B→C→……→S连成了一个链；斯坦利•米尔格伦通过对这个链做了统计后做出了六度分离的结论。尽管如此，实际上这个理论并没有得到严格的证实；美国心理学教授朱迪斯•克兰菲尔德（JudithKleinfeld）对米尔格伦最初的实验提出不同意见，因为她发现实验的完成率极低（实际上只有三分之一的信送到了收信人那里）。小世界实验米尔格伦的实验过程：尽管如此，实际上这个理论并没有小世界实验Bacon数截止到最近，世界电影史上共产生了大约23万部电影，78多万名电影演员，KavinBacon在许多部电影中饰演小角色；Virginia大学的计算机专家BrettTjaden设计了一个游戏，他声称电影演员KevinBacon是电影界的中心，定义了Bacon数：一个演员如果和KavinBacon一起演过电影，那么他（她）的Bacon数就为1；如果他（她）没有和Bacon演过电影，但是和Bacon数为1的演员一起演过电影，那么他的Bacon数就为2；依此类推。小世界实验Bacon数截止到最近，世界电影史上共产生小世界实验Bacon数网站http:///oracle/的数据库里总共存有有783,940个世界各地的演员的信息，以及231,088部电影信息；通过简单地输入演员名字就可以知道这个演员的bacon数；比如输入StephenChow（周星驰）就可以得到这样的结果：周星驰在1991年的《豪门夜宴(Haomenyeyan)》中与洪金宝(SammoHungKam-Bo)合作；而洪金宝又在李小龙的最后一部电影，即1978年的《死亡的游戏（GameofDeath）》中与ColleenCamp合作；ColleenCamp在去年的电影《Trapped》中与KevinBacon合作；这样周星驰的Bacon数为3。对78万个演员所做的统计：演员的最大Bacon数仅仅为8，平均Bacon数仅为2.948。小世界实验Bacon数网站http://www.cs.小世界实验Erdos数PaulErdos(1913-1996)：出生于匈牙利的犹太籍数学家，被公认为20世纪最伟大的天才之一；Erdos毕生发表的论文超过1500篇（在数学史上仅次于欧拉），超长的合作者名单，合作者超过450位，若加上别人所做但曾获他关键性提示之论文，则数万篇；他的研究领域主要是数论和组合数学，但他的论文中涵盖的非常多的学科；"MathematicalReviews"曾把数学划分为大约六十个分支，Erdos的论文涉及到了其中的40%.

小世界实验Erdos数PaulErdos(1913小世界实验Erdos数定义Erdos数(Erdos

number)

的定义：

Erdos本人之Erdos数为0；任何人若曾与Erdos合写过论文，则其Erdos数为1；任何人若曾与一位Erdos数为l(且不曾与有更少的Erdos数)

的人合写过论文，则他的Erdos数为2…几乎每一个当代数学家都有一个有限的Erdos数，而且这个数往往非常小，小得出乎本人的预料；证明Fermat大定理的AndrewWiles，他的研究方向与Erdos相去甚远，但他的Erdos数只有3，是通过这个途径实现的：Erdos--AndrewOdlyzko--ChrisM.Skinner--AndrewWiles.小世界实验Erdos数定义Erdos数(Erdos

小世界实验Erdos数Fields奖得主的Erdos数都不超过5（只有Cohen和Grothendieck的Erdos数是5）；

Nevanlinna奖得主的Erdos数不超过3（只有Valiant的Erdos数是3）；Wolf数学奖得主的Erdos数不超过6（只有V.I.Arnold是6，且只有Kolmogorov是5）；Steele奖的终身成就奖得主的Erdos数不超过4；其他领域的专家：比尔盖兹(BillGates)，他的Erdos数是4，通过如下途径实现：Erdos--PavolHell--XiaoTieDeng--ChristosH.Papadimitriou--WilliamH.(Bill)Gates；

爱因斯坦的Erdos数是2。小世界实验Erdos数Fields奖得主的Erdos复杂网络研究两篇开创性的文章可以看作是复杂网络研究新纪元开始的标志：美国康奈尔（Cornell）大学理论和应用力学系的博士生Watts及其导师、非线性动力学专家Strogatz教授于1998年6月在Nature杂志上发表的《“小世界”网络的集体动力学》（CollectiveDynamicsof‘Small-World’Networks）；美国NotreDame大学物理系的Barabāsi教授及其博士生Albert于1999年10月在Science杂志上发表的《随机网络中标度的涌现》（EmergenceofScalinginRandomNetworks）。这两篇文章分别揭示了复杂网络的小世界特征和无标度性质，并建立了相应的模型以阐述这些特性的产生机理。复杂网络研究两篇开创性的文章可以看作是复杂网络研究新纪元开始1998，Watts和Strogatz：WS小世界网络D.J.Watts,andS.H.Strogatz,Nature,393,440-442(1998).1998，Watts和Strogatz：WS小世界网络D.60个节点组成的一个环每个节点与相邻的两个节点相连，计算网络的平均路径长度，即网络中所有节点对之间的路径长度的平均值。规则网络的平均路径长度为15，面对面的两个点之间的信息交流会需要较长时间。60个节点组成的一个环将规则网络中少量与相邻节点连接的边改成长距离连接对图中5%的边（3条）进行重连后得到的网络，重连时3条边的一端被解开，重新连接到一个随机选择的节点上；重连后的网络与原来的规则网络的边数量一样多，但平均路径长度降到了9左右；节点数量越多，这个效应越明显。如果是有1000个节点的规则网络，平均路径长度是250，如果5%的边重连，平均路径长度会降到20。将规则网络中少量与相邻节点连接的边改成长距离连接小世界性一个网络如果只有少量的长程连接，相对于节点数量来说平均路径却很短，则为小世界网络；自然、社会和技术演化产生的许多生物、群体和产品似乎都具有这种结构；这是为什么呢？有人认为至少有两种相互矛盾的选择压力导致了这种结果：在系统内快速传播信息的需要，以及产生和维持可靠的远程连接的高成本；小世界网络具有较短的平均路径长度，同时又只需相对较少的长程连接，从而解决了这两个问题。反映到人类社会网络中，就是有一类人特别擅长交往，他们认识很多人，正是由于他们的存在，才使得六度分隔成为可能。小世界性反映到人类社会网络中，就是有一类人特别擅长交往，他们无标度网络（Scale-freenetwork）六度分隔告诉我们，人与人建立链接不是一个完全随机的过程；“人以类聚，物以群分”，复杂网络中的节点往往也呈现出集群特性：例如，社会网络中总是存在熟人圈或朋友圈，其中每个成员都认识其他成员。一种网络聚集现象集群程度的意义是网络集团化的程度，这是一种网络的内聚倾向；连通集团反映的是一个大网络中各集聚的小网络分布和相互联系的状况。例如，它可以反映这个朋友圈与另一个朋友圈的相互关系。每个人认识的人数分布符合二八定律无标度网络（Scale-freenetwork）六度分隔告无标度网络（Scale-freenetwork）现实世界的网络大部分都不是随机网络，少数的节点往往拥有大量的连接，而大部分节点却很少，一般而言他们符合zipf（其普夫）定律，(即：80/20马太定律)；现实中的交通网，电话网和Internet都是无标度网络；在这种网络中，存在拥有大量连接的集散节点，比如交通枢纽就是这样的节点。人们给具有这种性质的网络起了一个特别的名字——无标度网络。这里的无标度是指网络缺乏一个特征度值（或平均度值），即节点度值的波动范围相当大。在一般的随机网络（如ER模型）中，大部分的节点的度都集中在某个特殊值附近，形成泊松分布。无标度网络（Scale-freenetwork）现实世界的复杂网络-课件无标度网络（Scale-freenetwork）真实社会化网络的建立是一个什么过程呢？Barabási,Albert-László提出了他们的方法，为了构造出符合幂律（PowerLaw）分布（即二八定律）的网络，他们给出了一个网络的构建过程，并把这种网络称之为无尺度网络：网络是动态增长的，不断有新的节点加入，而不是随机网络中那样所有节点都已给出，仅仅是随机建立连接；优先情结，新增的点并不是如随机网络中那样和其他点有相同的概率建立建立连接，它会有更大的概率和已有很多连接的节点建立连接。无标度网络（Scale-freenetwork）真实社会化从最初的两个点开始，每次新增的一个绿色节点有更高的概率和已经有很多连接的节点建立连接；优先情节在现实中也是存在的，大多数的普通人总是期望和少数的活跃用户建立间接。一个随机网络和一个无尺度网络，右边的黑色点就是活跃用户。从最初的两个点开始，每次新增的一个绿色节点有更高的概率和已经无标度网络的定义按生长方式定义网络的每个节点的连接数与此节点产生新连接的概率成增函数关系；按分布定义网络中有一定数量的连接的节点数与此连接数量成减函数。节点连接数的zipf分布符合zipf分布的无标度网络无标度网络的定义节点连接数的zipf分布符合zipf分布的无1999，Barabasi和Albert：BA无标度网络A.-L.Barabasi

andR.Albert,Science,286,509(1999).幂律分布（一般是负指数）1999，Barabasi和Albert：BA无标度网络A网络称之为无尺度网络，是相对于有尺度网络来讲的；随机网络中每个节点有的连接数符合正态分布（左图）因为有大多数节点的连接数居中，于是我们可以称这个中值为这个网络的尺度；无尺度网络的分布符合幂律分布（右图）大多数人只有很少的连接，而有少数人有很多的连接，这个网络没有一个尺度来衡量网络中节点的距离，于是称之为无尺度网络。网络称之为无尺度网络，是相对于有尺度网络来讲的；无尺度网络的意义新用户建立连接时候的有优先情节，它更倾向于与活跃用户建立连接；拥有有大量连接的活跃用户，随着网络规模的增加，连接会越来越多，也就是富者愈富；对于社交网站：建立一个完全草根化的SNS（社交网站）是不现实的，因为人们需要活跃用户，活跃用户对SNS的拉动不容忽视；SNS中20%的人产生了80%的连接，这些人是整个网络的核心，关注这部分人的行为、喜好、特点，设计有针对性的产品会产生更好的效果；另外80%的人在网络中处于失势的地位，虽然他们有出声的权利，但是他们的声音很难成为主流。无尺度网络的意义对于社交网站：Internet就是无尺度网络；分析Internet的度分布，Internet连接有两种：入连接和出连接；如果我的网页有一个连接指向你的网页，而你却没有指向我，则我有一个出连接而你则有一个入连接；将网页的入连接数量称为网页的入度。有几个研究团队都发现网页入度分布可以用非常简单的规则来描述：入度为k的网页数量正比于1/(k^2.3)。Internet就是无尺度网络；为了解释为何Internet是”无尺度“，用三种不同的尺度画出遵循上面的规则的入度分布；x轴为入度，y轴为频率。入度1000-10000频率0-0.000001入度10000-100000频率0-0.00000001入度100000-1000000频率0-1*10^(-10)无尺度就是“在不同尺度下具有不变性”为了解释为何Internet是”无尺度“，用三种不同的尺度画对无标度网络的理解在做实验之前，很多人都认为：连接数k应当服从泊松分布或正态分布，即每个网站的被访问量差异不会太大，就像人类身高差异不会太大那样；Barabasi等人设计了一种软件，可以从一个节点跳到另一节点，收集并记录网上的所有连接。在对几十万个节点进行统计后发现：在绝大多数网站的连接数很少的情况下，却有极少数网站拥有高于普通网站百倍、千倍甚至万倍的连接数；就像在茫茫人海中突然发现若干身高数百尺的巨人那样，令人意外。巨人的身高之大，已不能用普通人高度的尺度来度量，于是想出了“无尺度”的一词，反映少数节点连接数超乎异常的事实。实验结果用数学语言表达为：出现连接数为k的概率p(k)，反比于k的n次方；其中，n称为幂数，它是很接近于2的一个常数；也就是说，WWW巳成为无尺度网络（scalefreenetwork）。对无标度网络的理解在做实验之前，很多人都认为：连接数k应当服无尺度现象的成因Barabasi等人认为优先连接性和网络的成长性是两个起因成长性是指网民网页急剧增加，优先连接性是指新网民总是优先选择前人经常访问的网站；随着时间的演进，某些热门的网站愈加热门，不知名的网站愈加冷门。信息社会同时兼有“大世界”与“小世界”两种属性网民、网页、带宽随时间快速成长，使互联网巳成为全球范围内的巨大网络；互联网是为一个个人提供服务的，每个人一天之内所能接受的信息，受到生理带宽与生理精力的限制，又是一个不随时间增长的有限世界；大世界与小世界之间，技术世界与人文世界之间存在明显的差异与矛盾。无尺度现象的成因Barabasi等人认为无尺度现象的成因信息学家认为无尺度现象反映了信息共享和物质共享存在本质差异信息共享的本质：信源母体不限数量（scalefree）的复制（copy）；物质共享的本质：只是资源母体有限量的瓜分（share）。无尺度现象的成因信息学家认为随机网络与无尺度网络的抗毁性：随机网络如果有大量结点发生故障，可能导致系统分散成多个孤岛；无尺度网络承受随机故障后的抗毁性较强，但是对于协同式攻击则更加脆弱。随机网络与无尺度网络的抗毁性：复杂网络研究的简史列表时间（年）人物事件173619591967197319981999EülerErdǒs和RényiMilgramGranovetterWatts和StrogatzBarabási和Albert七桥问题随机图理论小世界实验弱连接的强度小世界模型无标度网络复杂网络研究的简史列表时间（年）人物事件1736Eü不同领域的复杂网络社会网：演员合作网、友谊网、姻亲关系网、科研合作网、Email网生物网：食物链网、神经网、新陈代谢网、蛋白质网、基因网络信息网络：WWW、专利使用、论文引用、信息共享技术网络：电力网、Internet、电话线路网交通运输网：航线网、铁路网、公路网、自然河流网不同领域的复杂网络社会网：复杂网络研究内容1）复杂网络模型典型的复杂网络：随机网、小世界网、无标度网等；实际网络及其分类。2）网络的统计量及与网络结构的相关性度分布的定义和意义，聚集性、连通性的统计量及其实际意义等。3）复杂网络性质与结构的关系同步性、鲁棒性和稳定性与网络结构的关系。4）复杂网络的动力学信息传播动力学、网络演化动力学、网络混沌动力学。复杂网络研究内容1）复杂网络模型5）复杂网络的复杂结构社团结构、层次结构、节点分类结构等。6）网络控制关键节点控制、主参数控制和控制的稳定性和有效性。7）复杂网络建模机理建模、数据建模和实际系统的复杂网络正向与逆向建模。8）复杂逻辑网络逻辑与高阶逻辑定义、分类、判定算法，高阶逻辑的实际意义等等。5）复杂网络的复杂结构复杂网络研究突破性进展的主要原因①越来越强大的计算设备和迅猛发展的Internet，使得人们开始能够收集和处理规模巨大且种类不同的实际网络数据；②学科之间的相互交叉使得研究人员可以广泛比较各种不同类型的网络数据，从而揭示复杂网络的共性；③以还原理论和整体论相结合为重要特色的复杂性科学的兴起，也促使人们开始从整体上研究网络的结构与性能之间的关系。复杂网络研究突破性进展的主要原因主要研究目标发现：揭示刻画网络系统结构的统计性质，以及度量这些性质的合适方法；建模：建立合适的网络模型以及理解网络的统计性质的意义与产生机理；分析：基于单个节点的特性和整个网络的结构性质分析与预测网络的行为；控制：提出改善已有网络性能和设计新的网络的有效方法，特别是稳定性、同步和数据流通等方面。主要研究目标复杂网络中的基本概念度(degree)：节点i的度ki

定义为与该节点连接的其他节点的数目；直观上看，一个节点的度越大就意味着这个节点在某种意义上越“重要”（“能力大”）；网络的平均度：网络中所有节点的度和的平均值；度分布函数p(k)：随机选定节点的度为k的概率；复杂网络中的基本概念度(degree)：节点i的度ki复杂网络中的基本概念节点的聚类系数（簇系数）：简单图中，设节点v的邻集为N(v)，|N(v)|=ki，则节点v的聚类系数定义为这ki个节点之间存在边数Ei与总的可能边数ki(ki-1)/2之比，即： Ci=2Ei/ki(ki-1)节点v的邻点间关系的密切程度。

在随机网络中，当P较小时(P<0.01)，最短路径平均长度急剧下降，而聚类系数几乎没有变化。这些网络具有较短的特征路径长度和较大的聚类系数，称其为“小世界网络”。复杂网络中的基本概念节点的聚类系数（簇系数）：简单图中，设节网络的聚类系数C：所有节点i的聚类系数Ci的平均值，（0C1）C=0

网络中所有节点都是孤立点C=1

网络中任意节点间都有边相连说明网络节点间联系的密切程度，体现网络的凝聚力；许多大规模的实际网络都具有明显的聚类效应。事实上，在很多类型的网络(如社会关系网络)中，你的朋友同时也是朋友的概率会随着网络规模的增加而趋向于某个非零常数，即当N→∞时，C=O(1)；这意味着这些实际的复杂网络并不是完全随机的，而是在某种程度上具有类似于社会关系网络中“物以类聚，人以群分”的特性。网络的聚类系数C：事实上，在很多类型的网络(如社会关系网络)最短路径（Shortestpath）：两个节点之间边数最少的路径，最短路径的长度称为两点间的距离，用dij表示。平均路径长度（特征路径长度）L：所有节点对之间的距离的平均值。研究发现：尽管许多实际复杂网络的节点数巨大，网络的平均路径长度却小的惊人。（小世界效应）d(a,b)=1;d(a,d)=1;d(a,b)=1;d(b,c)=2;d(b,d)=1;d(c,d)=2L=8*2/4*3=16/12=1.33最短路径（Shortestpath）：研究发现：尽管许多实介数（Betweenness）点介数：网络中通过该节点的最短路径的条数；如果一对节点间共有B条不同的最短路径，其中有b条经过节点i，那么节点i对这对节点的介数的贡献为b/B；把节点i对所有节点对的贡献累加起来再除以节点对总数，就可得到节点i的介数。边介数：网络中通过该边的最短路径的条数；所有节点对的最短路径中经过该边的数量比例。介数（Betweenness）点介数：介数（Betweenness）说明：介数反映了节点或边的作用和影响力；介数越大，说明经过该节点（边）的最短路径的数目越多；在信息传播过程中，通过该节点（边）的信息量就越大，于是就越容易发生拥塞；研究表明：节点介数与度之间有很强的相关性，不同类型的网络，其介数分布也大不一样。网络介数

网络点介数，网络边介数：所有节点（边）的平均介数

网络介数说明了网络的什么性质？

介数（Betweenness）说明：网络介数核数一个图的k-核：反复去掉图中度小于等于k的节点后，所剩余的子图，若一个节点存在于k-核，而在(k+1)-核中被去掉，则此节点核数为k；例：所有度为1的节点的核数必为0；节点核数中的最大值称为网络图的核数；节点核数可以表明节点在核中的深度；即便一个节点的度数很高，它的核数也可能很小；例如：包含N个节点的星型网络的中心节点的度数为N-1，但它的核数为0。核数思考：目前刻划复杂网络的统计量有很多；如：聚类系数、平均路径长度、平均度、介数、核数等。问题：能不能用一个或尽可能少的统计量来综合刻划复杂网络的结构呢？用多少相互独立的统计量刻画复杂网络的结构是完备的？思考：复杂寓于简单在不同领域许多系统都呈自相似结构，即局部与总体相似。例如国家、河流、行星系等都是这样；“分形”是研究自相似结构的。分形的构成常遵循一种法则：复杂的分形外形是由简单的规则重复迭代生成的；以Koch曲线为例：将一直线三等分，中间的1/3用一等边三角形取代。直线变为4段等长折线。每段直线再按此规则变化,一直重复下去，即生成Koch曲线。复杂寓于简单在不同领域许多系统都呈自相似结构，即局部与总体相复杂网络研究方向从统计物理的角度研究的核心思想是研究一个系统所有节点的统计规律；大部分复杂网络的统计量也是从这里出来的可根据百度百科对统计物理粗浅的说明：“统计物理学statisticalphysics根据对物质微观结构及微观粒子相互作用的认识，用概率统计的方法，对由大量粒子组成的宏观物体的物理性质及宏观规律作出微观解释的理论物理学分支，又称统计力学；“大量”是以1摩尔物质所含分子数（其数量级为10^23个）为尺度的。”但是，从统计物理的角度研究复杂网络或复杂系统可能有个问题，就是现在研究系统中节点的个数都称不上“大量”，甚至可以预想的将来某些系统也不会达到这个量级，有限数据效应可能会导致无标度分布的度大节点在网络中占统治地位，结果使某些看似合情合理的统计性质并不能反映网络的真实性质。复杂网络研究方向从统计物理的角度复杂网络研究方向从系统科学的角度系统科学研究复杂网络就是将复杂网络中的所有节点作为一个大系统进行研究；但问题是这样的，将一个复杂系统抽象成一个网络进行研究本来就是无法从系统论对某个系统进行详细研究的无奈简化，也就是说，对某个系统无法进行直接研究；系统中各个节点相互交互的某种关系能否抽象为一种链接关系，然后集中精力来研究这种链接关系，那么怎么来研究这种链接联系呢，系统科学没告诉我们，能否从系统科学的角度来“发明”一种复杂网络的研究方法？但是系统科学目前还不能提供比较好的方法论，现在仅仅知道节点之间是相互关联的，一个整体的各个部分不能像以前那样分割出来进行研究，这也是系统科学对其他各个学科门类的贡献。复杂网络研究方向从系统科学的角度复杂网络研究方向从知识发现或数据挖掘的角度这方面的研究目前主要集中在在线社会网络（SNS）研究方面，实际上这10年来复杂网络方面有重大意义的研究都集中在这方面，尽管某些有用特征（如无标度和小世界特性）挖掘出来以后后面会有相应的在统计物理和系统科学方面的理解，比如有好多这方面的建模工作；但是实际数据中得到的规律是最重要的，复杂网络的兴起实际上也是信息获取便捷的产物，本质上使用复杂网络来研究实际系统是数据挖掘的一种形式和方法，尽管这种方法的直观性是它的天然优势，但并不代表这种方法是最有效的，随着数据挖掘技术的不断深化，也许对于某些研究基于数据本身的挖掘方法的能力会强于先将原始数据的某种关系转变为一种网络关系，再使用复杂网络进行分析。复杂网络研究方向从知识发现或数据挖掘的角度PageRank算法Web上超链接结构是个非常丰富和重要的资源，如果能够充分利用的话，可以极大的提高检索结果的质量；SergeyBrin(谢尔盖·布林)和LawrencePage(拉里·佩奇)在1998年提出了PageRank算法，同年J.Kleinberg（J·克莱因伯格）提出了HITS算法；LawrencePage,SergeyBrin,RajeevMotwani,TerryWinograd,'ThePageRankCitationRanking:BringingOrdertotheWeb',1998,

/~backrub/pageranksub.ps为了更高效地计算PageRank，算法改良以后的一篇论文：TaherH.Haveliwala,‘EfficientComputationofPageRank’,StanfordTechnicalReport,1999；http://:8090/pub/1999-31PageRank(TM)是美国Google公司的登记注册商标。PageRank算法Web上超链接结构是个非常丰富和重要的资Google查询过程PageRank?Google查询的全过程通常不超过半秒时间，但在这短短的时间内需要完成多个步骤，然后才能将搜索结果交付给搜索信息的用户。Google查询过程PageRank?Google查询的全过PageRank的提出Google的创始人之一LarryPage于1998年提出了PageRank，并应用在Google搜索引擎的检索结果排序上，该技术也是Google早期的核心技术之一；LarryPage是Google的创始首席执行官，2001年4月转任现职产品总裁。他目前仍与EricSchmidt和SergeyBrin一起共同负责Google的日常运作。他在斯坦福大学攻读计算机科学博士学位期间，遇到了SergeyBrin，他们于1998年合伙创立Google。PageRank的提出Google的创始人之一LarryPGoogle的网页排序在Google中搜索“体育新闻”Google的网页排序在Google中搜索“体育新闻”Google的网页排序在Google中搜索“体育新闻”搜索引擎工作的简要过程：针对查询词“体育新闻”进行分词—》“体育”、“新闻”；根据建立的倒排索引，将同时包含“体育”和“新闻”的文档返回，并根据相关性进行排序；这里的相关性主要是基于内容的相关性；但是会有一些垃圾网页，虽然也包含大量的查询词，但却并非满足用户需要的文档。因此，页面本身的重要性在网页排序中也起着很重要的作用一个网页中虽然出现了四次“体育新闻”但却不是用户所需要的Google的网页排序在Google中搜索“体育新闻”因此，AB网页是节点，网页间的链接关系是边Google的网页排序如何度量网页本身的重要性呢？互联网上的每一篇html文档除了包含文本、图片、视频等信息外，还包含了大量的链接关系，利用这些链接关系，能够发现某些重要的网页；直观地看，某网页A链向网页B，则可以认为网页A觉得网页B有链接价值，是比较重要的网页；某网页被指向的次数越多，则它的重要性越高；越是重要的网页，所链接的网页的重要性也越高。AB网页是节点，网页Google的网页排序如何度量网页本身的Google的网页排序如何度量网页本身的重要性呢？比如，新华网体育在其首页中对新浪体育做了链接，人民网体育同样在其首页中对新浪体育做了链接；可见，新浪体育被链接的次数较多；同时，人民网体育和新华网体育也都是比较“重要”的网页，因此新浪体育也应该是比较“重要”的网页。新华网体育人民网体育Google的网页排序如何度量网页本身的重要性呢？新华网体育链向网页E的链接远远多于链向网页C的链接，但网页C的重要性却大于网页E；这是因为因为网页C被网页B所链接，而网页B有很高的重要性。Google的网页排序一个更加形象的图链向网页E的链接远远多于链向网页C的链接，但网页C的重要性却什么是PageRankPageRank一种在搜索引擎中根据网页间相互链接关系计算网页排名的技术；是Google用来标识网页的等级或重要性的一种方法；级别从1到10级，PR值越高说明该网页越受欢迎（越重要）；查看某站点PageRank值，安装GOOGLE工具条并启用PageRank特性，或者在firefox安装SearchStatus插件。PageRank近似于一个用户，是指在Internet上随机地单击链接将会到达特定网页的可能性；思想：能够从更多地方到达的网页更为重要，因此具有更高的PageRank。什么是PageRankPageRank查看某站点PageRaPageRank的核心思想

PageRank基于“从许多优质的网页链接过来的网页，必定还是优质网页”的回归关系，来判定所有网页的重要性。链入链接数(单纯的意义上的受欢迎度指标)链入链接是否来自推荐度高的页面(有根据的受欢迎指标)链入链接源页面的链接数

(被选中的几率指标)因此，如果从类似于Yahoo!那样的PageRank非常高的站点被链接的话，仅此网页的PageRank也会一下子上升；相反地，无论有少链入链接数，如果全都是从那些没有多大意义的页面链接过来的话，PageRank也不会轻易上升。PageRank的核心思想PageRank基于“从许多PageRank简单计算假设一个由只有4个页面组成的集合：A、B、C和D，如果所有页面都链向A，那么A的PR（PageRank）值将是B，C及D的和；继续假设B也有链接到C，并且D也有链接到包括A的3个页面，由于一个页面不能投票2次，所以B给每个页面0.5票。以同样的逻辑，D投出的票只有1/3算到了A的PR值上；即：链出总数平分一个页面的PR值；PageRank简单计算假设一个由只有4个页面组成的集合：APageRank的简化模型把互联网上的各网页之间的链接关系看成一个有向图；假设浏览的下一个网页链接来自于当前网页。建立简化模型：任意网页Pi的PageRank值可表示为：Bi为所有链接到网页i的网页集合；Lj为网页j的对外链接数（出度）。PageRank的简化模型把互联网上的各网页之间的链接关系看PR(A)PR(B)PR(C)PR(D)初始50.25一次迭代0.1250.1250.250.25二次迭代0.1250.1250.1250.25三次迭代0.1250.1250.1250.125……………n次迭代0000简化模型面临的缺陷RankLeak一个独立的网页如果没有外出的链接就产生等级泄漏。PR(A)PR(B)PR(C)PR(D)初始0.250.25PR(A)PR(B)PR(C)PR(D)初始50.25一次迭代00.3750.250.375二次迭代00.3750.3750.25三次迭代00.250.3750.375四次迭代00.3750.250.375五次迭代0………RankSink整个网页图中的一组紧密链接成环的网页如果没有外出的链接就产生Ranksink。PR(A)PR(B)PR(C)PR(D)初始0.250.25PageRank的随机浏览模型假定一个上网者从一个随机的网页开始浏览，上网者不断点击当前网页的链接开始下一次浏览。但是，上网者最终厌倦了，开始了一个随机的网页；随机上网者用以上方式访问一个新网页的概率就等于这个网页PageRank值；①这种随机模型更加接近于用户的浏览行为；②一定程度上解决了rankleak和ranksink的问题；③保证pagerank具有唯一值。设定任意两个顶点之间都有直接通路，在每个顶点处以概率d按原来蓝色方向转移，以概率1-d按红色方向转移。PageRank的随机浏览模型假定一个上网者从一个随机的网页随机浏览模型的邻接表表示由于网页数目巨大，网页之间的连接关系的邻接矩阵是一个很大的稀疏矩阵，采用邻接表来表示网页之间的连接关系，随机浏览模型的PageRank公式：N:网络中网页总数；d:阻尼因子，通常设为0.85,d即按照超链接进行浏览的概率；1-d：随机跳转一个新网页的概率；PR(pj):网页pj的PR值；L(pj)：网页pj的链出网页数。随机浏览模型的邻接表表示由于网页数目巨大，网页之间的连接关系马尔可夫链收敛定理一个页面的PageRank是由其他页面的PageRank计算到；Google不断的重复计算每个页面的PageRank；如果给每个页面一个随机PageRank值（非0），由于等式PR=A*PR满足马尔可夫链的性质，如果马尔可夫链收敛，则PR存在唯一解，并且经过不断的重复迭代计算，这些页面的PR值会趋向于正常和稳定。马尔可夫链收敛定理一个页面的PageRank是由其他页面的PPageRank的计算互联网是一个有向图；每一个网页是图的一个顶点；网页间的每一个超链接是图的一个有向边；用邻接矩阵来表示图，即：定义邻接矩阵为G，若网页j到网页i有超链接，则；反之；显然，如果网页有N个，则矩阵为N×N的0、1方阵。多个网页相互链接的图对应的邻接矩阵（这里将0,1值用二值图像显示，黑色代表0，白色代表1）PageRank的计算互联网是一个有向图；多个网页相互链接的PageRank的计算定义邻接矩阵为G，若网页j到网页i有超链接，则

；反之，；记矩阵G的列和、行和分别是它们分别给出了页面j的链出链接数目和链入链接数目；假设我们在上网的时侯浏览页面并选择下一个页面，这个过程与过去浏览过哪些页面无关，而仅依赖于当前所在的页面，那么这一选择过程可以认为是一个有限状态、离散时间的随机过程，其状态转移规律用Markov链描述；定义转移概率矩阵PageRank的计算定义邻接矩阵为G，若网页j到网页i有超PageRank的计算根据Markov链的基本性质，对于正则Markov链，存在平稳分布，满足表示在极限状态（转移次数趋于无限）下各网页被访问的概率分布；定义为网页的PageRank向量，表示第i个网页的PageRank值。求矩阵A的特征值1对应的特征向量PageRank的计算根据Markov链的基本性质，对于正则某7个网页之间的链接关系图某7个网页之间的链接关系图PageRank结果的评价将PageRank的评价按顺序排列(PageRank小数点3位四舍五入)：PageRank结果的评价将PageRank的评价按顺序页面之间相互关系及状态转移图页面之间相互关系及状态转移图PageRank结果的评价ID=1的页面的PageRank是0.304，占据全体的三分之一，成为了第1位；起到相当大效果的是从排在第3位的ID=2页面中得到了所有的PageRank(0.166)数；ID=2页面有从3个地方过来的链入链接，而只有面向ID=1页面的一个链接，因此(面向ID=1页面的)链接就得到ID=2的所有的PageRank数。PageRank结果的评价ID=1的页面的PageRankPageRank结果的评价反过来，最后一名的ID=6页面只有ID=1的15％的微弱评价；总之，即使有同样的链入链接的数目，链接源页面评价的高低也影响PageRank的高低。PageRank结果的评价反过来，最后一名的ID=6页面PageRank数值计算难点计算机容量限制假设N是104

的数量级；通常，数值计算程序内部行列和矢量是用双精度记录的，N次正方行列A的存储规模为：

sizeof(double)*N*N=8*104

*104＝800MB目前，Google处理80亿个以上的页面，这种做法已经完全不适用了。收敛问题特征向量的求解，就是求解方程

，是N元一次方程组，一般地不能得到分析解，所以只能解其数值；然而，常用的迭代求解方法会导致收敛速度很慢。PageRank数值计算难点计算机容量限制改进LarryPage和SergeyBrin两人从理论上证明了不论初始值如何选取，这种算法都保证了网页排名的估计值能收敛到他们的真实值；由于互联网上网页的数量是巨大的，上面提到的二维矩阵从理论上讲有网页数目平方之多个元素。如果假定有十亿个网页，那么这个矩阵就有一百亿亿个元素。这样大的矩阵相乘，计算量是非常大的；LarryPage和SergeyBrin两人利用稀疏矩阵计算的技巧，大大的简化了计算量。改进LarryPage和SergeyBrin两人从理论PageRank算法的应用学术论文的重要性排序学术论文的作者的重要性排序；某作者引用了其它作者的文献，则该作者认为其它作者是“重要”的；网络爬虫(WebCrawler)可以利用PR值，决定某个URL，所需要抓取的网页数量和深度；重要性高的网页抓取的页面数量相对多一些，反之，则少一些；关键词与句子的抽取（节点与边）。PageRank算法的应用学术论文的重要性排序PageRank小结优点：与查询无关的静态算法，所有网页的PageRank值通过离线计算获得；有效减少在线查询时的计算量、降低了查询响应时间。缺点过分相信链接关系一些权威网页往往是相互不链接的，比如新浪、搜狐、网易以及腾讯这些大的门户之间，基本是不相互链接的，学术领域也是这样；忽略了主题相关性人的查询具有主题特征，导致结果的相关性和主题性降低；旧的页面等级比新页面高因为即使是非常好的新页面也不会有很多上游链接，除非它是某个站点的子站点。排序技术是搜索引擎的核心技术，Google目前所使用的排序技术，已经不再是简单的PageRankPageRank小结优点：排序技术是搜索引擎的核心技术，G信息传播控制信息传播网络可看做一个无标度网络信息传播中两个要素接受信息的人媒体：电台、网站、报社等等；消息封锁切断信息流通的途径从而使得人们接受不到信息；消息封锁两种形式阻断人们接受信息的途径相当于破坏通信网络的边，这一方式效率较低；禁止媒体传播信息相当于破坏无标度网络的核心节点；实际上对于消息的封锁基本上都是禁止媒体进行传播。信息传播控制信息传播网络可看做一个无标度网络信息传播控制通信方式随着时代的不同而变化；当前的手段包括信件、电话、短信、面谈等等。每个人都可以很容易的和数十个甚至上百个人相联系并通信；这样的网络很难被切断成为不连通的，除非以某种方式强制关掉大部分通信设施，比如电台、报社、卫星、电话交换机、网络路由器等等。信息传播能力的度量可以用网络连通的可靠性等指标信息传播控制通信方式信息传播能力的度量可以用网络连通的可靠性网络传播行为网络结构研究固然重要，但其最终目的是通过研究结构来了解和解释基于这些网络之上的系统运作方式，进而预测和控制网络系统的行为；一般将这种建立在网络上的系统动态性质称为网络上的动力学行为，其涉及面非常之广，如：系统的渗流、同步、相变、网络搜索和网络导航等等。网络上的传播行为上述研究理论性较强，有一类应用性很强的网络行为研究已经日益引起人们的兴趣；如计算机病毒在计算机网络上的蔓延、传染病在人群中的流行、谣言在社会中的扩散等等；都是一种服从某种规律的网络上的传播行为。网络传播行为网络结构研究固然重要，但其最终目的是通过研究结构网络传播行为的研究最初且仍是主要的目的之一是为了认识疾病的传播机制；传统的网络传播模型大都基于规则网络；复杂网络研究的深入使我们重新审视这一问题；一般用节点表示疾病传染或感染的个体，如果两个个体之间可以通过某种方式直接发生传染与被传染关系，就认为这两个个体之间存在连接，这样就得到了传播网络的拓扑结构，进而可以建立相关模型来研究这种传播行为；显然，网络传播模型研究的关键是传播规则的制定和网络拓扑结构的选择。网络传播行为的研究最初且仍是主要的目的之一是为了认识疾病的传传播动力学基本研究对象是动力学模型在不同网络上的性质与相应网络的静态统计性质的联系。包括已知和未知的静态几何量；像传染病、谣言的传播过程的研究不能像其他一些学科一样，通过在人群中做实验的方式获得数据，相关数据、资料只能从已有的报告和记录中获取，而这些数据往往不够全面和充分，很难根据这些数据准确地确定某些参数，进行预报和控制工作；通过合理的网络模型产生数据并在此基础上进行理论和数值研究，是当前传播动力推进创新理论探索创新实践学的重要方法。传播动力学经典的疾病传播模型为SIS模型和SIR模型它们都将网络拓扑结构简单的假定为规则网络或者充分混合均匀网络，区别在于传播规则的不同；SIS模型每个节点处于两种状态：健康易受感染的和已被感染而具有传染性的；运行过程随机选择网络中一个或若干节点为染病节点，其余为健康节点；在每一时间步，染病节点的邻近节点以概率α变成染病节点，α称为传染率；同时每个染病节点都依某个事先设定的痊愈率β变成健康节点；上述演化规则在整个网络中被同时执行；经典的疾病传播模型为SIS模型和SIR模型SIS模型分析：传染率α越大，痊愈率β越小，疾病就越有可能感染更多的人，一般定义传染率和痊愈率的比值为传染强度λ=α/β；研究表明：经典SIS模型存在一个传染强度阈值λc>0，如果λ≥λc，疾病传染将一直持续下去达到一个稳定的范围，此时称染病节点数占总节点数的比例为疾病传染的波及范围；相反，如果λ<λc，疾病持续传染一段时间后最终将全部被治愈。SIR模型适合于染病者在治愈后可以获得终生免疫力，或者染病者几乎不可避免走向死亡的情形；SIR模型中，节点还可以处于另一种“免疫”状态，这种状态下的节点既不会被感染也不会感染其它节点，相当于将它从传播网络中剔除掉。SIS模型分析：SIR模型传统模型的问题传统的基于微分方程的传染病模型假设人群是充分混合的，染病个体原则上有机会感染任何易感的个体；这种感染总是通过某种“接触”完成的，因此如果两个个体可能接触就在相应的节点之间连一条边，那么传统的模型可以看做是对疾病在一个完全连通的社会接触网络上传播行为的描述；但是，社会接触网络具有不同于完全连通网络的结构特点；特别地，由统计物理学家发展出来的一些分析技术，例如逾渗理论、生成函数方法、平均场近似等等，使得分析具有复杂结构特性的真实网络上的传播行为称为可能；事实上，社会接触网络（复杂网络的一种）一些公认的结构特征被证明对传播规律有重大影响。小世界、无尺度等传统模型的问题小世界、无尺度等将疾病接触网络简单抽象为规则均匀连接网络并不符合实际情况；Moore等人研究了小世界网络中的疾病传播行为，发现疾病在小世界网络中的传播阈值明显比在规则网络中小，相同的传染强度下，经历相同时间后，疾病在小世界网络中的传染范围明显大于其在规则网络中的传染范围；即：相对于规则网络，疾病在小世界网络中更适宜传染；Paster-Satorras等研究了在无标度网络上的传染行为，结果令人震惊：无论是规则网络还是小世界网络，总存在正的传染强度阈值；无标度网络中疾病传染的阈值却非常接近于零；规则网络、小世界网络、无标度网络的疾病传播波及范围与传染强度关系示意图对SIR模型的分析也可以得到类似的结果将疾病接触网络简单抽象为规则均匀连接网络并不符合实际情况；规由于大量的实证研究表明真实世界网络既具有小世界性又具有无标度特性，上述结论是相当令人沮丧的；所幸的是，生活中无论是疾病还是计算机病毒的传染强度都非常小（λ<<1），危害不至于太大；然而，一旦疾病或病毒的传染强度较大时就必须高度重视其危害，对其的控制措施也不能完全依赖于医疗卫生条件的提高，而只能采取隔离保护某些节点、强行切断相关连接进而中断传染途径的方法来改变传播网络的拓扑结构；事实上，我们也正是采用上述方法成功的战胜了03年春夏之交席卷全国的SARS灾害。由于大量的实证研究表明真实世界网络既具有小世界性又具有无标度疾病传播机制的研究并非问题的全部，我们的最终目的是研究如何有效控制疾病传播；Pastor-Satorras等的研究表明：在资源有限的情况下，优先保护节点度数比较大的节点比随机选择节点进行保护效果要好得多；然而实际应用中，节点的度（传染期间与某个体有可能接触的个体数目）往往是很难统计的；在对性传播疾病的研究中，研究人员只能通过问卷和口头询问的方式获知患病者或高危人群的情况，但他们回答的可信度很低；有鉴于此，一些学者依据上述思想提出了一些具有实际意义的免疫策略。疾病传播机制的研究并非问题的全部，我们的最终目的是研究如何有随机免疫随机免疫是在网络中随机抽取一部分节点进行免疫；研究表明，采取这种策略的话，需要对网络中几乎所有的节点都进行免疫才能保证最终消灭传染病。选择免疫选择免疫是在网络中抽取度最大的节点进行免疫；针对BA模型，采取选择免疫策略，即使有效传播率变化，也可以只免疫很小一部分节点就保证消灭传染病。随机免疫熟人免疫由于选择免疫需要知道全局节点的度数情况，才能找到度数最大节点进行免疫，这在面对互联网等庞大的复杂网络时会导致难以操作；熟人免疫采取的是随机抽取一部分节点，然后对每个节点随机选一个与之相连的“邻居”节点来进行免疫；由于在无尺度网络中，度大的节点可以与非常多的节点相连，因此选择“邻居”免疫的话，碰到度大节点的概率会比碰到度小节点的概率大得多。所以熟人免疫要比随机免疫有效得多，只略差于选择免疫。熟人免疫网络传播行为的研究不仅在于分析疾病传播现象，而且可以用来分析其它许多事物的传播行为；例如，我们可以将其应用于社会网络上传播行为的研究，基本思路如下：首先从复杂网络理论出发抽象出社会网络的拓扑结构，然后按照一定的传播规则分析其传播机制，最后分析如何通过一定措施影响这种传播。如：知识或技术的扩散、网络新产品的扩散以及银行金融风险的传染等，它们既有联系又有区别，前两者的研究目的是为了促进传播；后者则是为了尽量避免传播。对复杂网络的认识，也可用于理解电脑病毒、疾病和时尚的传播。网络传播行为的研究不仅在于分析疾病传播现象，而且可以用来分析社区检测社区检测（communitydetection）又被称为是社区发现，它是用来揭示网络聚集行为的一种技术；社区检测实际就是一种网络聚类的方法，这里的“社区”可以将其理解为一类具有相同特性的节点的集合。网络中的社区结构近年来，社区检测得到了快速的发展，这主要是由于复杂网络领域中的大牛Newman提出了一种模块度（modularity）的概念，从而使得网络社区划分的优劣可以有一个明确的评价指标来衡量；一个网络不通情况下的社区划分对应不同的模块度，模块度越大，对应的社区划分也就越合理；如果模块度越小，则对应的网络社区划分也就越模糊。社区检测社区检测（communitydetection）又Newman提出的模块度计算公式：其中：m为网络中总的边数，A是网络对应的邻接矩阵，Aij=1代表节点i和节点j之间存在连边，否则不存在连边。ki为节点i的度数，Ci为节点i属于某个社区的标号，而δ(Ci,Cj)=1当且仅当Ci=Cj。模块度定义可以根据一个网络的空模型去进行理解：网络的空模型可以理解为只有节点而没有边，这时候一个节点可以和图中的任意其他节点相连，并且节点i和j相连的概率可以通过计算得到；随机选择一个节点与节点i相连的概率为ki/2m，随机选择一个节点与节点j相连的概率为kj/2m，那么节点i和节点j相连的概率为pipj=kikj/(4m2)，边数的期望值Pij=2mpipj=kikj/(2m)；所以模块度其实就是指一个网络在某种社区划分下与随机网络的差异，因为随机网络并不具有社区结构，对应的差异越大说明该社区划分越好。Newman提出的模块度计算公式：其中：m为网络中总的边数，Newman提出的模块度具有两方面的意义：模块度的提出成为了社区检测评价一种常用指标，它是度量网络社区划分优劣的量化指标；模块度的提出极大地促进了各种优化算法应用于社区检测领域的发展。许多优化算法以模块度为优化的目标方程进行优化，从而使得目标函数达到最大时得到不错的社区划分结果。常用的社区检测方法：基于图分割的方法，如Kernighan-Lin算法，谱平分法等；基于层次聚类的方法，如GN算法、Newman快速算法等；基于模块度优化的方法，如贪婪算法、模拟退火算法、Memetic算法、PSO算法、进化多目标优化算法等。模块度的概念也有弊端，比如分辨率限制问题等，国内有学者在模块度的基础上提出了模块度密度的概念，可以很好的解决模块度的弊端。Newman提出的模块度具有两方面的意义：模块度的概念也有弊复杂网络

ComplexNetwork复杂网络

ComplexNetwork为什么研究复杂网络？二十一世纪涌现的新现象互联网是怎样“链”接的？从一个页面到另一个页面，平均需要点击多少次鼠标？为什么研究复杂网络？二十一世纪涌现的新现象互联网是怎样“链美国航空网城市公共交通网为什么两者结构差异如此之大？这种差异是必然还是偶然的？城市交通涌堵的原因是什么？美国航空网城市公共交通网为什么两者结构差异如此之大？非典发现在广州，为什么却在北京爆发呢？传染病是怎样扩散和消失的？计算机病毒是怎样传播的？为什么“好事不出门，坏事行千里”呢？……互联网病毒传播网非典发现在广州，为什么却在北京爆发呢？计算机病毒是怎样传神经网络生态网络电力网络电信网络社交网络神经网络生态网络电力网络电信网络社交网络航空网络Facebook全球友谊图航空网络Facebook二十一世纪科学研究的特点二十世纪科学研究方法：分析、还原论；当分析为主要的研究方法时，人类关注如何将系统“分析”、“分解”，揭开系统的细部，了解是什么元素或部件组成了系统；忽视或破坏了这些元素是如何组合成系统的。二十一世纪（二十世纪末），系统成为主要的研究对象，整合成为主要方法；整合的方法在于了解细部以后，研究“如何组合”的问题，这导致复杂网络结构的研究；如：普列高津的耗散结构理论、哈肯的协同学、混沌和复杂系统理论、系统生物学、…二十一世纪科学研究的特点二十世纪科学研究方法：分析、还原论；复杂系统与复杂网络复杂系统与复杂网络的概念系统：集合（具体元素）+结构+功能系统的结构是什么？一切系统的基础结构都是网络；一切系统的核心结构都是逻辑网络；复杂系统的结构就是复杂网络。复杂网络是构成复杂系统的基本结构，每个复杂系统都可以看作是单元或个体之间的相互作用网络；复杂网络在刻画复杂性方面的重要