分子生物网络分析(崔颖)第2章 网络拓扑基本模型及其性质.ppt
《分子生物网络分析(崔颖)第2章 网络拓扑基本模型及其性质.ppt》由会员分享,可在线阅读,更多相关《分子生物网络分析(崔颖)第2章 网络拓扑基本模型及其性质.ppt(256页珍藏版)》请在三一文库上搜索。
1、第二章 网络拓扑基本模型及其性质,教 师:崔 颖 办公室:外语学馆412室 E- mail: ,学习目标,理解网络结构和网络行为之间的关系。 对实际网络结构有深入的了解,考虑改善网络的行为。 在此基础上建立合适的网络结构模型。 本章介绍几类基本的模型:规则网络、随机图、小世界网络、无标度网络、等级网络等模型。,引言,Watts和Strogatz关于小世界网络的工作; Barabasi和Albert关于无标度网络的开创性工作。 人们对存在于不同领域的大量实际网络的拓扑特征进行了广泛的实证性研究。 从不同角度提出了各种各样的网络拓扑结构模型。,第二章 网络拓扑基本模型及其性质,2.1规则网络模型
2、2.2随机网络模型 2.3小世界网络模型 2.4无标度网络模型 2.5局域世界演化模型 2.6模块性与等级网络 2.7超家族 2.8复杂网络的自相似性,2.1.规则网络,规则网络(Regular Network)的特征: 如果系统中节点及其与边的关系是固定的,每个节点都有相同的度数,就可以用规则图来表示这个系统。 这样的网络就称为规则网络。,2.1.规则网络,定义:全局耦合网络(globally coupled network),任意两个点之间都有边直接相连。,全局耦合网络 -完全连接,2.1.规则网络,定义:最近邻耦合网络(nearest-neighbor coupled network),
3、每一个节点只和它周围的邻居节点相连。,最近邻耦合网络 -最近邻连接,2.1.规则网络,定义:星形耦合网络(star coupled network),有一个中心点,其余N-1个点都只与这个中心点连接。,星形耦合网络 -星形连接,2.1.规则网络,全局耦合网络 任意两个点之间都有边直接相连,最近邻耦合网络 每一个节点只和它周围的邻居节点相连,星形耦合网络 有一个中心点,其余N-1个点都只与这个中心点连接,1.全局耦合网络(Globally coupled network),平均路径长度为L=1 聚类系数为C=1 度分布:Delta函数,请同学分析全局耦合网络的 拓扑属性。如:平均路径长度, 聚类
4、系数,服从哪种分布。,全局耦合网络(Globally coupled network),具有N个节点的全局耦合网络有N(N-1)/2条边; 但是大多数实际网络是稀疏的,边数一般至多是O(N)而不是O(N2),全局耦合网络 -完全连接,1.全局耦合网络(Globally coupled network),请计算全局耦合网络的紧密度、拓扑系数、介数。,2.最近邻耦合网络 (Nearest-neighbor coupled network),最近邻耦合网络:每个节点都与它左右的K/2个节点相连,K是一个偶数。 对大的N, K, 有:聚类系数C3/4, 平均路径长度L无穷大。,请同学分析最近邻耦合网络
5、的 拓扑属性。如:平均路径长度, 聚类系数,服从哪种分布。,2.最近邻耦合网络 (Nearest-neighbor coupled network),一般地,规则网络具有大的聚类系数和大的平均距离。 这类网络是高度聚类的但不是一个小世界网络。,2.最近邻耦合网络 (Nearest-neighbor coupled network),请计算最近邻耦合网络的紧密度、拓扑系数、介数。,3.星形耦合网络(star coupled network),请同学分析星形耦合网络的 拓扑属性。如:平均路径长度, 聚类系数,服从哪种分布。,3.星形耦合网络(star coupled network),星形耦合网络
6、是比较特殊的一类网络。 有些文献中定义如果一个节点只有一个邻居节点,那么该节点聚类系数定义为1. 有些研究文献则定义只有一个邻居节点的节点聚类系数为0,依此定义,星形网络的聚类系数为0.,3.星形耦合网络(star coupled network),请计算星形耦合网络的紧密度、拓扑系数、介数。,2.1.规则网络-小结,全局耦合网络:聚类系数高,平均路径长度小,反映了网络的高度聚类和小世界性质 最近邻耦合网络:聚类系数高,平均路径长度大,此类网络具有高度聚类但是不是小世界网络。 星形耦合网络:聚类系数低(高),平均路径长度小,此类网络为小世界网络,2. 2随机网络,与完全规则网络相反的是完全随机
7、网络。 典型的模型是Erds和Rnyi于40多年前开始研究的ER随机图模型。,2. 2随机网络,假设有大量的纽扣(N1)散落在地上,并以相同的概率P给每对纽扣系上一根线。 这样就会得到一个有N个点,约PN(N-1)/2条边的ER随机图的实例。,例如:节点数N=10,P值分别为:0,0.1,0.15,0.25 则可以得到ER随机图的实例。 请同学给出此实例演化过程。,2. 2随机网络,随机演化示意图:N=10,P=0;P=0.1;P=0.15,P=0.25,2. 2随机网络,ER随机图具有的性质:涌现或相变性质 ER随机图的许多重要性质都是突然涌现的:也就是说,对于任一给定的概率P,要么几乎每一
8、个图都具有某个性质Q(比如,连通性),要么几乎每一个图都不具有该性质。,2. 2随机网络,例如,对于上述纽扣网络,如果你捡起一个纽扣,那么将有多少个纽扣也会跟着被拎起来呢? 结果显示,如果概率P有大于某个临界值Pc(lnN)/N,那么几乎每一个随机图都是连通的,也就是说,随机地捡起一个纽扣都会拎起地上几乎所有的纽扣。,2. 2随机网络,ER随机图的平均度=P(N-1)PN。 设LER是ER随机图的平均路径长度。直观上,对于ER随机图中随机选取的一个点,网络中大约有 LER个其他的点与该点之间的距离等于或非常接近LER。因此,LERlnN/ln。,2. 2随机网络,这种平均路径长度为网络规模的对
9、数增长函数的特征就是典型的小世界特征。 因为当lnN的值随N增长得很慢,这就使得即使是规模很大的网络也可以具有很小的平均路径长度。,2. 2随机网络,ER随机图中两个节点之间不论是否具有共同的邻居节点,其连接概率均为P。 因此,ER随机图的聚类系数C=P=/N1,这意味着大规模的稀疏ER随机图没有聚类特征。 现实中的复杂网络一般都具有明显的聚类特性,也就是说,实际的复杂网络的聚类系数要比相同规模的ER随机图的聚类系数高得多。,2. 2随机网络,如果节点不是按确定的规则连线,譬如按纯粹的随机方式连线,所得到的网络就成为随机网络(random network)。 如果节点按照某种(自)组织原则方式
10、连线,将演化成各种不同的网络,称为复杂网络(complex network)。,2. 2随机网络,2. 2随机网络,随机网络特征:如果系统中节点及其与边的关系不确定,就只能用随机网络来表示这个系统。 1.节点确定,但边以概率p任意连接; 2.节点不确定,点边关系也不确定,2. 2随机网络,布朗运动,2. 2随机网络,随机网络的度分布服从泊松分布 平均度:k=p(N-1)p*N 平均路径长度Lln(N)/ln 聚类系数: C=p 1 (由于极度稀疏) 一般地,随机网络具有低的 聚集程度和小的平均距离。,2. 2随机网络,ER随机图作为实际复杂网络的模型存在明显的缺陷。 ER随机图理论一直是研究复
11、杂网络拓扑的基本理论,其中一些基本思想在目前的复杂网络理论研究中仍然很重要。 可以参考Bollobs的著作。,2. 2随机网络,从多角度对ER随机图进行扩展以使其更接近真实的网络。 一个推广就是具有任意给定度分布的广义随机图(generalized random graph)。,2. 2随机网络,给定一个度分布P(k),它表示了网络中度为k的节点所占的比例。 基于这一分布按相同概率产生多个度序列为ki(i=1,2,.,N)的由N个节点组成的网络。 这些网络模型的集合称为配置模型(configuration model),详细介绍参见Newman的综述。,2.3 小世界网络,最近邻耦合网络具有高
12、聚类特性,但平均路径长度较大; 随机网络具有小的平均路径长度,但却没有高聚类特性; 这两类网络模型都不能再现真实网络的一些重要特征。,2.3 小世界网络,毕竟大部分实际网络既不是完全规则的,也不是完全随机的。 是否存在一个同时具有高的集聚程度,以及小的最短路径的网络呢?,2.3 小世界网络,Watts和Strogtz于1998年引入了一个有趣的小世界网络模型,称为WS小世界模型,作为从完全规则网络向完全随机图的过渡。 发表在Nature上,常称为:WS model。,2.3 小世界网络,WS小世界模型构造算法如下: 1.从规则图开始:考虑一个含有N个点的最近邻耦合网络,它们围成一个环,其中每个
13、节点都与它左右的各K/2节点相连,K是偶数。 2.随机化重连:以概率P随机地重新连接网络中的每个边,即将边的一个端点保持不变,而另一个端点取为网络中随机选择的一个节点。其中规定,任意两个不同的节点之间至多只能有一条边,并且每一个节点都不能有边与自身相连。,2.3 小世界网络,对于传染病模型, 平均集聚程度对应于传播的广度,平均最短距离代表的是传播的深度。 因此,如果实际网络同时存在宽的广度和大的深度的话,在这样的网络上的传染病传播显然将大大高于规则网络与随机网络。,2.3 小世界网络,通过调节P的值就可以控制从完全规则网络到完成随机网络的过渡。,1.WS小世界模型,方法:Watts和Strog
14、atz 发现,只需要在规则网络上稍作随机改动就可以同时具备以上两个性质。 改动的方法是,对于规则网络的每一个顶点的所有边,以概率p 断开一个端点,并重新连接,连接的新的端点从网络中的其他顶点里随机选择,如果所选的顶点已经与此顶点相连,则再随机选择别的顶点来重连。 形成机制: 规则网络以概率p 断开一个端点随机连接,当p=0时,对应的规则网络。两个节点间的平均距离线性地随N增长而增长,集群系数大 当p=1时,系统变为随机网络。对数地随N增长而增长,且集群系数随N减少而减少。 在p等于(0,1)区间任意值时,模型显示出小世界特性,约等于随机网络的值,网络具有高度集群性。,1.WS小世界模型,1.W
15、S小世界模型,WS小世界模型的随机化重连过程:,WS小世界模型性质: 1.度与度分布 WS小世界由于没有改变原来网络的连线数目所以平均度仍为K,但是由于改变的旧线的连接方式,所以每个节点的度数不再保持常数。 WS小世界网络的度分布形态与随机网络的度分布形态相似。,1.WS小世界模型,1.WS小世界模型,2.WS小世界的平均路径长度 迄今还没有精确解析表达式。 不过,利用重正化群方法得到如下公式: 小世界网络的路径长度分布介于最小的路径长度1和最大路径长度N/2K之间,而且随着p的增长,路径长度分布的峰值越来越高。,1.WS小世界模型,1.WS小世界模型,2.NW小世界模型,WS小世界模型构造算
16、法中的随机化过程有可能破坏网络的连通性。 另一个研究较多的小世界模型由Newman和Watts稍后提出的,称为NW小世界模型。 该模型是通过用“随机化加边”取代WS小世界模型 构造中的“随机化重连”而得到的。,2.NW小世界模型,NW小世界模型构造算法: 1.从规则图开始:考虑一个含有N个点的最近邻耦合网络,它们围成一个环,其中每个节点都与它左右相邻的各k/2个节点相连,k是偶数。 2.随机化加边:以概率P在随机选取的一对节点之间加上一条边。其中,任意两个不同的节点之间至多只能有一条边,并且每一个节点都不能有边与自身相连。,2.NW小世界模型,NW小世界模型的随机化加边过程。,2.NW小世界模
17、型,在NW小世界模型中: P=0对应于原来的最近邻耦合网络; P=1则对应于全局耦合网络。 理论分析,NW小世界模型要比WS小世界模型简单一些。当P足够小和N足够大时,NW小世界模型本质上等同于WS小世界模型。,2.NW小世界模型,3.小世界网络模型的统计性质,聚类系数:,3.小世界网络模型的统计性质,3.小世界网络模型的统计性质,4.社会小世界网络,在社会系统中,朋友或熟人关系网络是最基本的,也是研究比较深入的一种网络。 尽管人际关系网络及其庞大而又复杂,然而平均路径(average path length)则是相对短的。 另外,人际关系网络中大多数人都是他们邻居的朋友,表现出很高的集群性。
18、,4.社会小世界网络,规则图中的最近邻耦合网络具有高聚类的特性但是不是小世界网络,在随机图中具有小世界性质但是不具有高聚类特性。两者都与实际的社会网络不一致,原因何在? 人们发现,在熟人关系网络中,个别人偶尔会有几个远方的朋友。然而,这少数远方朋友的存在很可能根本改变网络的结构。,2.4无标度网络,随机网络中节点总数N是预先给定的,所以它们是静态的、固定的、平衡的网络,也有称为设计网络(designed network) 与此相对应,若网络模型的节点总数不是预先给定的,而是逐步增减的,则它们是动态的、增长的、非平衡的网络,或者称为演化网络(evolving network),2.4无标度网络(
19、Scale-free network),随机网络和小世界网络的一个共同特征就是网络的连接度分布可近似poisson分布,该分布在度平均值处有一峰值,两侧呈指数快速衰减。 当k 时,度为k的节点几乎不存在。因此这类网络也成为均匀网络或指数网络。,2.4无标度网络(Scale-free network),许多复杂网络包括Internet、WWW、以及新陈代谢网络等的连接度分布函数具有幂律(power law)形式。 由于这类网络的节点连接度没有明显的特征长度,故称为无标(尺)度网络。,请同学们回忆什么是幂律分布? 请同学们思考什么是特征长度?,2.4无标度网络(Scale-free network
20、),特征长度(Characteristic length)是属于分形几何的概念。 对于某个物体, 特征长度通常是指该物体长度中有代表意义的长度, 如我们考察一个球体, 那么它的特征长度就是该球体的半径或直径。,2.4无标度网络(Scale-free network),普通几何学研究的对象,一般都具有整数的维数。比如,零维的点、一维的线、二维的面、三维的立体、乃至四维的时空。 在20世纪70年代末80年代初,产生了新兴的分形几何学(fractal geometry),空间具有不一定是整数的维,而存在一个分数维数。,2.4无标度网络(Scale-free network),自然界中的物体或图形,
21、要么具有特征长度, 要么不具有特征长度。 对于具有特征长度的物体, 只要其特征长度不变, 其性质就不会发生什么变化。 还有的事物没有特征尺度,就必须同时考虑从小到大的许许多多尺度(或者叫标度),这叫做“无标度性”的问题。,2.4无标度网络(Scale-free network),分开几何:,2.4无标度网络(Scale-free network),分形几何学的基本思想是:客观事物具有自相似的层次结构,局部与整体在形态、功能、信息、时间、空间等方面具有统计意义上的相似性,称为自相似性。 例如,一块磁铁中的每一部分都像整体一样具有南北两极,不断分割下去,每一部分都具有和整体磁铁相同的磁场。 这种自
22、相似的层次结构,适当的放大或缩小几何尺寸,整个结构不变。,2.4无标度网络(Scale-free network),自相似性:,2.4无标度网络(Scale-free network),上世纪80年代初开始的“分形热”经久不息。分形作为一种新的概念和方法,正在许多领域开展应用探索。 美国物理学大师约翰惠勒说过:今后谁不熟悉分形,谁就不能被称为科学上的文化人。 由此可见分形的重要性。,2.4无标度网络(Scale-free network),近年来,人们在互联网和人际关系网络等社会学网络的研究中都发现了“无标度”特性。 无标度网络中,大部分节点通过少数中心节点连接到一起,这就意味着节点在网络中的
23、地位是不平等的,中心节点在连接网络完整性方面起更加重要的作用。,2.4无标度网络(Scale-free network),定义:无标度网络,是指网络中连通度的分布符合幂率分布,即P(k)k-r的网络,如图2-4 B所示。 这种分布说明,在无标度网络中大部分节点的连通度较低,但存在少数连通度非常高的节点使网络连接在一起。在这种网络中,平均连通度等标度已经不足以描述网络的规模和结构。,2.4无标度网络(Scale-free network),图2-4B无标度网络及其连通度分布和聚类系数函数趋势图 B为无标度网络,其连通度分布符合幂率分布,平均聚类系数函数曲线水平。,1.BA无标度网络,为了解释幂律
24、分布(power law)的产生机理,Barabsi和Albert提出了一个无标度网络模型,现在称为BA模型。 他们认为以前的许多网络模型都没有考虑到实际网络的两个重要特征。,1.BA无标度网络,实际网络存在两个重要特征: 1.增长特性(growth):网络的规模不断扩大。,例如: 每个月都会有大量的生物信息学文章发表; WWW上则每天都有大量新的网页产生;,1.BA无标度网络,实际网络存在两个重要特征: 2.优先连接特性(preferential attachment):新的节点更倾向于与那些具有较高连接度的“大”节点相连接,这种现象也称为“富者更富(rich get richer)”或“马
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 分子生物网络分析崔颖第2章 网络拓扑基本模型及其性质 分子 生物 网络分析 崔颖 网络 拓扑 基本 模型 及其 性质
链接地址:https://www.31doc.com/p-3052004.html