加权网络.ppt

《加权网络.ppt》由会员分享，可在线阅读，更多相关《加权网络.ppt（50页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、加权网络加权网络PPT制作制作:苏延森苏延森 主讲人：张海霞主讲人：张海霞 Tel：135893112982009.12.19引言引言l网络加权的网络加权的必要性必要性:无权网络只能给出顶点之间是否存在相互作用，但是在很无权网络只能给出顶点之间是否存在相互作用，但是在很多情况下，顶点之间相互作用的强度的差异起着至关重要多情况下，顶点之间相互作用的强度的差异起着至关重要的作用。的作用。例如：神经元突触之间的连接在学习和认知过程中并不改例如：神经元突触之间的连接在学习和认知过程中并不改变，只是突触之间连接强度的变化使大脑皮层产生了新的变，只是突触之间连接强度的变化使大脑皮层产生了新的功能。功能。再

2、如，再如，Internet网络上的带宽、航空网中两个机场网络上的带宽、航空网中两个机场间航班数量或者座位数、科学家合作网中的合作次数等都间航班数量或者座位数、科学家合作网中的合作次数等都是影响系统性质的重要因素。是影响系统性质的重要因素。而且，加权网络在实际中是普遍存在的，无权网络完全可而且，加权网络在实际中是普遍存在的，无权网络完全可以作为加权网络的一种特例。以作为加权网络的一种特例。一一.加权网络的统计性质加权网络的统计性质二二.加权网络的演化模型加权网络的演化模型三三.权重对网络结构性质的影响权重对网络结构性质的影响四四.加权网络上的动力学加权网络上的动力学主要内容主要内容:一一.加权网

3、络的统计性质加权网络的统计性质1.加权的方式加权的方式2.加权网络上的统计量加权网络上的统计量1.加权的方式加权的方式u根据根据相关的物理量相关的物理量 例如例如:电阻网络边上的权值代表电阻值电阻网络边上的权值代表电阻值,邮递员问邮递员问题中的距离题中的距离u根据相互作用的某种属性根据相互作用的某种属性 例如例如:科学家通过文献相互作用科学家通过文献相互作用,把引文的次数作把引文的次数作为权重为权重l边权按照意义划分边权按照意义划分:相异权相异权:权值越大权值越大,两点之间的距离越大两点之间的距离越大,关系越疏远关系越疏远.例例:邮递员问题中的距离邮递员问题中的距离相似权相似权:权值越大权值越

4、大,两点之间的距离越小两点之间的距离越小,关系越亲密关系越亲密.例例:科学家合作网中科学家合作网中,把次数作为权重把次数作为权重,得到相似权得到相似权注意注意:在计算两点间的距离和聚类系数时在计算两点间的距离和聚类系数时,边权的意义不同边权的意义不同,计计算方式也不同算方式也不同.2.加权网络上的统计量加权网络上的统计量l基本概念：点权、单位权和差异性l权的相关性 l最短路径l聚类系数l基本概念基本概念1 1）点权（点强度）点权（点强度）：，（其中，（其中 是节点是节点i 的近邻集合）的近邻集合）注注：无权网中节点度的自然推广，即与节点：无权网中节点度的自然推广，即与节点i关联的边权之和。关联

5、的边权之和。2 2）单位权单位权：,即即 顶点连接的平均权重顶点连接的平均权重.3）权重分布的）权重分布的差异性差异性：表示与表示与i相连的边权分布的离散程度。相连的边权分布的离散程度。注注：拥有相同点权与单位权的两个节点相比，差异性越大，：拥有相同点权与单位权的两个节点相比，差异性越大，离散程度越大。离散程度越大。l基本概念基本概念结论结论结论结论1 1：点权与度的关系：点权与度的关系，当边权与网络的拓扑结构，当边权与网络的拓扑结构无关无关时时，当边权与网络的拓扑结构，当边权与网络的拓扑结构有关有关时时其中其中为边权平均值；为边权平均值；或者或者结论结论结论结论2 2：差异性与度的关系：差异

6、性与度的关系：差异性与度的关系：差异性与度的关系1）如果与顶点）如果与顶点i关联的边的权重值差别不大，关联的边的权重值差别不大，则则与与成正比。成正比。2）如果权值相差较大，例如只有一条边的权重起主要作用，则）如果权值相差较大，例如只有一条边的权重起主要作用，则l权的相关性权的相关性对加权网络进行对加权网络进行 度相关性分析度相关性分析 权与度相关性分析权与度相关性分析 点权相关性分析点权相关性分析 1.度相关性分析度相关性分析：因为对网络加权不改变节点的度的性质，所以度相关性分析因为对网络加权不改变节点的度的性质，所以度相关性分析与无权网络中分析相同。与无权网络中分析相同。在无权网络中：在无

7、权网络中：定义节点定义节点i的近邻平均度的近邻平均度并由此可以得到度为并由此可以得到度为k的所有节点的近邻平均度的平均值的所有节点的近邻平均度的平均值1）如果此函数无单调性，那么该网络没有度相关性。）如果此函数无单调性，那么该网络没有度相关性。2）如果是增函数，那么该网络是）如果是增函数，那么该网络是同向匹配同向匹配网络。（度大的节点与网络。（度大的节点与度大的节点相连）度大的节点相连）3）如果是减函数，那么该网络是）如果是减函数，那么该网络是负向匹配负向匹配网络。网络。2.权与度的相关性分析权与度的相关性分析在加权网络中，定义节点的在加权网络中，定义节点的加权平均近邻度加权平均近邻度1），具

8、有，具有较大权重较大权重的边倾向于连接具有的边倾向于连接具有较大度值较大度值的点的点2），具有，具有较大权重较大权重的边倾向于连接具有的边倾向于连接具有较小度值较小度值的点的点l权的相关性权的相关性定义节点的加权平均近邻权，同样找到点权为定义节点的加权平均近邻权，同样找到点权为s的所有节点的加的所有节点的加权平均近邻权的平均值权平均近邻权的平均值 ，通过该函数的单调性分析得到，通过该函数的单调性分析得到点权相关性。点权相关性。3.点权相关性分析点权相关性分析：l权的相关性权的相关性l最短路径最短路径1.定义加权网络中两点之间的距离与权重的关系定义加权网络中两点之间的距离与权重的关系：距离是权重

9、的某种函数，这时需要看权重是相似权还是相异权。距离是权重的某种函数，这时需要看权重是相似权还是相异权。相异权相异权：定义两点之间的距离：定义两点之间的距离相似权相似权：令：令假设顶点假设顶点i和和k分别通过两条权重分别为分别通过两条权重分别为 和和 的边相连，现的边相连，现求求i与与k之间的距离。之间的距离。对于对于相异权相异权：对于对于相似权相似权：l最短路径最短路径2.最短路径最短路径：两点之间所有连通的路径中距离之和最小的一条或几条路径。两点之间所有连通的路径中距离之和最小的一条或几条路径。无权网无权网：边数最少的路径：边数最少的路径 最短路径最短路径 加权网加权网：因为距离不满足三角不

10、等式，所以两边之和不一定大于第三边：因为距离不满足三角不等式，所以两边之和不一定大于第三边.边数最少的路径边数最少的路径 最短路径最短路径注：网络的其他全局统计量，如介数，可以在加权最短路径的基础上注：网络的其他全局统计量，如介数，可以在加权最短路径的基础上进行计算进行计算l聚类系数聚类系数 节点节点i的聚类系数的聚类系数 反映了该节点邻点的联系的程度。反映了该节点邻点的联系的程度。越大，说明越大，说明该点的邻接点之间的联系越紧密。该点的邻接点之间的联系越紧密。对加权网络中的聚类系数提出了多种定义方式：对加权网络中的聚类系数提出了多种定义方式：1）Barat 定义：定义：分母上为单位权乘以最大

11、可能的三角形的数目，分子上是实际三角形数目乘以分母上为单位权乘以最大可能的三角形的数目，分子上是实际三角形数目乘以与与i相连的边的权重的平均值相连的边的权重的平均值 2）Onnela 定义：定义：其中其中 为网络中经最大权重标准化后的数值为网络中经最大权重标准化后的数值l聚类系数聚类系数比较比较Barat和和Onnela的定义：计算结果后者优于前者定义：计算结果后者优于前者。如图：第一种定义，聚类系数值的大小只与三角形连接顶点第一种定义，聚类系数值的大小只与三角形连接顶点i的两边权有关。的两边权有关。第二种定义，值的大小与三边权都有关。第二种定义，值的大小与三边权都有关。l聚类系数聚类系数Pe

12、tter Holme 分析加权网络的聚类系数，指出它应该满足以下几条要求：分析加权网络的聚类系数，指出它应该满足以下几条要求：l聚类系数聚类系数1.2.加权网退化为无权网时，聚类系数应与加权网退化为无权网时，聚类系数应与Watts-Strogatz定义的聚类系定义的聚类系数的计算结果一致。数的计算结果一致。3.权值为权值为0表示该边不存在。表示该边不存在。4.包含节点包含节点i的三角形中三条边对的三角形中三条边对 的贡献应与边的权重成正比。的贡献应与边的权重成正比。Petter Holme定义：定义：Watts-Strogatz 定义的聚类系数定义的聚类系数:（权重必须为相似权）（权重必须为相

13、似权）二二.加权网络的演化模型加权网络的演化模型l赋权的类型：赋权的类型：静态网络不能揭示加权网络的演化行为静态网络不能揭示加权网络的演化行为,需要研究网络拓扑结需要研究网络拓扑结构和权重分布的耦合演化机制构和权重分布的耦合演化机制.l演化过程中的关键问题：如何给边赋值演化过程中的关键问题：如何给边赋值l研究的意义：研究的意义：边权固定模型边权固定模型引入边的时候就按一定的规则给边赋值，引入边的时候就按一定的规则给边赋值，之后边权不变之后边权不变边权演化模型边权演化模型边权随网络结构的演化而改变边权随网络结构的演化而改变l边权固定模型1.YJBT（Yook-Jeong-Barabasi-Tu）

14、模型）模型 2001年，年，Yook和和Barabasi等提出了类似于等提出了类似于BA模型的加权网络生成模型。其模型的加权网络生成模型。其演化规则演化规则如下：如下：（1）网络拓扑结构的演化网络拓扑结构的演化（同（同BA模型）模型）增长：初始时有增长：初始时有n0个节点，每个时间布加入一个新节点个节点，每个时间布加入一个新节点j，并使新节点，并使新节点j与与m个已经存在的点连接（个已经存在的点连接（m n0）择优连接：新加入的点与网络中已经存在的点的连接不是等概率的，而是择优连接：新加入的点与网络中已经存在的点的连接不是等概率的，而是以一种择优的方式选择与自己连接的点。新节点以一种择优的方式

15、选择与自己连接的点。新节点j与节点与节点i连接的概率连接的概率:（2）赋边权赋边权(基于两个假设基于两个假设:权重权重Wij正比于节点正比于节点i的度的度;所有新节点有相同的点所有新节点有相同的点权权)新节点与已存在节点之间的每一条连接新节点与已存在节点之间的每一条连接j i,被赋予一定的权重被赋予一定的权重 ，权，权重的多少取决于被连接节点重的多少取决于被连接节点i的度的度这时新节点这时新节点j的点权为的点权为1YJBT模型特点模型特点：拓扑结构与拓扑结构与BA模型相同，故度分布模型相同，故度分布点权分布符合幂律分布：点权分布符合幂律分布：，其中指数与参数，其中指数与参数m有关有关在在 时，

16、点权分布渐进逼近度分布。时，点权分布渐进逼近度分布。YJBT模型的关键是在模型的关键是在BA无标度网络无标度网络的基础上为边赋权。的基础上为边赋权。2.ZTZH（Zheng-Trimper-Zheng-Hui）模型）模型在在YJBT模型的基础上进行推广，赋边权时综合考虑节点的度和模型的基础上进行推广，赋边权时综合考虑节点的度和适应度适应度。适应度适应度 ：反应节点：反应节点i本身的性质。假设其服从本身的性质。假设其服从0,1上的均匀分布上的均匀分布.(当不知当不知道随机变量取值的特点时道随机变量取值的特点时,假设其服从某一区间上的均匀分布假设其服从某一区间上的均匀分布)演化规则：演化规则：(1

17、)网络结构拓扑演化同网络结构拓扑演化同YJBT网络网络 (2)赋边权赋边权:设定一概率设定一概率p 则当则当p=1时时,ZTZH模型模型=YJBT模型模型 当当p=0时时,边权的赋予完全由节点的适应度决定边权的赋予完全由节点的适应度决定.l边权固定模型该模型的特点该模型的特点:1）度分布）度分布=BA模型模型,服从幂为服从幂为3的幂律分布的幂律分布.2）点权分布服从幂律分布）点权分布服从幂律分布,幂依赖于参数幂依赖于参数p.3）边权一经赋予）边权一经赋予,不再改变不再改变.另外还有一些边权固定模型。比如在另外还有一些边权固定模型。比如在YJBT网络的基础上将基于度的择优网络的基础上将基于度的择

18、优连接机制改进为基于点权的择优连接机制，从而得到连接机制改进为基于点权的择优连接机制，从而得到Ak（Antal-Krapivsky）模型。模型。边权固定模型的边权固定模型的共同特点共同特点:边权一旦设定不再改变边权一旦设定不再改变,也就是说网络中也就是说网络中边的权重在初始时刻己经给定边的权重在初始时刻己经给定,而且随着网络规模的增大而且随着网络规模的增大,边权没有任何边权没有任何变化。这与实际系统中的情况有很大的差异。变化。这与实际系统中的情况有很大的差异。比如在航空网络中随着航空网络的增大，比如在航空网络中随着航空网络的增大，与新机场有连接关系的机与新机场有连接关系的机场的场的各条航线上的

19、客各条航线上的客流流量也会有相应的增加，量也会有相应的增加，在加权网络中就表现为边在加权网络中就表现为边权的增加权的增加.这时在加权网络的演化模型中需要考虑边权的演化这时在加权网络的演化模型中需要考虑边权的演化.l边权演化模型1.BBV（Barrat-Barthelemy-Vespignani）模型）模型演化规则：演化规则：(1)网络结构拓扑演化网络结构拓扑演化 增长：初始时有增长：初始时有n0个节点，每边赋权值为个节点，每边赋权值为w0 每个时间间隔加入一个带有每个时间间隔加入一个带有m条边的新节点条边的新节点 j，边权也为边权也为w0 优先连接：根据优先连接：根据 选择选择老节点老节点 i

20、 与新节点与新节点 j 相连相连（2）边权演化）边权演化与新边相连的顶点与新边相连的顶点点权点权新边的加入新边的加入i的原邻边按权重所占的比例分配增值的原邻边按权重所占的比例分配增值BBV模型的特点模型的特点：(1).度分布，边权分布，点权分布均服从幂律分布度分布，边权分布，点权分布均服从幂律分布：度分布度分布：说明说明BBV模型可以生成幂指数介于模型可以生成幂指数介于2,3之间的之间的无标度网络无标度网络.边权分布边权分布：点权分布点权分布：(2).权与度的相关性权与度的相关性点权与网络的拓扑结构有关点权与网络的拓扑结构有关 ,其中其中可以看到可以看到:这里这里2.DM（Dorogovtse

21、v-Mendes）模型）模型实例实例:科学家合作网络科学家合作网络边权设定为能反应合作著作的重要性的数值边权设定为能反应合作著作的重要性的数值(综合著作的出版时间综合著作的出版时间,著作的影响力著作的影响力等因素得到的等因素得到的).比如两个科学家在比如两个科学家在20年前之合作出版了一部著作年前之合作出版了一部著作,那么另外一个那么另外一个科学家与他们合作的几率就会很小科学家与他们合作的几率就会很小.这时网络拓扑演化过程就应该首先考虑到边这时网络拓扑演化过程就应该首先考虑到边权大小权大小.DM模型模型演化规则演化规则:网络开始于任意的一组节点和边网络开始于任意的一组节点和边.(1)择优择优:

22、在已有的节点中在已有的节点中,按照与边权成正比的概率选择一条边按照与边权成正比的概率选择一条边 加权加权:令该边的权值有一个小的增量令该边的权值有一个小的增量(2)增长增长:加入一个新节点加入一个新节点,且该节点于且该节点于所选边的两端连接所选边的两端连接,并设并设新边的权重为新边的权重为1DM模型的特点模型的特点:度分布度分布,边权分布边权分布,点权分布均为点权分布均为幂律分布幂律分布度分布度分布:边权分布边权分布:点权分布点权分布:BBV模型与模型与DM模型的模型的不同点不同点:择优机制：点权与边权同时考虑？择优机制：点权与边权同时考虑？例如：基因网络中，存在某基因活性很高，同时存在一条细

23、胞路径（一条边）例如：基因网络中，存在某基因活性很高，同时存在一条细胞路径（一条边）非常重要，要加入的新基因既可以和活性高的基因完成一些活动，又可与该边非常重要，要加入的新基因既可以和活性高的基因完成一些活动，又可与该边结合进行其他细胞过程的完成，问题是：如何决定新基因的连接？结合进行其他细胞过程的完成，问题是：如何决定新基因的连接？BBV模型和模型和DM模型的模型的共同特点共同特点:1）拓扑结构上）拓扑结构上:只考虑新节点与老节点相连只考虑新节点与老节点相连2）边权是独立于连接之外的一个基本量）边权是独立于连接之外的一个基本量.也就是说不管连接的具体程度如何也就是说不管连接的具体程度如何,只

24、只要有连接要有连接,就按照相同的规则来赋边权就按照相同的规则来赋边权.但在实际中但在实际中,所赋边权的大小往往与连接所赋边权的大小往往与连接的强度有关的强度有关,这时应该做相关方面的假设这时应该做相关方面的假设.BBV模型是以点权为驱动机制模型是以点权为驱动机制,而而DM模型是以边权为驱动机制模型是以边权为驱动机制.比较两种模型比较两种模型:思考思考:模型改进模型改进三三.权重对网络结构性质的影响权重对网络结构性质的影响无权网络无权网络结构性质的改变：通过改变网络的拓扑结构来实现结构性质的改变：通过改变网络的拓扑结构来实现加权网络加权网络结构性质的改变结构性质的改变:通过改变网络的拓扑结构和通

25、过改变网络的拓扑结构和调整权重调整权重两种途径两种途径 来实现来实现调整权重调整权重的途径：的途径：第一种：权重集合不变，改变权与边的对应关系第一种：权重集合不变，改变权与边的对应关系第二种：权重的总量或是均值不变，改变权重的分布形式第二种：权重的总量或是均值不变，改变权重的分布形式网络中有多种统计量来反应网络结构的性质：网络中有多种统计量来反应网络结构的性质：基本结构：点权，最短路径，聚类系数基本结构：点权，最短路径，聚类系数 社团结构社团结构权重调整对基本结构性质的影响权重调整对基本结构性质的影响 1.通过改变权与边的对应关系，研究对基本结构的影响通过改变权与边的对应关系，研究对基本结构的

26、影响 2.通过改变权重的分布形式，研究对基本结构的影响通过改变权重的分布形式，研究对基本结构的影响权重调整对社团结构性质的影响权重调整对社团结构性质的影响权重调整对基本结构性质的影响权重调整对基本结构性质的影响1.通过通过改变权与边的对应关系改变权与边的对应关系，研究对基本结构性质的影响，研究对基本结构性质的影响如何表示权与边的对应关系？如何表示权与边的对应关系？给定一个加权网络，引入一个参数给定一个加权网络，引入一个参数p,描述权重和边的匹配关系。描述权重和边的匹配关系。将原始网络中权与边的关系降序排列，令将原始网络中权与边的关系降序排列，令p=1表示该原始序列：表示该原始序列：P=-1表示

27、权与边的关系进行反序排列，称之为反权网络：表示权与边的关系进行反序排列，称之为反权网络：P=0表示保持边的顺序不变，然后从权重集合中随机抽取一个权重分给该表示保持边的顺序不变，然后从权重集合中随机抽取一个权重分给该边，称之为随机赋权网络。边，称之为随机赋权网络。P可以看作新序列与原来序列的相关系数。改变可以看作新序列与原来序列的相关系数。改变p值就改变了边与权的对应值就改变了边与权的对应关系，下面考虑关系，下面考虑p由由1变为变为0和和-1时时，基本结构性质有何变化。，基本结构性质有何变化。研究结果：研究结果：1.通过无权网络和加权网络的点介数和边介数的对比发现：两者在通过无权网络和加权网络的

28、点介数和边介数的对比发现：两者在统计分布上定性一致，但在微观上节点或边的位置或数值发生了变统计分布上定性一致，但在微观上节点或边的位置或数值发生了变化。化。2.对对p=1原始网原始网,p=0随机加权网随机加权网,p=-1反权网的点权分布，聚类系数反权网的点权分布，聚类系数分布，边介数，点介数的比较发现：分布，边介数，点介数的比较发现：点权分布基本一致，聚类系数分布差别相对明显，点权分布基本一致，聚类系数分布差别相对明显，边介数分布基边介数分布基本一致，但某一条边的位置在不同网络中差别很大。点介数分布基本一致，但某一条边的位置在不同网络中差别很大。点介数分布基本一致，高端处变化相对较大，某一点的

29、位置在不同网络中略有改本一致，高端处变化相对较大，某一点的位置在不同网络中略有改变。变。结论：结论：原始网络，反权网络，随机权网络以及他们对应的无权网络，各静态统原始网络，反权网络，随机权网络以及他们对应的无权网络，各静态统计量的全局分布大致相同，但是细致结构受到了权重的影响。说明权重计量的全局分布大致相同，但是细致结构受到了权重的影响。说明权重与实际网络中的边有特定的匹配关系，不能随便赋权。与实际网络中的边有特定的匹配关系，不能随便赋权。边的序边的序1101001k1101001k边介数分布，在加权网与无权网边介数分布，在加权网与无权网中边介数分布差别相对较大，同中边介数分布差别相对较大，同

30、一条边的介数值相差相对较大。一条边的介数值相差相对较大。边边介介数数实例实例：边介数反映了这两个科学：边介数反映了这两个科学家交流对整个新思想的传播的影家交流对整个新思想的传播的影响。加权网中的边介数更能说明响。加权网中的边介数更能说明这两个人的交流的重要性。这两个人的交流的重要性。1101001k1101001k点的序点的序点点介介数数粗线代表加权网粗线代表加权网细线代表无权网细线代表无权网点介数分布，在加权网和无权网中点介数分布，在加权网和无权网中分布基本一致，只有在高端略有差分布基本一致，只有在高端略有差别，同一个科学家的位置没有变化，别，同一个科学家的位置没有变化，但在数值上有明显差别

31、。但在数值上有明显差别。经济物理学家合作网经济物理学家合作网1101001k1101001k原始网原始网随机赋权网随机赋权网反权网反权网点权分布，三种情况基本一致点权分布，三种情况基本一致点的序点的序权权重重1101001k1101001k点的序点的序聚聚类类系系数数原始网原始网随机赋权网随机赋权网反权网反权网聚类系数：反权网和随机聚类系数：反权网和随机赋权网的聚类系数都比原赋权网的聚类系数都比原始网的聚类系数低始网的聚类系数低1101001k1101001k边的序边的序边边介介数数原始网原始网随机赋权网随机赋权网反权网反权网边介数分布基本相同但同一条边边介数分布基本相同但同一条边的位置差别较

32、大的位置差别较大1101001k1101001k点的序点的序点点介介数数原始网原始网随机赋权网随机赋权网反权网反权网点介数分布：除了高端处略有差别点介数分布：除了高端处略有差别外，分布大致相同，相同顶点的位外，分布大致相同，相同顶点的位置略有改变。置略有改变。2.通过通过改变权重的分布形式改变权重的分布形式，研究对基本结构的影响，研究对基本结构的影响调整权与边的对应关系没有改变边权的分布，下面介绍如何改变权重分布的方法。调整权与边的对应关系没有改变边权的分布，下面介绍如何改变权重分布的方法。构造网络（与构造小世界网络方法类似），再通过对平均路径和平均聚类系数的构造网络（与构造小世界网络方法类似

33、），再通过对平均路径和平均聚类系数的分析研究网络基本结构性质的变化情况。分析研究网络基本结构性质的变化情况。构造网络构造网络：（1）起始于最近邻耦合网络）起始于最近邻耦合网络 构造一个包含构造一个包含N个节点的环状规则网络，每个节点与个节点的环状规则网络，每个节点与k(k=2m)个邻居相连，个邻居相连，每条边赋予相同的相异权重每条边赋予相同的相异权重w，例如，例如w=5；其次再把每条边的权重；其次再把每条边的权重n等分，每份等分，每份为为 (=w/n),例如例如n=5，则每份权重为，则每份权重为1 (2)重分概率重分概率p 把每条边上的每份权重把每条边上的每份权重 按按p的概率抽出，再把抽出的

34、权重放回到从网络的概率抽出，再把抽出的权重放回到从网络中等概率地随机选择的一条边上。中等概率地随机选择的一条边上。要求每条边上都至少有一个单位权重。要求每条边上都至少有一个单位权重。这样构造的网络不会改变网络连接，但可以把权重为这样构造的网络不会改变网络连接，但可以把权重为 分布的规则网络转化为分布的规则网络转化为权重为泊松分布的网络。权重为泊松分布的网络。结论结论:通过对比多个通过对比多个p(0P1)对应的多个网络之间的平均路径和平均聚类系数对应的多个网络之间的平均路径和平均聚类系数,可以可以看出网络结构性质的变化看出网络结构性质的变化.边权的重新分布过程中，随着重分概率的增加边权的重新分布

35、过程中，随着重分概率的增加,网络的网络的平均最短距离平均最短距离明显减小明显减小,而而聚类系数聚类系数略有增加略有增加.显然通过对原始权重的重新分布显然通过对原始权重的重新分布,也可以获得小世界效应也可以获得小世界效应.网络密度用网络密度用 来表示来表示,网络密度不同对应的网络密度不同对应的曲线不同曲线不同,有何关系有何关系?在同一重分概率在同一重分概率p下下,同一规模下同一规模下N，随着网络密度的增加，随着网络密度的增加,平均最短路径可以达平均最短路径可以达到一个极小值到一个极小值,说明要想得到较短的平均最短距离，应考虑构造稠密网络。间接说明要想得到较短的平均最短距离，应考虑构造稠密网络。间

36、接说明在稠密网络中说明在稠密网络中,权重的作用更加重要。权重的作用更加重要。平均最短路径在平均最短路径在p一定下随网络密度变化的现象与网络的规模一定下随网络密度变化的现象与网络的规模N无关无关,不同规模下不同规模下所得的结果定性一致所得的结果定性一致.P=1时时,不同网络规模下平均最短路径的变化曲线不同网络规模下平均最短路径的变化曲线给定给定p后后,平均最短路径的变化与网络密度的关系平均最短路径的变化与网络密度的关系权重调整对社团结构的影响权重调整对社团结构的影响社团社团可以看做一组节点可以看做一组节点,社团内的连接比较密集社团内的连接比较密集,社团间的连接社团间的连接比较稀疏比较稀疏.社团结

37、构反应网络整体性质社团结构反应网络整体性质.无权网络无权网络社团划分依据社团划分依据:连接密度连接密度加权网络加权网络社团划分依据社团划分依据:连接密度和连接强度连接密度和连接强度(边权边权)所以所以,在加权网络中在加权网络中,权重调整将会对社团的划分产生影响权重调整将会对社团的划分产生影响.如何定量地来描述由于权重的调整造成的社团划分的不同如何定量地来描述由于权重的调整造成的社团划分的不同?以下重点运用以下重点运用差异性函数差异性函数D，来定量描述社团划分的差异性。，来定量描述社团划分的差异性。差异性函数差异性函数D:1.基本依据基本依据:两个集合两个集合A和和B的相似性和相异性的相似性和相

38、异性 表示其相似性表示其相似性 表示其相异性表示其相异性 因此因此相似性相似性和和相异性相异性的定义如下的定义如下 为了量化为了量化,定义定义:故故122集合之间的集合之间的相似性相似性和和相异性相异性的数值可以如下计算的数值可以如下计算:每个社团可以看成是一个集合，一个社团结构可以看做是一个集合每个社团可以看成是一个集合，一个社团结构可以看做是一个集合的集合。两个社团结构之间的差异性是先通过相似性得到相配对的的集合。两个社团结构之间的差异性是先通过相似性得到相配对的集合，再综合每对集合之间的差异性得到的。集合，再综合每对集合之间的差异性得到的。2.利用差异函数利用差异函数D,社团结构差异社团

39、结构差异的比较规则如下的比较规则如下:(1).建立不同情况下生成两组集合之间的匹配关系建立不同情况下生成两组集合之间的匹配关系,根据相似性寻根据相似性寻找子集找子集Xi的配对子集的配对子集Yi(2).根据配对关系计算各组子集的相异性根据配对关系计算各组子集的相异性d(3).把计算出的相异性数值综合考虑把计算出的相异性数值综合考虑,得到最终社团结构的差异性得到最终社团结构的差异性,即即在这个定义下在这个定义下,D的数值将在的数值将在0,1之间之间,函函数值越大说明两种划分的差异性越大数值越大说明两种划分的差异性越大设同一网络的有两种不同的社团划分设同一网络的有两种不同的社团划分 Xk,Yk.对于

40、对于Xk中中的每一个社团的每一个社团Xi,现要从现要从Yk 中寻找一个社团中寻找一个社团Yi,使得使得Xi与与Yi的的相似性相似性S最大。但可能出现的问题：最大。但可能出现的问题：(1)如果如果Xk 中社团个数与中社团个数与Yk中社团个数不相同中社团个数不相同,怎么找与怎么找与Xi相似的相似的Yi?(2)多个多个Xi对应于同一个对应于同一个Yi，如何解决？如何解决？采用采用G-N算法分别进行算法分别进行加权网加权网与与无权网无权网的社团划分的社团划分,再利用差异性函再利用差异性函数数D进行社团结构之间差异性分析进行社团结构之间差异性分析,发现差异性较大发现差异性较大,说明权重对集团说明权重对集

41、团的划分有很大的影响的划分有很大的影响.00.10.250100150200250300社团数量社团数量D经济物理科学家合作关系研究中经济物理科学家合作关系研究中,加权网和无权网的差异性分析加权网和无权网的差异性分析.四四.加权网络上的动力学加权网络上的动力学目的：目的：了解网络结构对网络功能的作用，理解和解释系统的工作方式，进了解网络结构对网络功能的作用，理解和解释系统的工作方式，进而改善或优化系统的功能。而改善或优化系统的功能。关键问题：关键问题：在给定网络拓扑结构的前提下，如何匹配权重以优化网络功在给定网络拓扑结构的前提下，如何匹配权重以优化网络功能？而探讨在给定网络上权重分布于相应动力

42、学之间的关系是解决这一能？而探讨在给定网络上权重分布于相应动力学之间的关系是解决这一问题的第一步。问题的第一步。加权网上的传播行为加权网上的传播行为加权网上的同步加权网上的同步可激发系统的协同震荡可激发系统的协同震荡l加权网络上的同步加权网络上的同步无权网络无权网络的研究表明：与规则网络相比，小世界网络和无标度网络的同步的研究表明：与规则网络相比，小世界网络和无标度网络的同步 能力大幅提高，这说明同步协调能力与网络的平均最短距离以及能力大幅提高，这说明同步协调能力与网络的平均最短距离以及 集聚系数密切相关。集聚系数密切相关。加权网络加权网络中的研究发现：网络中适当加权与无权网络相比可以大大提高

43、网中的研究发现：网络中适当加权与无权网络相比可以大大提高网 络的同步能力。络的同步能力。考虑如下耦合晶格映射：考虑如下耦合晶格映射：其中其中 表示节点表示节点i在在t时刻的状态变量，时刻的状态变量，t 为离散时间变量。为离散时间变量。f(x)表示节点的动力学函数，本文表示节点的动力学函数，本文中采用中采用Logistic映射映射 。表示节点表示节点i和其他和其他m个节点的耦合强度（只考个节点的耦合强度（只考虑最近邻和次近邻）。虑最近邻和次近邻）。l加权网络上的同步加权网络上的同步 对比了所有边上的权重相同时（对比了所有边上的权重相同时（p=0）和权重完全随机分布（）和权重完全随机分布（p=1）后）后网络的同步水平，发现权重随机分布以后系统更易于达到完全同步。且随网络的同步水平，发现权重随机分布以后系统更易于达到完全同步。且随着分布概率着分布概率p 的增大，网络的同步能力逐步增强，即权重随机分布能显著的增大，网络的同步能力逐步增强，即权重随机分布能显著提高网络的同步能力。提高网络的同步能力。(a)同步水平在不同概率同步水平在不同概率p下与下与 的关系的关系(b)同步水平在同步水平在 确定的情况下与概率确定的情况下与概率p的关系的关系Thank you！