复杂网络概述复习课程.pptx

复杂网络概念 复杂网络含义 大量真实复杂系统的拓扑抽象； 在感觉上比规则网络和随机网络复杂； 大量复杂系统得以存在的拓扑基础。 复杂网络的研究历史 哥尼斯堡七桥——随机图论——小世界和无标度网络;2;3;4;小世界实验--- 六度分离;小世界实验—六度分离;小世界实验--- Bacon数 ;小世界实验---Erdos数;小世界实验---Erdos数;小世界实验---Erdos数;13;复杂网络的结构;规则网络;最近邻耦合网络:包含N个围成一个环的点，其中每个节点都与它左右各K/2个邻居点相连（K为偶数），对于较大的K值，最近邻耦合网络的聚类系数为 因此，这样的网络是高度聚类的。对于固定的K值，网络平均路径长度为 星形耦合网络：有一个中心点，其余N-1个点都只与这个中心点连接，其平均路径长度为 聚类系数为 ;随机图;18;C(p) : 平均聚集系数 L(p) : 平均最短路径;作为从完全规则网络向完全随机图的过渡，Watts和Strogtz于1998年引入了一个小世界网络模型，称为WS小世界模型。其构造算法如下： ①从规则图开始：考虑一个含有N个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右相邻的各K/2个节点相连，K是偶数。 ②随机化重连：以概率p随机地重连网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同节点之-间至多只能有一条边，并且每一个节点都不能有边与自身相连。 P=0对应于完全规则网络，p=1对应于完全随机网络。 ; 具有较短的平均路径长度又具有较高的聚类系数的网络就称为小世界网络。 Newman和Watts提出了NW小世界模型，用“随机化加边”取代WS小世界模型构造中的“随机化重连”。算法如下： ①从规则图开始：含有N 个节点的最近邻耦合网络。 ②随机化加边：以概率P在随机选取的一对节点之间加上一条边。 NW小世界模型中，p=0对应于原来的最近邻耦???网络，p=1对应于全局耦合网络。;无标度网络模型; 幂律分布函数的无标度性质 ：考虑一个概率分布函数f(x)，如果对任意给定常数a，存在常数 b 使得函数 f(x) 满足如下“无标度条件”: f(ax)=bf(x) 那么必有(假定 ) 也就是说，幂律分布函数是唯一满足“无标度条件”的概率分布函数。 ;24;技术网络;社会网络;交通运输网络;生物网络;Santa Fe 研究所的科学家合作网;30;中药方剂网;中药方剂网示意图;中国淮扬菜肴网 ;度(degree)：节点 i 的度 ki 定义为与该节点连接的其他节点的数目。 ★ 直观上看，一个节点的度越大就意味着这个节点在 某种意义上越“重要”（“能力大”）。 网络的平均度：网络中所有节点的度和的平均值 ，记作k。事实上，k=2q/p ？ 度分布函数p(k):随机选定节点的度恰好为k的概率 ? 节点的聚类系数（簇系数）：在简单图中，设节点v的邻集为N(v), |N(v)|=ki，则节点v的聚类系数定义为这ki个节点之间存在边数Ei与总的可能边数ki(ki-1)/2之比，即：Ci=2Ei/ki(ki-1) ★ 节点v的邻点间关系的密切程度