《复杂网络 课件.pptx》由会员分享，可在线阅读，更多相关《复杂网络 课件.pptx（109页珍藏版）》请在三一办公上搜索。
1、复杂网络Complex Network,为什么研究复杂网络？,二十一世纪涌现的新现象,互联网是怎样“链”接的？从一个页面到另一个页面，平均需要点击多少次鼠标？,美国航空网,城市公共交通网,为什么两者结构差异如此之大？这种差异是必然还是偶然的？城市交通涌堵的原因是什么？,非典发现在广州，为什么却 在北京爆发呢？传染病是怎样扩散和消失的？,计算机病毒是怎样传播的？为什么“好事不出门，坏事行千里”呢？,互联网,病毒传播网,神经网络,生态网络,电力网络,电信网络,社交网络,航空网络,Facebook全球友谊图,二十一世纪科学研究的特点,二十世纪科学研究方法：分析、还原论；当分析为主要的研究方法时，人类
2、关注如何将系统“分析”、“分解”，揭开系统的细部，了解是什么元素或部件组成了系统；忽视或破坏了这些元素是如何组合成系统的。二十一世纪（二十世纪末），系统成为主要的研究对象，整合成为主要方法；整合的方法在于了解细部以后，研究“如何组合”的问题，这导致复杂网络结构的研究；如：普列高津的耗散结构理论、哈肯的协同学、混沌和复杂系统理论、系统生物学、,复杂系统与复杂网络,复杂系统与复杂网络的概念 系统：集合（具体元素）+ 结构 + 功能系统的结构是什么？一切系统的基础结构都是网络；一切系统的核心结构都是逻辑网络；复杂系统的结构就是复杂网络。,复杂网络是构成复杂系统的基本结构，每个复杂系统都可以看作是单元
3、或个体之间的相互作用网络；复杂网络在刻画复杂性方面的重要性是由于结构决定功能的；复杂网络是研究复杂系统的一种角度和方法，它关注系统中因子相互关联作用的拓扑结构，是理解复杂系统性质和功能的基础。,具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络称为复杂网络。钱学森,复杂系统与复杂网络的主要特性,1) 开放性与环境和其它系统进行相互作用，交换物质、能量、信息，保持和发展系统内部的有序性与结构稳定性；在这种交换中，系统经历着从低级向高级、从简单到复杂、从无序向有序的不断优化的动态发展过程；虽然开放性是所有真实系统的基本属性，但这里的开放非指一般意义上的相互作用与交流，而开放的度量、性
4、质、强度对复杂系统的性态、演化具有决定性的意义。例：人、城市网络簇。,2)涌现性即内部元素通过非线性相互作用，在宏观层次上产生出新的、元素不具有的整体属性；虽然涌现同样是所有系统都具有的，但这里涌现意味着新的整体属性的产生。“整体大于部分之和”，如：大脑的神经网络系统3)演化性（不可逆性)即通过与所在环境中的其它系统的相互作用和内部的自组织，使系统发展到新的阶段，表现出阶段性、临界性，完成系统演化的生命周期。社会网络中的人、生物群体的自组织系统（鸟群）,4）复杂性结构复杂性：表现为多元性，非对称性，非均匀性，非线性分岔 (Bifurcation) 、混沌(Chaos)、分形Fractal；行为
5、复杂性：表现为学习，自适应性，混沌同步，混沌边沿，随机性等等；认识复杂性：又称为主观复杂性，它表现为不确定性，描述复杂性与计算复杂性等等。例：神经网络中的突触有强有弱，可抑制也可兴奋网络复杂性：即系统内部和系统之间的相互作用可以看成由节点、边（连接）构成的体系，出现网络复杂性、小世界特征与无标度特征等。,网络系统的复杂性,（1）结构复杂性网络连接结构错综复杂、极其混乱，同时又蕴含着丰富的结构：社区、基序、聚集性、生成规律性等等，而且网络连接结构可能是随时间变化的。包括：静态结构的复杂性和结构动态演化的复杂性。例如：互联网上每天都不停地有页面和链接的产生和删除。 例：神经系统由神经元互连形成，连
6、接以“突触连接结构”实现，突触有强弱、兴奋与抑制、不同的神经递质；连接不断改变，形成连接结构变化。（重边，加权等）,（2）节点复杂性节点的独立或固有特性网络中的节点可能是具有分岔和混沌等复杂非线性行为的动力系统；例如：基因网络中每个节点都具有复杂的时间演化行为；一个网络中可能存在多种不同类型的节点，比如控制哺乳动物中细胞分裂的生化网络就包含各种各样的基质和酶。关联引发的节点特性当关联失去时这类特性会在节点处消失或改变；例如：耦合神经元重复地被同时激活，那么它们之间的连接就会加强，这被认为是记忆和学习的基础。,（3）复杂网络之间相互影响的复杂性实际的复杂网络会受到各种各样因素的影响和作用。例如：
7、电力网络故障会导致Internet网速变慢，运输系统失控等一系列不同网络间的连锁反应。（4）网络分层结构的复杂性行政管理网络是具有层结构的，多数网络都有节点的分层结构，只是在许多网络中没有意识到是一种造成复杂性的重要结构。,对复杂网络的理解,复杂网络是二十一世纪科学研究的思想和理念，它启发我们用什么观点理解这个世界：整个世界以及组成世界的任何细部都是由网络及其变化形成的；复杂网络也是研究复杂系统的一种技术和方法，它关注系统中个体相互作用的拓扑结构，是理解复杂系统性质和功能的基本方法。,复杂网络研究简史,格尼斯堡七桥问题,Euler（17071783），瑞士数学家 ，图论之父,一笔画问题,随机图
8、理论20世纪60年代，由两位匈牙利数学家Erds和Rnyi建立的随机图理论（random graph theory）被公认为是在数学上开创了复杂网络理论的系统性研究。,Erds和Rnyi的最重要的发现：ER随机图的许多重要性质都是突然涌现的。即：对于任一给定的概率p，要么几乎每一个图都具有某个性质Q（比如说，连通性），要么几乎每一个图都不具有该性质。,在20世纪的后40年中，随机图理论一直是研究复杂网络的基本理论,小世界实验,大多数人都过这样的经历：碰到一个陌生人，同他聊了一会后发现你认识的某个人居然他也认识，然后一起发出“这个世界真小”的感叹；那么对于世界上任意两个人来说，借助第三者、第四者
9、这样的间接关系来建立起他们两人的联系平均来说最少要通过多少人呢？,哈佛大学美国社会心理学家斯坦利米尔格伦(Stanley Milgram)在1967年实验后得出结论：中间的联系人平均只需要5个，他把这个结论称为“六度分离”（Six Degrees of Separation）；六度分离：平均只要通过5个人，你就能与世界任何一个角落的任何一个人发生联系。这个结论定量地说明了我们世界的”大小”，或者说人与人关系的紧密程度；六度分离理论一直被作为社会心理学的经典范例之一。,小世界实验,米尔格伦的实验过程：他计划通过人传人的送信方式来统计人与人之间的联系；首先把信交给志愿者A，告诉他信最终要送给收信人
10、S；如果他不认识S，那么就送信到某个他认识的人B手里，理由是A认为在他的交集圈里B是最可能认识S的；但是如果B也不认识S，那么B同样把信送到他的一个朋友C手中，就这样一步步最后信终于到达S那里；这样就ABCS连成了一个链；斯坦利米尔格伦通过对这个链做了统计后做出了六度分离的结论。,尽管如此，实际上这个理论并没有得到严格的证实；美国心理学教授朱迪斯克兰菲尔德（Judith Kleinfeld）对米尔格伦最初的实验提出不同意见，因为她发现实验的完成率极低（实际上只有三分之一的信送到了收信人那里）。,小世界实验-Bacon数,截止到最近，世界电影史上共产生了大约23万部电影，78多万名电影演员，Ka
11、vin Bacon在许多部电影中饰演小角色；Virginia 大学的计算机专家Brett Tjaden设计了一个游戏，他声称电影演员Kevin Bacon是电影界的中心，定义了Bacon数：一个演员如果和Kavin Bacon一起演过电影，那么他（她）的Bacon数就为1；如果他（她）没有和Bacon演过电影，但是和Bacon数为1的演员一起演过电影，那么他的Bacon数就为2；依此类推。,小世界实验-Bacon数,网站http:/www.cs.virginia.edu/oracle/的数据库里总共存有有783,940个世界各地的演员的信息，以及231,088部电影信息；通过简单地输入演员名字
12、就可以知道这个演员的bacon数；比如输入Stephen Chow（周星驰）就可以得到这样的结果：周星驰在1991年的豪门夜宴(Haomen yeyan) 中与洪金宝(Sammo Hung Kam-Bo)合作；而洪金宝又在李小龙的最后一部电影，即1978年的死亡的游戏 （Game of Death） 中与 Colleen Camp 合作；Colleen Camp 在去年的电影Trapped 中与Kevin Bacon 合作；这样周星驰的Bacon数为3。,对78万个演员所做的统计：演员的最大Bacon数仅仅为8，平均Bacon数仅为2.948。,小世界实验-Erdos数,Paul Erdos(
13、1913-1996)：出生于匈牙利的犹太籍数学家，被公认为20世纪最伟大的天才之一；Erdos毕生发表的论文超过1500篇（在数学史上仅次于欧拉），超长的合作者名单，合作者超过450位，若加上别人所做但曾获他关键性提示之论文，则数万篇；他的研究领域主要是数论和组合数学，但他的论文中涵盖的非常多的学科；Mathematical Reviews 曾把数学划分为大约六十个分支，Erdos的论文涉及到了其中的40%.,小世界实验-Erdos数,定义Erdos数(Erdosnumber)的定义：Erdos本人之Erdos数为0；任何人若曾与Erdos合写过论文，则其Erdos数为1；任何人若曾与一位Er
14、dos数为l(且不曾与有更少的Erdos数)的人合写过论文，则他的Erdos数为2几乎每一个当代数学家都有一个有限的Erdos数，而且这个数往往非常小，小得出乎本人的预料；证明Fermat大定理的Andrew Wiles，他的研究方向与Erdos相去甚远，但他的Erdos数只有3，是通过这个途径实现的：Erdos-Andrew Odlyzko-Chris M.Skinner-Andrew Wiles.,小世界实验-Erdos数,Fields奖得主的Erdos数都不超过5（只有Cohen和Grothendieck的Erdos数是5）； Nevanlinna奖得主的Erdos数不超过3（只有Val
15、iant的Erdos数是3）；Wolf数学奖得主的Erdos数不超过6（只有V.I.Arnold是6，且只有Kolmogorov是5）；Steele奖的终身成就奖得主的Erdos数不超过4；其他领域的专家：比尔盖兹(Bill Gates)， 他的Erdos数是4，通过如下途径实现：Erdos-Pavol Hell-Xiao Tie Deng-Christos H. Papadimitriou-William H. (Bill) Gates； 爱因斯坦的Erdos数是2。,复杂网络研究,两篇开创性的文章可以看作是复杂网络研究新纪元开始的标志：美国康奈尔（Cornell）大学理论和应用力学系的博士
16、生Watts及其导师、非线性动力学专家Strogatz教授于1998年6月在Nature杂志上发表的“小世界”网络的集体动力学（Collective Dynamics of Small-World Networks）；美国Notre Dame大学物理系的Barabsi教授及其博士生Albert于1999年10月在Science杂志上发表的随机网络中标度的涌现（Emergence of Scaling in Random Networks）。这两篇文章分别揭示了复杂网络的小世界特征和无标度性质，并建立了相应的模型以阐述这些特性的产生机理。,1998，Watts和Strogatz：WS小世界网络,
17、D. J. Watts, and S. H. Strogatz, Nature, 393, 440-442 (1998).,60个节点组成的一个环每个节点与相邻的两个节点相连，计算网络的平均路径长度，即网络中所有节点对之间的路径长度的平均值。规则网络的平均路径长度为15，面对面的两个点之间的信息交流会需要较长时间。,将规则网络中少量与相邻节点连接的边改成长距离连接对图中5%的边（3条）进行重连后得到的网络，重连时3条边的一端被解开，重新连接到一个随机选择的节点上；重连后的网络与原来的规则网络的边数量一样多，但平均路径长度降到了9左右；节点数量越多，这个效应越明显。如果是有1000个节点的规则网
18、络，平均路径长度是250，如果5%的边重连，平均路径长度会降到20。,小世界性一个网络如果只有少量的长程连接，相对于节点数量来说平均路径却很短，则为小世界网络；自然、社会和技术演化产生的许多生物、群体和产品似乎都具有这种结构；这是为什么呢？有人认为至少有两种相互矛盾的选择压力导致了这种结果：在系统内快速传播信息的需要，以及产生和维持可靠的远程连接的高成本；小世界网络具有较短的平均路径长度，同时又只需相对较少的长程连接，从而解决了这两个问题。,反映到人类社会网络中，就是有一类人特别擅长交往，他们认识很多人，正是由于他们的存在，才使得六度分隔成为可能。,无标度网络（Scale-free netwo
19、rk）,六度分隔告诉我们，人与人建立链接不是一个完全随机的过程；“人以类聚，物以群分”，复杂网络中的节点往往也呈现出集群特性：例如，社会网络中总是存在熟人圈或朋友圈，其中每个成员都认识其他成员。,一种网络聚集现象,集群程度的意义是网络集团化的程度，这是一种网络的内聚倾向；连通集团反映的是一个大网络中各集聚的小网络分布和相互联系的状况。例如，它可以反映这个朋友圈与另一个朋友圈的相互关系。,每个人认识的人数分布符合二八定律,无标度网络（Scale-free network）,现实世界的网络大部分都不是随机网络，少数的节点往往拥有大量的连接，而大部分节点却很少，一般而言他们符合zipf（其普夫）定律
20、，(即：80/20马太定律)；现实中的交通网，电话网和Internet都是无标度网络；在这种网络中，存在拥有大量连接的集散节点，比如交通枢纽就是这样的节点。人们给具有这种性质的网络起了一个特别的名字无标度网络。这里的无标度是指网络缺乏一个特征度值（或平均度值），即节点度值的波动范围相当大。,在一般的随机网络（如ER模型）中，大部分的节点的度都集中在某个特殊值附近，形成泊松分布。,无标度网络（Scale-free network）,真实社会化网络的建立是一个什么过程呢？Barabsi, Albert-Lszl提出了他们的方法，为了构造出符合幂律（Power Law）分布（即二八定律）的网络，他们
21、给出了一个网络的构建过程，并把这种网络称之为无尺度网络：网络是动态增长的，不断有新的节点加入，而不是随机网络中那样所有节点都已给出，仅仅是随机建立连接；优先情结，新增的点并不是如随机网络中那样和其他点有相同的概率建立建立连接，它会有更大的概率和已有很多连接的节点建立连接。,从最初的两个点开始，每次新增的一个绿色节点有更高的概率和已经有很多连接的节点建立连接；优先情节在现实中也是存在的，大多数的普通人总是期望和少数的活跃用户建立间接。,一个随机网络和一个无尺度网络，右边的黑色点就是活跃用户。,无标度网络的定义按生长方式定义网络的每个节点的连接数与此节点产生新连接的概率成增函数关系；按分布定义网络
22、中有一定数量的连接的节点数与此连接数量成减函数。,节点连接数的zipf分布,符合zipf分布的无标度网络,1999，Barabasi和Albert ：BA无标度网络,A.-L. Barabasi and R. Albert, Science, 286, 509 (1999).,幂律分布（一般是负指数）,网络称之为无尺度网络，是相对于有尺度网络来讲的；随机网络中每个节点有的连接数符合正态分布（左图）因为有大多数节点的连接数居中，于是我们可以称这个中值为这个网络的尺度；无尺度网络的分布符合幂律分布（右图）大多数人只有很少的连接，而有少数人有很多的连接，这个网络没有一个尺度来衡量网络中节点的距离，于
23、是称之为无尺度网络。,无尺度网络的意义新用户建立连接时候的有优先情节，它更倾向于与活跃用户建立连接；拥有有大量连接的活跃用户，随着网络规模的增加，连接会越来越多，也就是富者愈富；,对于社交网站：建立一个完全草根化的SNS（社交网站）是不现实的，因为人们需要活跃用户，活跃用户对SNS的拉动不容忽视；SNS中20%的人产生了80%的连接，这些人是整个网络的核心，关注这部分人的行为、喜好、特点，设计有针对性的产品会产生更好的效果；另外80%的人在网络中处于失势的地位，虽然他们有出声的权利，但是他们的声音很难成为主流。,Internet就是无尺度网络；分析Internet的度分布，Internet连接
24、有两种：入连接和出连接；如果我的网页有一个连接指向你的网页，而你却没有指向我，则我有一个出连接而你则有一个入连接；将网页的入连接数量称为网页的入度。有几个研究团队都发现网页入度分布可以用非常简单的规则来描述：入度为k的网页数量正比于1/(k2.3)。,为了解释为何Internet是”无尺度“，用三种不同的尺度画出遵循上面的规则的入度分布；x轴为入度，y轴为频率。,入度1000-10000 频率0-0.000001,入度10000-100000 频率0-0.00000001,入度100000-1000000频率0-1*10(-10),无尺度就是“在不同尺度下具有不变性”,对无标度网络的理解,在做
25、实验之前，很多人都认为：连接数k应当服从泊松分布或正态分布，即每个网站的被访问量差异不会太大，就像人类身高差异不会太大那样；Barabasi等人设计了一种软件，可以从一个节点跳到另一节点，收集并记录网上的所有连接。在对几十万个节点进行统计后发现：在绝大多数网站的连接数很少的情况下，却有极少数网站拥有高于普通网站百倍、千倍甚至万倍的连接数；就像在茫茫人海中突然发现若干身高数百尺的巨人那样，令人意外。巨人的身高之大，已不能用普通人高度的尺度来度量，于是想出了“无尺度”的一词，反映少数节点连接数超乎异常的事实。实验结果用数学语言表达为：出现连接数为k的概率 p(k)，反比于k的n次方；其中，n称为幂
26、数，它是很接近于2的一个常数；也就是说，WWW巳成为无尺度网络（scale free network）。,无尺度现象的成因,Barabasi等人认为优先连接性和网络的成长性是两个起因成长性是指网民网页急剧增加，优先连接性是指新网民总是优先选择前人经常访问的网站；随着时间的演进，某些热门的网站愈加热门，不知名的网站愈加冷门。信息社会同时兼有“大世界”与“小世界”两种属性网民、网页、带宽随时间快速成长，使互联网巳成为全球范围内的巨大网络；互联网是为一个个人提供服务的，每个人一天之内所能接受的信息，受到生理带宽与生理精力的限制，又是一个不随时间增长的有限世界；大世界与小世界之间，技术世界与人文世界之
27、间存在明显的差异与矛盾。,无尺度现象的成因,信息学家认为无尺度现象反映了信息共享和物质共享存在本质差异信息共享的本质：信源母体不限数量（scale free）的复制（copy）；物质共享的本质：只是资源母体有限量的瓜分（share）。,随机网络与无尺度网络的抗毁性：随机网络如果有大量结点发生故障，可能导致系统分散成多个孤岛；无尺度网络承受随机故障后的抗毁性较强，但是对于协同式攻击则更加脆弱。,复杂网络研究的简史列表,不同领域的复杂网络,社会网：演员合作网、友谊网、姻亲关系网、科研合作网、Email网生物网：食物链网、神经网、新陈代谢网、蛋白质网、基因网络信息网络：WWW、专利使用、论文引用、信
28、息共享技术网络：电力网、Internet、电话线路网交通运输网：航线网、铁路网、公路网、自然河流网,复杂网络研究内容,1）复杂网络模型典型的复杂网络：随机网、小世界网、无标度网等；实际网络及其分类。2）网络的统计量及与网络结构的相关性度分布的定义和意义，聚集性、连通性的统计量及其实际意义等。3）复杂网络性质与结构的关系同步性、鲁棒性和稳定性与网络结构的关系。4）复杂网络的动力学信息传播动力学、网络演化动力学、网络混沌动力学。,5）复杂网络的复杂结构社团结构、层次结构、节点分类结构等。6）网络控制关键节点控制、主参数控制和控制的稳定性和有效性。7）复杂网络建模机理建模、数据建模和实际系统的复杂网
29、络正向与逆向建模。8）复杂逻辑网络逻辑与高阶逻辑定义、分类、判定算法，高阶逻辑的实际意义等等。,复杂网络研究,突破性进展的主要原因 越来越强大的计算设备和迅猛发展的Internet，使得人们开始能够收集和处理规模巨大且种类不同的实际网络数据； 学科之间的相互交叉使得研究人员可以广泛比较各种不同类型的网络数据，从而揭示复杂网络的共性； 以还原理论和整体论相结合为重要特色的复杂性科学的兴起，也促使人们开始从整体上研究网络的结构与性能之间的关系。,主要研究目标发现：揭示刻画网络系统结构的统计性质，以及度量这些性质的合适方法；建模：建立合适的网络模型以及理解网络的统计性质的意义与产生机理；分析：基于单
30、个节点的特性和整个网络的结构性质分析与预测网络的行为；控制：提出改善已有网络性能和设计新的网络的有效方法，特别是稳定性、同步和数据流通等方面。,复杂网络中的基本概念,度(degree)：节点 i 的度 ki 定义为与该节点连接的其他节点的数目；直观上看，一个节点的度越大就意味着这个节点在某种意义上越“重要”（“能力大”）；网络的平均度：网络中所有节点的度和的平均值；度分布函数p(k)：随机选定节点的度为k的概率；,复杂网络中的基本概念,节点的聚类系数（簇系数）：简单图中，设节点v的邻集为N(v)，|N(v)|=ki，则节点v的聚类系数定义为这ki个节点之间存在边数Ei与总的可能边数ki(ki-
31、1)/2之比，即：Ci=2Ei/ki(ki-1) 节点v的邻点间关系的密切程度。,在随机网络中，当P较小时(P0.01)，最短路径平均长度急剧下降，而聚类系数几乎没有变化。这些网络具有较短的特征路径长度和较大的聚类系数，称其为“小世界网络”。,网络的聚类系数C：所有节点i的聚类系数Ci的平均值，（0C1）C=0 网络中所有节点都是孤立点C=1 网络中任意节点间都有边相连说明网络节点间联系的密切程度，体现网络的凝聚力；许多大规模的实际网络都具有明显的聚类效应。,事实上，在很多类型的网络(如社会关系网络)中，你的朋友同时也是朋友的概率会随着网络规模的增加而趋向于某个非零常数，即当N时，C=O(1)
32、；这意味着这些实际的复杂网络并不是完全随机的，而是在某种程度上具有类似于社会关系网络中“物以类聚，人以群分”的特性。,最短路径（Shortest path）：两个节点之间边数最少的路径，最短路径的长度称为两点间的距离，用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、33,介数（Betweenness）,点介数：网络中通过该节点的最短路径的条数；如果一对节点间共有B条不同的最短路径，其中有b条经过节点i，那么节点i对这对节点的介数的贡献为b/B；把节点i对所有节点对的贡献累加起来再除以节点对总数，就可得到节点i的介数。边介数：网络中通过该边的最短路径的条数；所有节点对的最短路径中经过该边的数量比例。,介数（Betweenness）,说明：介数反映了节点或边的作用和影响力；介数越大，说明经过该节点（边）的最短路径的数目越多；在信息传播过程中，通过该节点（边）的信息量就越大，于是就越容易发生拥塞；研究表明：节点介数与度之间有很强的相关性，不同类型的网络，其介数
34、分布也大不一样。,网络介数 网络点介数，网络边介数： 所有节点（边）的平均介数 网络介数说明了网络的什么性质？,核数一个图的k-核：反复去掉图中度小于等于k 的节点后，所剩余的子图，若一个节点存在于k-核，而在(k+1)-核中被去掉，则此节点核数为k；例：所有度为1的节点的核数必为0；节点核数中的最大值称为网络图的核数；节点核数可以表明节点在核中的深度；即便一个节点的度数很高，它的核数也可能很小；例如：包含N个节点的星型网络的中心节点的度数为N-1，但它的核数为0。,思考：目前刻划复杂网络的统计量有很多；如：聚类系数、平均路径长度、平均度、介数、核数等。问题：能不能用一个或尽可能少的统计量来综
35、合刻划复杂网络的结构呢？用多少相互独立的统计量刻画复杂网络的结构是完备的？,复杂寓于简单,在不同领域许多系统都呈自相似结构，即局部与总体相似。例如国家、河流、行星系等都是这样；“分形”是研究自相似结构的。分形的构成常遵循一种法则：复杂的分形外形是由简单的规则重复迭代生成的；以Koch曲线为例：将一直线三等分，中间的1/3用一等边三角形取代。直线变为4段等长折线。每段直线再按此规则变化,一直重复下去，即生成Koch曲线。,复杂网络研究方向,从统计物理的角度研究的核心思想是研究一个系统所有节点的统计规律；大部分复杂网络的统计量也是从这里出来的可根据百度百科对统计物理粗浅的说明：“统计物理学 sta
36、tistical physics 根据对物质微观结构及微观粒子相互作用的认识，用概率统计的方法，对由大量粒子组成的宏观物体的物理性质及宏观规律作出微观解释的理论物理学分支，又称统计力学 ；“大量”是以1摩尔物质所含分子数（其数量级为1023个）为尺度的。” 但是，从统计物理的角度研究复杂网络或复杂系统可能有个问题，就是现在研究系统中节点的个数都称不上“大量”，甚至可以预想的将来某些系统也不会达到这个量级，有限数据效应可能会导致无标度分布的度大节点在网络中占统治地位，结果使某些看似合情合理的统计性质并不能反映网络的真实性质。,复杂网络研究方向,从系统科学的角度系统科学研究复杂网络就是将复杂网络中
37、的所有节点作为一个大系统进行研究；但问题是这样的，将一个复杂系统抽象成一个网络进行研究本来就是无法从系统论对某个系统进行详细研究的无奈简化，也就是说，对某个系统无法进行直接研究；系统中各个节点相互交互的某种关系能否抽象为一种链接关系，然后集中精力来研究这种链接关系，那么怎么来研究这种链接联系呢，系统科学没告诉我们，能否从系统科学的角度来“发明”一种复杂网络的研究方法？但是系统科学目前还不能提供比较好的方法论，现在仅仅知道节点之间是相互关联的，一个整体的各个部分不能像以前那样分割出来进行研究，这也是系统科学对其他各个学科门类的贡献。,复杂网络研究方向,从知识发现或数据挖掘的角度这方面的研究目前主
38、要集中在在线社会网络（SNS）研究方面，实际上这10年来复杂网络方面有重大意义的研究都集中在这方面，尽管某些有用特征（如无标度和小世界特性）挖掘出来以后后面会有相应的在统计物理和系统科学方面的理解，比如有好多这方面的建模工作；但是实际数据中得到的规律是最重要的，复杂网络的兴起实际上也是信息获取便捷的产物，本质上使用复杂网络来研究实际系统是数据挖掘的一种形式和方法，尽管这种方法的直观性是它的天然优势，但并不代表这种方法是最有效的，随着数据挖掘技术的不断深化，也许对于某些研究基于数据本身的挖掘方法的能力会强于先将原始数据的某种关系转变为一种网络关系，再使用复杂网络进行分析。,PageRank算法,
39、Web上超链接结构是个非常丰富和重要的资源，如果能够充分利用的话，可以极大的提高检索结果的质量；Sergey Brin(谢尔盖布林 )和Lawrence Page(拉里佩奇)在1998年提出了PageRank算法，同年J. Kleinberg（J克莱因伯格）提出了HITS算法；Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd, The PageRank Citation Ranking: Bringing Order to the Web, 1998, http:/www-db.stanford.edu/backrub/pag
40、eranksub.ps 为了更高效地计算 PageRank，算法改良以后的一篇论文：Taher H. Haveliwala, Efficient Computation of PageRank, Stanford Technical Report, 1999；http:/dbpubs.stanford.edu:8090/pub/1999-31 PageRank(TM) 是美国 Google 公司的登记注册商标。,Google查询过程,PageRank?,Google查询的全过程通常不超过半秒时间，但在这短短的时间内需要完成多个步骤，然后才能将搜索结果交付给搜索信息的用户。,PageRank的提
41、出,Google的创始人之一Larry Page于1998年提出了PageRank，并应用在Google搜索引擎的检索结果排序上，该技术也是Google早期的核心技术之一；Larry Page是Google的创始首席执行官，2001年4月转任现职产品总裁。他目前仍与Eric Schmidt和Sergey Brin一起共同负责 Google的日常运作。他在斯坦福大学攻读计算机科学博士学位期间，遇到了Sergey Brin，他们于1998年合伙创立Google。,Google的网页排序,在Google中搜索“体育新闻”,Google的网页排序,在Google中搜索“体育新闻”搜索引擎工作的简要过程
42、：针对查询词“体育新闻”进行分词“体育”、“新闻”；根据建立的倒排索引，将同时包含“体育”和“新闻”的文档返回，并根据相关性进行排序；这里的相关性主要是基于内容的相关性；但是会有一些垃圾网页，虽然也包含大量的查询词，但却并非满足用户需要的文档。,因此，页面本身的重要性在网页排序中也起着很重要的作用,一个网页中虽然出现了四次“体育新闻”但却不是用户所需要的,A,B,网页是节点，网页间的链接关系是边,Google的网页排序,如何度量网页本身的重要性呢？互联网上的每一篇html文档除了包含文本、图片、视频等信息外，还包含了大量的链接关系，利用这些链接关系，能够发现某些重要的网页；直观地看，某网页A链
43、向网页B，则可以认为网页A觉得网页B有链接价值，是比较重要的网页；某网页被指向的次数越多，则它的重要性越高；越是重要的网页，所链接的网页的重要性也越高。,Google的网页排序,如何度量网页本身的重要性呢？比如，新华网体育在其首页中对新浪体育做了链接，人民网体育同样在其首页中对新浪体育做了链接；可见，新浪体育被链接的次数较多；同时，人民网体育和新华网体育也都是比较“重要”的网页，因此新浪体育也应该是比较“重要”的网页。,新华网体育,人民网体育,链向网页E的链接远远多于链向网页C的链接，但网页C的重要性却大于网页E；这是因为因为网页C被网页B所链接，而网页B有很高的重要性。,Google的网页排
44、序,一个更加形象的图,什么是PageRank,PageRank一种在搜索引擎中根据网页间相互链接关系计算网页排名的技术；是Google用来标识网页的等级或重要性的一种方法；级别从1到10级，PR值越高说明该网页越受欢迎（越重要）；,查看某站点PageRank值，安装GOOGLE工具条并启用PageRank特性，或者在firefox安装SearchStatus插件。,PageRank近似于一个用户，是指在Internet上随机地单击链接将会到达特定网页的可能性；思想：能够从更多地方到达的网页更为重要，因此具有更高的PageRank。,PageRank 的核心思想,PageRank 基于“从许多优
45、质的网页链接过来的网页，必定还是优质网页”的回归关系，来判定所有网页的重要性。,链入链接数 (单纯的意义上的受欢迎度指标) 链入链接是否来自推荐度高的页面 (有根据的受欢迎指标) 链入链接源页面的链接数 (被选中的几率指标),因此，如果从类似于 Yahoo! 那样的 PageRank 非常高的站点被链接的话，仅此网页的 PageRank 也会一下子上升；相反地，无论有少链入链接数，如果全都是从那些没有多大意义的页面链接过来的话，PageRank 也不会轻易上升。,PageRank简单计算,假设一个由只有4个页面组成的集合：A、B、C和D，如果所有页面都链向A，那么A的PR（PageRank）值
46、将是B，C及D的和； 继续假设B也有链接到C，并且D也有链接到包括A的3个页面，由于一个页面不能投票2次，所以B给每个页面0.5票。以同样的逻辑，D投出的票只有1/3算到了A的PR值上；即：链出总数平分一个页面的PR值；,PageRank的简化模型,把互联网上的各网页之间的链接关系看成一个有向图；假设浏览的下一个网页链接来自于当前网页。建立简化模型：任意网页Pi的PageRank值可表示为：Bi为所有链接到网页i的网页集合；Lj为网页j的对外链接数（出度）。,简化模型面临的缺陷,Rank Leak一个独立的网页如果没有外出的链接就产生等级泄漏。,Rank Sink整个网页图中的一组紧密链接成环
47、的网页如果没有外出的链接就产生Rank sink。,PageRank的随机浏览模型,假定一个上网者从一个随机的网页开始浏览，上网者不断点击当前网页的链接开始下一次浏览。但是，上网者最终厌倦了，开始了一个随机的网页；随机上网者用以上方式访问一个新网页的概率就等于这个网页PageRank值； 这种随机模型更加接近于用户的浏览行为； 一定程度上解决了rank leak和rank sink的问题； 保证pagerank具有唯一值。,设定任意两个顶点之间都有直接通路，在每个顶点处以概率d按原来蓝色方向转移，以概率1-d按红色方向转移。,随机浏览模型的邻接表表示,由于网页数目巨大，网页之间的连接关系的邻接
48、矩阵是一个很大的稀疏矩阵，采用邻接表来表示网页之间的连接关系，随机浏览模型的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存在唯一解，并且经过不断的重复迭代计算，这些页面的P
49、R值会趋向于正常和稳定。,PageRank的计算,互联网是一个有向图；每一个网页是图的一个顶点；网页间的每一个超链接是图的一个有向边；用邻接矩阵来表示图，即：定义邻接矩阵为G，若网页j到网页i有超链接，则 ；反之 ；显然，如果网页有N个，则矩阵为NN 的0、1方阵。,多个网页相互链接的图对应的邻接矩阵（这里将0,1值用二值图像显示，黑色代表0，白色代表1）,PageRank的计算,定义邻接矩阵为G，若网页j到网页i有超链接，则 ；反之， ；记矩阵G的列和、行和分别是它们分别给出了页面j的链出链接数目和链入链接数目；假设我们在上网的时侯浏览页面并选择下一个页面，这个过程与过去浏览过哪些页面无关，
50、而仅依赖于当前所在的页面，那么这一选择过程可以认为是一个有限状态、离散时间的随机过程，其状态转移规律用Markov链描述；定义转移概率矩阵,PageRank的计算,根据Markov链的基本性质，对于正则Markov链，存在平稳分布 ，满足 表示在极限状态（转移次数趋于无限）下各网页被访问的概率分布； 定义为网页的PageRank向量， 表示第i个网页的PageRank值。,求矩阵A的特征值1对应的特征向量,某7个网页之间的链接关系图,PageRank结果的评价,将 PageRank 的评价按顺序排列(PageRank小数点3位四舍五入)：,页面之间相互关系及状态转移图,PageRank结果的评
