加权确定性复杂网络某些特性研究 郁伯铭，鲁 芬，陈 牧 华中科技大学 物理学院

Presentation on theme: "加权确定性复杂网络某些特性研究 郁伯铭，鲁 芬，陈 牧 华中科技大学 物理学院"— Presentation transcript:

1 加权确定性复杂网络某些特性研究 郁伯铭，鲁 芬，陈 牧 华中科技大学 物理学院 yuboming2003@yahoo.com.cn
第七届全国网络科学论坛，北京 加权确定性复杂网络某些特性研究 郁伯铭，鲁 芬，陈 牧 华中科技大学 物理学院 2019/4/9

2 内容提要 一、确定性复杂网络概论 二、确定性复杂网络(DCN)的加权方式 三、加权确定性复杂网络(DCN)静态统计特性
五、总结 2019/4/9

3 Barabási, A.-L., Ravasz, E., & Vicsek, T.，
一、确定性复杂网络概论 Deterministic Scale-Free Networks (DSFN) Barabási, A.-L., Ravasz, E., & Vicsek, T.， (2001) Physica A 299, 559. 2019/4/9

4 Clustering coefficient scales
Hierarchical Networks (HK) Clustering coefficient scales 2019/4/9

5 E. Ravasz and A-L. Barabási, Phys. Rev. E 67, 026112(2003)
RB模型的叠代过程： E. Ravasz and A-L. Barabási, Phys. Rev. E 67, (2003) 2019/4/9

6 Our deterministic complex network (DCN)
Mu Chen, Boming Yu et al., Physica A 385, 707 (2007). 2019/4/9

7 比较： 1、 DSFN和HK存在自相似性和分形特征； 2、 我们的DCN 不具有自相似性和分形特征；
2019/4/9

8 DCN的基本特征 n步叠代后，节点的总数： N(n)与n满足指数增长关系； 总的边数： 平均度<k>：
<k>与n满足线性增长。 聚类系数： 平均最短路径： 2019/4/9

9 平均路径长度： 当DCN网络大小 趋于无穷大时， 其平均路径长度 趋近于2， 是一个恒量。 2019/4/9

10 DCN模型与随机网络，BA模型随N增长趋势的对比
2019/4/9

11 聚类系数: 当N增大时， DCN模型的 聚类系数C 缓慢增长并趋于1. 2019/4/9

12 --- DCN模型比BA模型的聚类系数大，稳定， 能更好的模拟现实网络。
随着网络的增长， BA模型的聚类 系数C迅速减小， 而DCN模型的C 基本保持不变， 近似为1。 --- 现实网络通常具有大的聚类系数 --- DCN模型比BA模型的聚类系数大，稳定， 能更好的模拟现实网络。 Mu Chen, Boming Yu等, Physica A 385, 707(2007). 2019/4/9

13 二、确定性复杂网络(DCN)的加权方式 --- 许多实际网络都可抽象为加权网络； --- 不同的实际网络节点代表的意义不同，
节点间作用的强弱程度可通过边的权重来描述； --- 构造适当的加权复杂网络以模拟实际的复杂网络 及其动力学演化特性，便于复杂网络的实际应用。 加权网络：包括N个节点，以及一组带有权重的边W的集合。 边权：个体间连接的紧密程度或相互作用强度（物理权重、抽象权重） 。 点权：即节点强度，表示节点的某种适应度，它包含了节点的连接度和所有与其相连的边的权重信息。 2019/4/9

14 可采用三种边权重赋予方式构建确定性加权复杂网络：
边权为常数 赋 权 方 式 边权服从指数分布 边权服从节点度乘积函数 2019/4/9

15 分别用上面三种方式给DCN模型的边赋值，
--- 计算各节点强度，作出点权分布曲线，分析结果； ---根据边权赋予方式计算加权DCN模型的 加权聚类系数、加权平均路径长度，进行分析； ---结合实际网络抽象出相对应的DCN模型， 进行权值研究 。 2019/4/9

16 以n=5的DCN模型为例，分析在给每条边赋值之后 得到的加权DCN网络的特点，进而研究加权DCN
网络的节点强度分布，加权聚类系数和加权平均路 径长度等加权网络特征量，得到加权DCN网络的特点。 2019/4/9

17 研究方法：同一层各节点的度相同，点权相同， 聚类系数相同，平均最短路径亦相同， 故在研究加权DCN网络的时候，只需
i层节点的度： i层节点数： 总节点数： 总边数： 研究方法：同一层各节点的度相同，点权相同， 聚类系数相同，平均最短路径亦相同， 故在研究加权DCN网络的时候，只需 按层数取该层的某一个节点出来研究， 该层的其他节点和该节点的性质一样。 2019/4/9

18 设：具有从属关系的节点间边(黑色)权重为1，隔一 代的节点间边(绿色)权重为2，隔两代的节点间边(蓝色)
（1）边权为常数（边权不等） 设：具有从属关系的节点间边(黑色)权重为1，隔一 代的节点间边(绿色)权重为2，隔两代的节点间边(蓝色) 权重为3，隔三代的节点间边(天蓝色)权重为4， 隔四代的节点间边(粉红色)权重为5。 由点权的定义式： 表示所有与节点i相连的节点的集合。 2019/4/9

19 si （节点强度） 得到： ，见表1： i(节点层数) 1 2 3 4 5 6 258 99 37 16 12 15
各节点点权均很大，即都比较重要，且随着层数的 增加而递减。 2019/4/9

20 如果设每条边的权重都相同，都为1，再计算整个 加权DCN网络的节点强度，此时
边权相等: 如果设每条边的权重都相同，都为1，再计算整个 加权DCN网络的节点强度，此时 边权为1的确定性加权复杂网络节点强度分布(P(Si))： 2019/4/9

21 加权DCN网络的节点强度近似服从幂律分布,
（γ=1） 2019/4/9

22 （2）边权服从指数分布 假设在加权复杂网络中边的权重服从指数分布； 参数 θ>0 ，w>0
节点i的强度分布P(s)可看作是ki个相同参数的指数分布的概率密度函数： 其中 ki是节点i的度 2019/4/9

23 各种参数下确定性复杂加权网络节点强度分布图：
节点i的强度服从Gamma分布，不具备幂律特征。 2019/4/9

24 3.边权服从节点度乘积函数 设节点i与节点j的度分别为ki和kj，则连接这2个节点的边权重满足关系式： 可有效地调节节点的强度大小。
由DCN模型的规则性和层次感, 知同一层任意节点 的点权相同，由点权定义式， 表示所有与节点i相连的节点的集合。 2019/4/9

25 考虑第i层的某个节点m，计算m节点的强度
1）节点m与1层到i-1层直系亲属节点是直接相连的： 2）节点m以下i+1层到n+1层所有直接子亲属节点 与m是直接相连的,其节点强度为Si2 , 因此，加权DCN网络第i层的任意节点m的强度为： 2019/4/9

26 2019/4/9

27 （1）α=0.5和0.02时确定性加权复杂网络点权分布 (a)节点强度分布在一定范围内呈现幂律分布规律；
(b) α减小时点权分布的幂律特性越明显 ； （γ=0.70） 2019/4/9

28 点权s(k)随着节点度k近似以幂律形式s(k)~ka增长； α减小时，点权与节点度的幂律关系越明显。
（2）确定性加权复杂网络点权与度关系 点权s(k)随着节点度k近似以幂律形式s(k)~ka增长； α减小时，点权与节点度的幂律关系越明显。 2019/4/9

29 小结： 赋权方式 常数权重 指数分布 节点度乘积函数 节点i的强度服从Gamma分布： s～Ga(ki,θ), 不具备幂律特征。
边权不等：各节点点权均很大且随着层数的增加而递减。 边权相等：从整体上来看点权是幂律分布的（类似于无权DCN的幂律度分布） 节点i的强度服从Gamma分布： s～Ga(ki,θ), 不具备幂律特征。 点权分布和点权与节点度之间都满足幂律关系，且α越小幂律特征越明显；可以根据实际需要改变参数α的值来有效调节点权的大小，从而更接近实际网络，达到很好的模拟效果 2019/4/9

30 边权服从节点度乘积函数的确定性加权复杂网络
1 2 3 对于给定规模的加权DCN网络，当α逐渐变大时节点强度迅速增长，从而能够设置不同的参数用于模拟不同的实际加权网络，很方便、灵活 点权s(k)随着节点度k以幂律形式s(k)~ka增长, α越小幂律关系越明显，从而可根据实际加权网络的要求设置不同的α值，有效调节网络节点强度的大小以适合于实际网络。 节点强度分布遵从幂律分布，且随着参数α的减小，幂律特征越明显 2019/4/9

31 三种边权赋予方式中，边权服从节点度乘积方式最 贴合实际的需要，不仅点权分布P(s)是幂律关系的， 而且点权与节点度之间也满足幂律关系：
（1）节点强度是服从幂律分布的，且随着参数 的减小，幂律特征越明显； （2）对于给定规模的加权DCN网络，当 逐渐变大时，节点强度迅速增长，从而能够设置 不同的参数用于模拟不同的实际加权网络，很方 便、灵活； （3）点权与节点度是关联的，且S(k)随着k以幂律形式 a s(k)~k a 增长， 越小幂律关系越明显， 从而可根据实际加权网络的要求设置不同的 值，有效调节网络节点强度的大小以适合于实际网络。 2019/4/9

32 三、加权确定性复杂网络(DCN)静态统计特性
1、加权聚类系数(Weighted clustering coefficient ) 考虑到在一个点的邻点中, 有的邻点相比其他的邻点更重要, 即要考虑相关边的权重问题. Barrat等人定义的加权网络聚类系数： , 否则为0。 为连接标志, 当节点i和j有连接时， Barrat A., etal., Proe. Natl. Acad. Sci. U.S.A.101, (2004) 2019/4/9

33 所有节点加权聚类系数的平均值即DCN网络整体的 加权聚类系数：
2019/4/9

34 (a)、(b)的分析可以知道当边权重服从度乘积函数时， 加权DCN网络的加权聚类系数随着网络大小的增长而 增长，最后趋于定值0.5。
可有效调节节点强度大小和加权聚类系数的增长 速度，但不能改变加权聚类系数的稳定值。 2019/4/9

35 不加权 加权 加权和无权DCN网络的聚类系数进行对比 2019/4/9

36 无权DCN网络中,未考虑边权重不同，即没有考虑 某节点相比其他节点更重要等问题， 因此无权聚类系数对真实网络的模拟意义不大；
而加权聚类系数正是考虑了以上所说的实际问题， 导致其值较之无权聚类系数值要小，但它是实际 网络的真实反映，对实际网络的模拟起到了 一定的参照作用。 2019/4/9

37 加权DCN网络(N=2047)中加权聚类系数与度的关系
2019/4/9

38 也就是说度大的节点属于平均聚类系数小的连通社 区，而度小的节点属于平均聚类系数大的连通社区；
随着 对于给定规模的加权DCN网络 的增长而呈下降的趋势，而且 越小，下降越快； 当 =0.1时， 随着 的增长呈幂律形式下降； 也就是说度大的节点属于平均聚类系数小的连通社 区，而度小的节点属于平均聚类系数大的连通社区； 因此，通过改变 的值， 可以找到合适的 与k 的关系，从而对实际网络进行很好的模拟。 2019/4/9

39 小结 ⑴ cw随着N的增长而增长，最后趋于定值0.5 ；a可有效调节节点强度大小和加权聚类系数的增长速度，
⑵ 无权DCN未考虑边权重不同、某节点相比其他节点更重要等问题，cN→∞=1，对真实网络模拟意义不大；而加权DCN则考虑了上述问题和实际网络的复杂性，cwN→∞=0.5 ，更真实反映实际网络。 ⑶ cw(k)随着k的增长而呈下降的趋势;可改变a的值找到合适的cw(k) ~k关系，从而对实际网络进行很好的模拟 。 2019/4/9

40 2、加权最短路径(weighted shortest path)
加权网络最短路径是指两节点之间所有连通的路径 中权重之和最小的一条或几条路径. 由于权重分为 相异权和相似权，所以最短路径和权重的关系也分 为两种，本文采用相异权进行研究。 两个直接相连的节点之间的距离： 以j点作为中介的两节点i和k之间的距离： 2019/4/9

41 加权DCN网络的平均最短路径长度： 2019/4/9

42 ① Lw~N (a)不同α下Lw随着N的增大在逐渐增长，α=10-7时，LwN→∞ =2.0；α=10-3时
(b)在较大α值下随N的增长Lw的值始终都在增长， α越大Lw的值增长越快， 很难达稳定。 2019/4/9

43 ② Lw与L的对比 加权 不加权 2019/4/9

44 小结 ⑴Lw随着N的增大也在逐渐增长；0<α<10-7时LwN→∞=2.0达稳定，且α越小，Lw趋于2的速度越快；α>10-7时, 在较小α值下Lw才能达稳定且LwN→∞>2.0,说明两个节点相连平均必须经过一个根节点; ⑵无权DCN中LN→∞=2.0未考虑现实网络的复杂性，各边权重不同的问题，距离过于简单，对实际网络的模拟意义不大，有局限性，而加权DCN中LwN→∞ ≥2.0，可根据实际情况改变α的值来调节加权平均路径长度的稳定值使其适应于现实网络，达到更好的模拟效果。 2019/4/9

45 四、加权DCN网络实例 道路交通网络 2019/4/9

46 人际关系网：学校关系简网 2019/4/9

47 爷，奶辈 太爷，太奶辈 父，母辈 儿女辈 家谱图网 2019/4/9

48 五、总结与展望 总结： 1、用三种边权重赋予方式，分析了确定性加权复杂网络的点权分布情况，得到了加权DCN 的特性。
2、研究了确定性加权复杂网络的特征量:加权聚类系数、 加权平均路径长度，并与无权DCN的特征量进行比较， 发现加权DCN网络模拟实际网络更具优势。 展望： 1、在各种打击方式下，确定性加权复杂网络的稳定性。 2、有方向性的确定性加权复杂网络的特性研究 。 2019/4/9

49 Thank you! 2019/4/9