复杂网络Ch6 加权网络

第6章加权网络6.1加权网络模型及统计性质6.2权重对网络结构性质的影响6.3加权网络的演化6.4空间网络16.1加权网络模型及统计性质26.1.1边权的定义3权重（点、边）加权网络中边权的赋予网络中以已有的物理量eg：电阻网络——电阻；航空网——座位数、航班数、里程；新陈代谢网——反应速率；因特网——带宽相互作用的抽象eg：科学家合作网——合著文章数；演员合作网——合演次数；中药网、菜肴网等4无权无向网络

加权无向网络31423214protein-proteininteractions,wwwCallGraph,metabolicnetworks6.1.1边权的定义5权重的不同定义相似权：

概念与距离相反，边权越大，顶点之间越亲近（0为无连接）如合作次数、化学反应速率相异权：

概念与距离相同，边权越大，顶点之间距离越远（∞为无连接）如航空线的里程

YINGFAN,MENGHUILI,JIAWEICHEN,LIANGGAOandZENGRUDI，InternationalJournalofModernPhysicsBVol.18,Nos.17-19(2004)2505-25116.1.1边权的定义6.1.2加权网络上的统计量6点强度，强度分布，单位权和差异性点权：单位权：权重分布的差异性：7相关性相关匹配性质：节点的加权平均近邻度：

具有较大权重的边倾向于连接具有较大度值的节点

具有较大权重的边倾向于连接具有较小度值的节点6.1.2加权网络上的统计量8最短路径：两个由权重分别为w12和w23的边连接的顶点之间的距离:相异权d13=w12+w23相似权d13=1/w=1/w12+1/w236.1.2加权网络上的统计量123w12w239加权集聚系数：加权网集聚系数:

加权网集聚系数:

(三角形三条边上权重的几何平均值)

6.1.2加权网络上的统计量10

6.1.2加权网络上的统计量11生物网络：阿尔莫斯（Almaas）等把大肠杆菌的新陈代谢反应看作加权网络进行研究。蒂耶里等研究了人类免疫系统中细胞间的通信过程。社会网络：科学家合作网、电影演员合作网、E-mail网络以及人际关系网等都是典型的社会网络，其中许多网络的拓扑性质，都得到了深入研究。技术网络:基础设施网络中如Internet、铁路网、地铁网和航空网中，输运过程中的流量可以自然的转化为权重。6.1.3一些加权网络的实证结果12收集了1992-2004年发表的经济物理学方面的文章，包括808篇文章和819位作者。从数据库中可以得到任意两位作者之间的合作、引用和致谢3种关系的次数3个网络：合著网络、引用网络和致谢网络，把不同层次的交流和相应次数转化为边上的权重。把每条边上的合作、引用和致谢的权重综合成为一个权重：3种关系所对应的权重定义为：引用和致谢是有方向性的，因此经济物理科学家合作网络是一个加权有向网。在以上数据库和边权赋予的情况下，得到了该网络的基本统计结果。6.1.4经济物理学科学家合作网络的建立和统计分析13经济物理学家合作网络的Zipf排序6.1.4经济物理学科学家合作网络的建立和统计分析14经济物理学家合作网络的点介数的Zipf排序6.1.4经济物理学科学家合作网络的建立和统计分析15单位权频数统计分布6.1.4经济物理学科学家合作网络的建立和统计分析16社团结构的模块化Q函数：6.1.5加权网络的社团结构表示节点i的点权网络中所有连边的权重之和

17GN算法在加权网上的推广:将加权网转化为无权多图，在无权多图中每条边的权重都是相同的，点与点之间的紧密程度是由边的个数表示的。加权网与无权多图：6.1.5加权网络的社团结构18

6.1.5加权网络的社团结构6.2权重对网络结构性质的影响1920调整权重与边的匹配关系:6.2.1权重调整对网络基本结构性质的影响原始加权网络（Weighted）相应的无权网（Nonweighted）反权网（Inverse）21原始网络、反权网络和随机赋权网络的比较6.2.1权重调整对网络基本结构性质的影响22加权网络和无权网络中最大连通集团介数分布的比较:6.2.1权重调整对网络基本结构性质的影响23最大连通集团的统计结果：6.2.1权重调整对网络基本结构性质的影响经济物理科学家合作网络原始网络集聚系数值比反权网络和随机网络的数值大。这表明权重和网络中的边有特定的匹配关系，权重并不是随机赋予的，而是与网络的结构与功能耦合在一起的。24调整权重的分布:6.2.1权重调整对网络基本结构性质的影响产生新权重分布的方法和理论分析（权重随机化方法）在规则网上，把每条边的权重w分成份(每为)，每一份都以

p的概率抽取；把抽取后的份

等概率的撒在每条边上。权重分布的理论分析：设随机化后边权为，那么每条边包含

的份数与同分布25平均最短路径和集聚系数与概率p的关系6.2.1权重调整对网络基本结构性质的影响26网络规模与平均最短路径的关系:6.2.1权重调整对网络基本结构性质的影响27网络引入权重之后，节点间的相互作用会发生改变，进而影响聚类过程中社团的划分。纽曼针对已知社团结构的网络，给出了判别不同聚类结果正确率的方法

不能准确的描述不同社团结构间的差别

达农等提出了一个比较不同聚类结果准确率的函数I(A,B)

没有注重社团结构中类的差别判断聚类结果差异性的函数D6.2.2权重调整对社团结构的影响28加权网络和无权网络聚类结果对比:6.2.2权重调整对社团结构的影响6.3加权网络的演化2930基本特征：按照一定的偏好机制形成网络拓扑结构的演化，在此过程中为每一条新加入的边赋权。而边权是固定的，并不随网络结构的演化而变化。模型：Yook-Jeong-Barabási-Tu(YJBT)、Zheng-Trimper-Zheng-Hui(ZTZH)、Antal-Krapivsky(AK)6.3.1边权固定模型31Yook-Jeong-Barabási-Tu(YJBT)考虑权重的无标度网络演化模型。在演化过程中，网络拓扑结构的演化规则与无权网络演化的BA模型完全相同。节点j所带有的边按偏好连接规则连接到老节点，连接到节点i的概为：

m条边连接完成后，节点j的每条边赋予权重：6.3.1边权固定模型32

6.3.1边权固定模型33Antal-Krapivsky(AK)加权网络的演化模型，改进之处是在演化过程中考虑了边权对网络结构演化的影响。模型的演化规则如下：每个时间间隔有一个新节点j加入网络中，并选择一个老节点i建立一条连接，其连接概率正比于节点的强度：6.3.1边权固定模型34上述模型都忽略了当新节点或边进入系统时边权演化的可能性。事实上，相互作用关系的演化和加强是现实系统共同的特征。例如，在飞机航线网络中，两机场间新航线的建立通常会影响到两个机场的客流量以及与其相关的航线的客流量。6.3.2边权演化模型35Barrat-Barthélemy-Vespignani(BBV)基于点强度驱动和边权逐渐加强机制建立的网络演化模型，可以模仿现实系统中相互作用强度的变化。权重分配示意图：6.3.2边权演化模型36Dorogovtsev-Mendes(DM)是一个边权演化模型，权重大的边增加权重，然后吸引新的连接。DM模型的演化规则示意图：6.3.2边权演化模型37流驱动的加权网络模型不仅考虑了新节点加入的影响，同时还考虑了边权随时间的演化以及老节点之间新边的生成。权重变化规则：带有m条边的新节点n按下面的规则与老节点随机连接：6.3.2边权演化模型38加权网络演化模型应该符合3个基本要求：边权演化、一般性、不需要额外的非网络信息。科学家合作网络的实证研究为构造加权网络演化模型的启示：新老节点每一时刻都可以建立新的连接，并允许节点间的重复连接，通过简单的函数关系把连接次数转化为权重，就可以研究在各种驱动机制下的加权网络演化模型。连接次数依照权重或度进行演化，然后，新的连接次数又转化为边权，再次驱动系统的演化6.3.3基于科学家合作机制的加权网络演化模型39基于科学家合作网的加权网络演化模型6.3.3基于科学家合作机制的加权网络演化模型6.4空间网络4041社会网Internet网络航空网络其他网络6.4.1空间网络的实证研究42社会网社会网络的空间距离分布呈幂律特征，即朋友之间距离的概率密度函数满足幂律分布。通过利本-诺威尔、阿达米克、埃达等人的研究案例，说明社会网络的空间距离分布的幂律特性。从人们追求信息量最大化的角度，因此社会网络空间结构中幂律特性的普适性。6.4.1空间网络的实证研究43Internet网络Internet

节点位置关系和人口分布具有强相关性。通过盒覆盖方法计算网络分形维度，与人口分布分形维度吻合。讨论科学技讨论科学技术发展对通信距离的影响，以及空间因素对网络性质的影响。术发展对通信距离的影响，以及空间因素对网络性质的影响。6.4.1空间网络的实证研究44航空网络航空网络受到多种因素的影响，例如地理位置、历史、政治因素、航空公司利益等。通过吉梅拉、杨华等人的研究案例，说明全球航空网络和日本航空网络均存在幂律特性。指出美国航空网络的距离分布也服从幂律分布。6.4.1空间网络的实证研究45其他网络介绍人脑网络的空间结构研究，指出其具有小世界特性，并指出当前研究的不足。其他空间网络广泛存在，例如电力网络、交通网络等。6.4.1空间网络的实证研究46Kleinberg导航模型6.4.2基于网格的导航模型(a)p=1，q=0的6*6二维网格，(b)p=1，q=2的6*6二维网格47如果说一个网络的搜索时间复杂度随着网络的规模呈对数多项式增