复杂网络9讲-加权网络ppt课件.ppt

第八讲加权网络 2010 11 13李凯凯 1 8 1加权网络的统计性质8 2加权网络的演化模型8 3权重对网络结构性质的影响 主要内容 2 8 1加权网络的统计性质 加权网络的加权的必要性与方式加权网络上的统计量 3 网络加权的必要性与赋权方式 网络加权的必要性 例 为研究某一新思想的在一个学术领域的产生传播 研究科学家之间通过文献相互作用的网络 相互作用分为三个层次 合作 引文 致谢 无权网中能体现相互作用的三个层次吗 我们可以根据不同的作用关系做三个网络 合作网络 引文网络 致谢网络 但即便对于同一个网络比如引文网络 引文次数不同所代表的相互作用关系不同 无权网中能表现相互作用的强度吗 这时必须考虑赋边权 表示相联系的强度 另外 我们希望在同一个网络中研究这三个层次的相互作用 还应该考虑加权的方式 当系统中包含同一属性的不同层次的关系的时候 必须仔细研究加权方式 4 加权的方式 根据相关的物理量 例如 电阻网络边上的权值代表电阻值 邮递员问题中的距离 根据相互作用的某种属性 例如 科学家通过文献相互作用 把引文的次数作为权重 边权按照意义划分 相异权 权值越大 两点之间的距离越大 关系越疏远 例 邮递员问题中的距离 相似权 权值越大 两点之间的距离越小 关系越亲密 例 科学家合作网中 把次数作为权重 得到相似权 注意 在计算两点间的距离和聚类系数时 边权的意义不同 计算方式也不同 5 2 加权网络上的统计量 权相关性最短路径集聚系数 6 权相关性 1 基本概念 点权 无权网中节点度的自然推广点权 即与节点i关联的边权之和 其中是节点i的近邻集合 单位权 顶点连接的平均权重 权重分布的差异性 表示与i相连的边权分布的离散程度 拥有相同点权与单位权的两个节点相比 差异性越大 离散程度越大 点强度分布P s 与度分布的作用类似 主要是考察节点具有点强度s的概率 边权分布P w 代表一条边具有权重w的概率 7 结论2 差异性与度k的关系如果与顶点i关联的边的权重值差别不大 则与成正比 如果权值相差较大 那么只有一条边的权重起主要作用 则 8 2 相关性分析加权网络需要进行度相关性分析点权相关性分析权与度相关性分析度相关性分析 因为对网络加权不改变节点的度的性质 所以度相关性分析与无权网络中分析相同 在无权网络中 定义节点i的近邻平均度 得到度为的所有节点的近邻平均度显然Knn k 是k的函数 那么度相关性可以通过函数Knn k 的单调性得到 如果Knn k 是无单调性 那么该网络没有度相关性 如果Knn k 是增函数 那么该网络是同向匹配网络 度大的节点倾向于与度大的节点相连 如果Knn k 是减函数 那么该网络是负向匹配网络 9 在加权网络中 定义节点的加权平均近邻度考虑权与度的相关性当时 具有较大权重的边倾向于连接具有较大度值的点当时 具有较大权重的边倾向于连接具有较小度值的点所以 对于相互作用强度 权重 给定的边 表明它与具有不同度值的顶点之间的亲和力 10 最短路径 1 加权网络中两点之间的距离与权重的关系 距离是权重的某种函数 这时需要看权重是相似权还是相异权 相异权 定义两点之间的距离相似权 令假设顶点i和k分别通过两条权重分别为和的边相连 现求i与k之间的距离 对于相异权 对于相似权 2 最短路径 两点之间所有连通的路径中距离之和最小的一条或几条路径 无权网 边数最少的路径最短路径加权网 因为距离不满足三角不等式 所以两边距离之和不一定大于第三边 边数最少的路径最短路径网络的其他全局统计量 如介数 可以在加权最短路径的基础上进行计算 11 集聚系数 节点i的聚类系数反映了该节点邻点的联系的程度 越大 说明该点的邻接点之间的联系越紧密 加权网络中的聚类系数有多种定义方式 Barat定义 分母上为单位权乘以最大可能的三角形的数目 分子上是实际三角形数目乘以与i相连的边的权重的平均值Onnela定义 其中wij为网络中经最大权重标准化后的数值 12 PetterHolme分析加权网络的聚类系数 指出它应该满足以下几条要求 1 2 加权网退化为无权网时 聚类系数应与Watts Strogatz定义的聚类系数的计算结果一致 3 权值为0表示该边不存在 4 包含节点i的三角形中三条边对的贡献应与边的权重成正比 Watts Strogatz定义的聚类系数 加权网的聚类系数 13 一些加权网络的实证结果 1 生物网络Almaas等人将酵母中的新陈代谢反应看作加权网络进行研究 把从代谢物i到j的流量看作边权 观察到流量具有高度非均匀性 在理想的培养下条件下 边权的分布符合幂律分布其中 此外还发现给定两端度值的边的权重平均值和两个端点的度值的关系为 其中 除了全局流量分布的非均匀性外 计算边权差异性还可以观察到在单个代谢物的层面上边权分布的非均匀性 在此网络上对出度和入度相同的顶点计算边权差异性 发现它们都服从这是一种介于和之间的中间状态 说明一个代谢物参与的化学反应越多 其中的某一个化学反应携带主要流量的可能性就越高 14 2 社会网络以科学家合作网为例 Newman定义了科学家合作网的权重 其中p包括数据库中的所有文章 如果i是文章p的作者之一 则 否则 表示文章p中作者的数目 从平均效果来看 合作者较少时作者之间的相互关系更加紧密 15 3 技术网络在一些基础设施网络中 例如Internet 铁路网和航空网中 运输过程中的流量可以转化为权重 Barrat等人分析了全球航空网络 把两机场i和j之间的航班的有效座位数作为机场间的权重 而李炜等人在研究中国航空网时 把两机场间的航班数作为机场间的权重 在对不同数据进行研究时 发现这些网络具有小世界网络和无标度网络的特征 特别是度分布表现为如下形式 其中 且是指数截断函数 与一个机场能够运作的最大航线数有关 点强度分布呈现出幂律尾 并且边权和度具有一定的相关性 平均来讲 边权与边的两端顶点的度值的函数关系为其中 点强度和度之间的关系服从幂律函数关系 其中 这说明机场越大 处理交通流量的能力就越强 16 经济物理学科学家合作网络的建立和统计分析科学家之间的合作有多个层次 若希望通过网络分析挖掘科学家在科学研究上的内在关联就必须考虑不同层次的相互作用的贡献 而网络连接权重就就需要综合考虑层次和强度两个方面 考虑科学家交流的三个层次 合著 引用和致谢 记录为 作者与合作x次 引用作者的文章y次 并且在的文章致谢里感谢z次 事实上 可以把整个数据看做三个不同的网络 合著网络 引用网络和致谢网络 把这三种关系综合在一起考虑 看做一个网络 采用以下赋权方式 其中可以取 1 2 3 分别对应合著 引用和致谢关系 是三种关系所对应的权重 定义为 17 直观上说 次数越多关系越亲密 但是随着次数的增加 新事件对亲密程度的贡献越来越小 即新事件对亲密程度的贡献具有边际递减效应 因此采用具有饱和效应的tanh函数将次数转化为权重 来刻画次数和亲密程度的非线性效应 假定三种相互作用对权重的贡献也是不同的 用参数表示 在研究经济物理学科学家合作网时 分别取值为0 7 0 2 0 1 18 8 2加权网络的演化模型 边权固定模型边权演化模型应用 研究的意义是什么 例 某一新思想的在一个学术领域的产生传播过程中 随着时间的推移 可能会有更多的科学家介入 增长 同时随着新思想影响程度的加深 已有交流的科学家之间的相互作用强度也会发生变化 权值改变 静态网络显然已经不能揭示加权网络的演化行为 因此在这里研究网络拓扑结构和权重分布的耦合演化机制 来描述新思想传播过程 19 边权固定模型 1 无标度加权网络模型 WSF 2001年 Yook和Barabasi提出了类似于BA模型的加权网络生成模型 其定义如下 1 网络拓扑结构的演化 同BA模型 增长 初始时有n0个节点 每个时间间隔加入一个新节点j 并使新节点j与m个已经存在的点连接 m n0 择优连接 新加入的点与网络中已经存在的点的连接不是等概率的 而是以一种择优的方式选择与自己连接的点 新节点j与节点i连接的概率 2 赋边权 基于两个假设 权重Wij正比于节点i的度 所有新节点有相同的点权 新节点与已存在节点之间的每一条连接ji 被赋予一定的权重 权重的多少取决于被连接节点i的度 i 代表新节点j所要连接的点的集合 这时新节点j的点权为1 20 无标度加权网络模型特点 拓扑结构与BA模型相同 故度分布点权分布符合幂律分布 其中指数与参数m有关 边权分布 21 ZTZH模型在WSF模型的基础上进行推广 赋边权时综合考虑节点的度和适应度 适应度 反应节点i本身的性质 假设其服从 0 1 上的均匀分布 当不知道随机变量取值的特点时 假设其服从某一区间上的均匀分布 1 网络结构拓扑演化同WSF网络 2 赋边权 设定一参数p以概率p按公式赋边权以概率1 p按公式赋边权当p 1时 ZTZH模型 WSF模型当p 1时 边权的赋予完全由节点的适应度决定 ZTZH模型的点强度分布也符合幂律分布 但是指数敏感地依赖于参数p 随着p的增加 从3连续下降 22 Antal Krapivsky提出了一个加权网络的演化模型 改进之处是在演化过程中考虑了边权对网络结构演化的影响 规则如下 每个时间间隔有一个节点j加入到网络中 并选择一个老节点建立连接 其连接概率正比于节点的强度 此规则关注点强度对连接的驱动作用 点强度越大的节点被连接到的概率越大 实际网络中 例Internet网络中 新的路由器会根据带宽或流量的处理能力连接到中枢路由器上 由于每个新顶点只有一条边 所以该模型生成的网络是树形结构的 23 边权演化模型 边权固定模型的共同的特点 边权一旦设定不再改变 也就是说网络中边的权重在初始时刻己经给定 而且随着网络规模的增大 边权没有任何变化 这与实际系统中的情况有很大的差异 比如在航空网络中随着航空网络的增大 与新加机场有连接关系的机场的各条航线上的客流量也会有相应的增加 在加权网络中就表现为边权的增加 这时在加权网络的演化模型中需要考虑边权的演化 下面建立基于点权的边权演化模型1 BBV模型 1 网络结构拓扑演化增长 初始时有n0个节点 每边赋权值为w0每个时间间隔加入一个带有m条边的新节点j 边权也为w0优先连接 根据选择老节点i与新节点j相连 24 2 边权演化新边的加入会导致节点i与其邻居节点之间的边权重重新分配 权重为的新边得加入会给节点i带来一个小的流量增加 然后在所有与i相连的边中按权重所占比例分配增量 分配情况如图所示 25 BBV模型的特点分析 1 度分布 边权分布 点权分布均服从幂律分布 具体地 度分布 说明BBV模型可以生成幂指数介于 2 3 之间的无标度网络 边权分布 点权分布 26 27 2 权与度的相关性点权与网络的拓扑结构有关 其中 可以看到 这里 28 2 DM模型 新加入的点和哪一节点相连 择优的过程 基于度择优 点权择优 其他方式 实例 科学家合作网络 边权设定为能反应合作著作的重要性的数值 它是综合著作的出版时间 著作的影响力等得到的 比如两个科学家在20年前之合作出版了一部著作 那么另外一个科学家与他们合作的几率就会很小 这时网络拓扑演化过程就应该首先考虑到边权大小 DM模型演化规则 网络开始于任意的一组节点和边 1 择优 在已有的节点中 按照与边权成正比的概率选择一条边加权 令该边的权值有一个小的增量 2 增长 加入一个新节点 且该节点与所选边的两端连接 并设新边的权重为1 29 DM模型的特点 度分布 边权分布 点权分布均为幂律分布度分布 边权分布 点权分布 30 总结 BBV模型与DM模型的不同点 择优机制 点权与边权同时考虑 例如 基因网络中 存在某基因活性很高 同时存在一条细胞路径 一条边 非常重要 要加入的新基因既可以和活性高的基因完成一些活动 又可与该边结合进行其他细胞过程的完成 问题是 如何决定新基因的连接 BBV模型和DM模型的共同特点 拓扑结构上 只考虑新节点与老节点相连边权是独立于连接之外的一个基本量 也就是说不管连接的具体程度如何 只要有连接 就按照相同的规则来赋边权 但在实际中 所赋边权的大小往往与连接的程度有关 这时应该做相关方面的假设 即没有考虑边权与度的相关性 BBV模型是以点权为驱动机制 而DM模型是以边权为驱动机制 31 基于科学家合作机制的加权网络演化模型 在科学家合作网络构造过程中作如下的规定 1 每一时刻 新加一个节点连接既可建立于新节点与老节点之间 还可建立于老节点与老节点之间 2 允许顶点之间重复相连 权重看做是连接次数的一个函数 32 模型的基本演化规则 具有N个节点的加权网络可以定义为一个N N的矩阵WN N 其中的每个元素代表相应节点之间的边权 设边权与连接次数Tij之间存在一个函数关系f 即wij f Tij 其中f可取tanh 双曲正切函数 或是线性函数 初始于n0个节点的完全网 每条边的连接次数初始化为Tij 1 并且把权初始化为wij f 1 在每一个时间间隔 1 添加一个新节点 同时从网络中随机选取l个不同的老节点 2 l 1个节点中的每一个节点 用n表示 都可以与其他节点建立m个联系 综合考虑节点的度 节点的强度 边权三方面因素得到节点n连接到节点i的概率 表示与节点n的距离 级数 小于等于d的所有近邻集合 33 3 找到节点i 后 节点n和i 之间的连接次数按下式进行演化 4 边权的演化如下 虽然本模型可以应用于有向网络 但假设模型为无向网络 并且边权与连接次数之间的关系为Wij Tij 34 8 3权重对网络结构性质的影响 无权网络结构性质的改变 通过改变网络的拓扑结构来实现加权网络结构性质的改变 通过改变网络的拓扑结构和调整权重两种途径来实现 网络中有多种统计量来反应网络结构的性质 基本结构 点权 最短路径 聚类系数社团结构 调整权重的途径 第一种 权重集合不变 改变权与边的对应关系第二种 权重的总量或是均值不变 改变权重的分布形式 35 权重调整对基本结构性质的影响1 通过改变权与边的对应关系 研究对基本结构的影响 边权分布不变 2 通过改变权重的分布形式 研究对基本结构的影响权重调整对社团结构性质的影响 36 权重调整对基本结构性质的影响1 通过改变权与边的对应关系 研究对基本结构性质的影响 如何表示权与边的对应关系 给定一个加权网络 引入一个参数p 描述权重和边的匹配关系 将原始网络中权与边的关系降序排列 令p 1表示该原始序列 P 1表示权与边的关系进行反序排列 称之为反权网络 P 0表示保持边的顺序不变 然后从权重集合中随机抽取一个权重分给该边 称之为随机赋权网络 P可以看作新序列与原来序列的相关系数 该变p值就改变了边与权的对应关系 下面考虑p由1变为0和 1时 基本结构性质有何变化 37 研究结果 1 通过无权网络和加权网络的点介数和边介数的对比发现 两者在统计分布上定性一致 但在微观上节点或边的位置或数值发生了变化 2 对p 1原始网 p 0随机加权网 p 1反权网的点权分布 聚类系数分布 边介数 点介数的比较发现 点权分布基本一致 聚类系数分布差别相对明显 边介数分布基本一致 但某一条边的位置在不同网络中差别很大 点介数分布基本一致 高端处变化相对较大 某一点的位置在不同网络中略有改变 结论 原始网络 反权网络 随机权网络以及他们对应的无权网络 各静态统计量的全局分布大致相同 但是细致结构受到了权重的影响 权重和实际网络中的边有特定的匹配关系 不能随便赋权 38 边的序 边介数分布 在加权网与无权网中边介数分布差别相对较大 同一条边的介数值相差相对较大 边介数 实例 边介数反映了这两个科学家交流对整个新思想的传播的影响 加权网中的边介数更能说明这两个人的交流重要的重要性 点的序 点介数 粗线代表加权网细线代表无权网 点介数分布 在加权网和无权网中分布基本一致 只有在高端略有差别 同一个科学家的位置没有变化 但在数值上有明显差别 经济物理学家合作网 39 点权分布 三种情况基本一致 点的序 权重 点的序 聚类系数 聚类系