2. 北京航空航天大学 中法工程师学院, 北京 100191
复杂网络研究促使了大量复杂网络模型的产生，用于描述抽象的复杂网络[1-2]，如随机网络模型[3]、ER模型[4]、小世界模型[5]、BA模型[6]等。同时，社交网络应用的兴起使得网络动态性与演化机制成为了重要的研究问题。针对有权网络，Barrat等对无向加权网络提出了简单加权网络演化模型，把节点强度引入到演化规则，被称为BBV模型[7]。BBV模型很好地刻画了无向加权网络中新节点加入引起的基于节点强度的新的边的生成，以及网络局部的边权重的动态变化。通过对BBV模型进行扩展，如对演化规则引入网络社区[8]、节点吸引力[9]、节点相关性[10]、加权节点介数[11]等网络属性，产生了一系列研究结果。针对有向加权网络，入节点强度与出节点强度被引入至演化规则，以刻画新节点的加入引起的新的有向边的生成[12-13]。
以上网络演化模型大多基于2个假设：常量平均度假设和网络直径缓慢增长假设[6, 14]。常量平均度假设指网络的平均节点度随着时间变化仍为一个常数，即网络的边数关于节点数为线性增长关系；网络直径缓慢增长假设是指随着网络的增大，其直径是缓慢增长的。文献[15]通过对美国专利引用网络、论文引用网络、电影和产品推荐网络、邮件网络等不同类型的现实网络进行分析，指出网络在演化过程中具有稠密幂律(densification power laws)和直径收缩(shrinking diameters)的性质，即随着网络的演化，其平均度增加，且有效直径(effective diameter)变小，并提出了有向无权网络演化的森林火灾模型。然而，该模型仍无法适合于有向加权网络。
本文针对现有有向加权网络演化模型无法支持稠密幂律和直径收缩性质的问题，提出了一种新的演化模型BBVd。该模型扩展了BBV模型，支持有向加权网络演化，且使得生成的有向加权网络满足稠密幂律和直径收缩的性质，符合现实网络特征。
1 BBV网络演化模型BBV网络演化模型是针对一类无向加权网络建立的演化模型[7]，其演化的思想为：当网络中有新节点n加入时, 网络中已有节点的节点强度(即与该节点相连的所有节点的权重的和)越大, 则该节点与新节点n相连的概率越大。
无向加权网络G是一个无向加权图(V, E, W), 其中
1) V={1, 2, …, N}为G的节点集合;
2) E为G的边集合, 满足节点i与j有边相连当且仅当(i, j)∈E;
3) W=(wij)N×N是G的加权矩阵:wij表示节点i与j相连的边(i, j)的权重。
假设若网络G中存在边(i, j), 则边(i, j)的权重wij一定大于0;反之若wij=0, 则认为节点i与j之间无边相连。
节点强度的概念是对无权网络的节点的度的概念的扩展, 使其既能包含节点的度的信息, 同时也能表示有权网络中边的权重信息。
设G=(V, E, W)是一个无向加权网络。对V中任意的结点i, 令Γi表示i的邻居节点集合, 即Γi={j|(i, j)∈E}, 则节点i的节点强度si为
|
即, si是以节点i为顶点的所有边的权重的和。
BBV模型的主要步骤是[7]:
第1步 初始设定
在初始时刻t0, 初始网络G0=(V0, E0)是包含N0个节点的全耦合网络, 其中V0={1, 2, …, N0}, 且G0中所有边的权重均初始设为w0。
第2步 节点与边的加入
每个时间步增添一个新节点, 并增加该节点与已有节点之间的边。具体地, 假设在tk时刻的网络为Gk=(Vk, Ek)。在下一时刻tk+1, 加入一个新节点n, 且节点n与Gk中m个节点相连, 即每次新加入m条边, 节点i∈Vk被选择的概率为:
|
式中，si为节点i的节点强度。因此, 连接节点的选择按节点权重的大小优先进行。
第3步 权值的动态演化
每次新加入的边(n, i)均被赋予权值w0, 并动态调整节点i与其邻居节点j∈Γi的边权值wij
|
式中, 
每次新引入的一条边(n, i)会给i带来新的流量负担δi, 且与节点i相连的每条边(i, j)按其权重wij的大小承担部分流量。据此, 节点i的节点强度si变为
|
BBV模型很好地刻画了在无向加权网络中, 新节点的加入引起的基于节点强度的新的边的生成, 以及网络局部的边权重的动态变化。然而, 现实网络中有很多是有向加权网络, 以论文引用网络为例, 节点u到v有一条边, 表示节点u代表的论文引用了节点v代表的论文。另外, 文献[15]通过对现实网络进行分析, 指出网络在演化过程中具有稠密幂律和直径收缩的性质, 即随着网络的演化, 网络的平均度增加, 且有效直径变小, 其中有效直径d是满足网络中90%的节点对之间的无向最短路径都不超过d的最小值。因此本文基于BBV模型提出有向加权网络的演化模型BBVd, 且满足稠密幂和直径收缩的性质。
给定一个有向网络G=(V, E, W), 其中E为有向边集合。对于G中任意2个节点i和j, e(i, j)是从节点i到节点j的一条边, w(i, j)表示e(i, j)的权重。显然, 在有向网络中, w(i, j)与w(j, i)不一定相等。
对于节点i, 定义Γiout包含i的所有出边到达的节点的集合, Γiin包含所有通过i的入边到达i的节点集合, 即
|
如下定义节点i的入节点强度(in-strength)siin与出节点强度(out-strength)siout
|
则i的节点强度si定义为i的入节点强度与出节点强度的和, 即si=siin+siout。
以论文引用网络为例, 假设权w(i, j)表示节点j所代表的论文被引用的次数, 相应地, 节点i的出节点强度表示它引用的所有论文的被引用次数的和, 而j的入节点强度表示j被引用次数的平方。
文献[15]提出了森林火灾模型, 使得演化后的网络满足稠密幂律和直径收缩的性质。直观上理解, 森林火灾模型的思路是:设在时刻t的网络为Gt, 节点v在时刻t加入网络; 首先v从Gt中随机选择一个节点w, 增加边e(v, w); 然后生成2个随机变量x与y分别服从平均值为p/(1-p)与rp/(1-rp)的几何分布, 其中, p是火灾向前燃烧概率(forward burning probability), r=p/pb是火灾向后燃烧率(backward burning ratio), pb是火灾向后燃烧概率(backward burning probability); 节点v选择x个从w有出边连接的点w1, …, wx以及y个到达w的点wx+1, …, wx+y, 即Gt中存在边e(w, wi), i∈[1, x]和边e(wj, w), j∈[x+1, x+y]; 对于这些点中在t时刻前没有被选中过的点, 增加从w到这些点的边, 然后对这些点重复以上步骤, 直至Gt中所有的点被选中。
基于森林火灾的思想, 本文扩展BBV模型, 提出有向加权网络的演化模型BBVd:
第1步 初始设定
在t0时刻, 初始网络G0=(V0, E0, W0)是包含单个节点的网络。
第2步 节点与边的加入
假设G0中所有边的权重均为w0。在每个时间步增添一个新节点并增加该新节点与已有节点之间的边。分2步进行:
1) 假设在tk时刻的网络为Gk=(Vk, Ek)。在下一时刻tk+1, 加入一个新节点v和m条边, 即节点v与Gk中m个节点相连, 且m个节点的选择按节点强度从大到小排列, 即选择节点i∈Vk的概率为
|
2) 假设新增的m条边的端点分别为1, 2, …, m。针对每个端点i∈{1, 2, …, m}, 生成2个随机变量xi与yi, 分别服从平均值为p/(1-p)与rp/(1-rp)的几何分布:
a) 节点v选择xi个从i有出边连接的点u1, …, uxi, 且增加从v到每个点uj(j=1, …, xi)的边, 其中节点uj的选择按入节点强度的大小优先进行, 即节点uj被选择的概率为
|
b) 节点v选择yj个到达i的点uxi+1, …, uxi+yi, 且增加从v到每个点uk(k=xi+1, …, xi+yi)的边, 其中节点uk的选择按出节点强度的大小优先进行, 即节点uk被选择的概率为
|
对增加的节点u1, …, uxi, uxi+1, …, uxi+yi递归重复以上过程, 直到Vk中的所有点都被访问到。注意, Vk中的点只能被访问一次。
第3步 权值的动态演化
每个时间步网络中新增加的边被赋予权值w0。注意到, 增加的边均为新增节点v的出边, 因此新增出边e(v, i)只对i的所有入边的权重进行影响:对i的任意邻居j, 当Ek中存在边e(j, i)时
|
式中, 
区别于文献[12-13]中的演化模型, BBVd对BBV模型引入了森林火灾模型的思想, 在每个时刻t, 不仅对新加入的点v生成m条边, 还对这m条边的端点i的邻居节点u根据其入节点强度与出节点强度分别生成v到u或u到v的边, 从而使得BBVd生成的网络能够满足稠密幂律和直径收缩性质。
3 实验及分析实验实现了加权有向网络演化模型BBVd, 并验证了入节点强度与出节点强度的密度函数均服从幂律分布, 并满足稠密幂律和直径收缩性质。
实验部署在1台CPU为Intel(R) Core TM i7 960 3.20 GHz CPU, 12 GB内存, 1TB硬盘的服务器上。操作系统为Windows Server 2007, 方法实现语言为C++。
文献[15]指出网络在演化过程中在时刻t的边数e(t)与节点数n(t)有以下关系
|
式中：a∈[1, 2]是实数, 且a越小表示网络越稀疏, a越大表示网络越稠密, 且a=2时表示任意2个节点之间都有一条有向边, 是一个全耦合图。
下面针对以上演化模型, 通过仿真实验检验模型节点的幂律特性。在仿真实验中, 取w0=1.0, δ=1.0, m=3, p=0.37, pb=0.32。同时, 实验检验了生成的网络具有稠密幂律性质和直径收缩性质。
如图 1至2所示, 当节点数为5 000时, 入节点强度与出节点强度的密度函数服从幂律指数分别为1.21与1.59的幂律分布。通过观察, 随着网络规模的扩大该幂律指数不会发生变化。
|
| 图 1 入节点强度分布 |
|
| 图 2 出节点强度分布 |
如图 3所示, 生成的网络均具有稠密幂律的性质。同时, 除了过于稀疏的网络(a=1.06)外, 生成的网络均具有直径收缩(shrinking diameters)的性质。如图 4所示, 当a=1.06时, 网络的直径是缓慢增加的; 当a分别等于1.24, 1.34和1.60时, 生成的网络的直径均减小, 且a越大, 减小的趋势越大。
|
| 图 3 稠密幂律 |
|
| 图 4 有效直径 |
本文针对现有有向加权网络演化模型不满足现实网络演化具有的稠密幂律和直径收缩性质的问题，基于森林火灾算法的思想，对BBV模型进行扩展，提出了加权有向网络演化模型BBVd。仿真实验结果表明，BBVd不仅满足BBV模型提出的节点强度分布符合幂律分布，同时还满足稠密幂律和直径收缩的性质，符合现实网络的特征。
| [1] | RWAL C, SUBBIAN K. Evolutionary Network Analysis: a Survey[J/OL]. (2014-05-15)[2019-08-30]. https://dl.acm.org/doi/10.1145/2601412 |
| [2] | COOLEN T, ANNIBALE A, ROBERTS E. Generating Random Networks and Graphs[M]. Oxford University Press, 2017. |
| [3] | SOLOMONOFF R J, RAPOPORT A. Connectivity of Random Nets[J]. Bulletin of Mathematical Biology, 1951, 13(2): 107-117. |
| [4] | ERDÖS P, RÉNYI, A. On the Strength of Connectedness of a Random Graph[J]. Acta Mathematica Academiae Scientiarum Hungaricae, 1964, 12(1/2): 261-267. |
| [5] | WATTS D J, STROGATZ S H. Collective Dynamics of 'Small-World' Networks[J]. Nature, 1998, 393(6684): 440-442. DOI:10.1038/30918 |
| [6] | BARABASI A, ALBERT R. Emergence of Scaling in Random Networks[J]. Science, 1999, 286(5439): 509-512. DOI:10.1126/science.286.5439.509 |
| [7] | BARRAT A, BARTHELEMY M, VESPIGNANI A. Weighted Evolving Networks: Coupling Topology and Weight Dynamics[J/OL]. (2004-06-04)[2019-08-30]. https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.92.228701 |
| [8] | WANG D, QIAN X, JIN X. Dynamical Evolution of Weighted Scale-Free Network Models[C]//24th Chinese Control and Decision Conference, Taiyuan, 2012 |
| [9] | DENG X, WU Y, LI D, et al. A Weighted Network Model Based on Node Fitness Dynamic Evolution[C]//IEEE 22nd International Conference on Parallel and Distributed Systems, 2016 |
| [10] | DENG X, WU Y, DONG M, et al. A Weighted Network Model Based on the Correlation Degree Between Nodes[C]//11th International Conference on Mobile Ad-Hoc and Sensor Networks, Shenzhen, 2015 |
| [11] | TOPIRCEANU A, UDRESCU M, MARCULESCU R. Weighted Betweenness Preferential Attachment: a New Mechanism Explaining Social Network Formation and Evolution[EB/OL]. (2018-07-18)[2019-08-30]. https://www.nature.com/articles/s41598-018-29224-w |
| [12] | WANG G, ZHOU J, XIE Y. Directed Weighted Network Model Based on BBV[J]. Computer Engineering, 2010, 36(12): 142-143. |
| [13] | MASUCCI A P, RODGERS G J. Multi-Directed Eulerian Growing Networks[J]. Physica A 386, 2007: 386. |
| [14] | BRODER A Z, KUMAR R, MAGHOUL F, et al. Graph Structure in the Web[J]. Computer Networks, 2000, 33(1/2/3/4/5/6): 309-320. |
| [15] | LESKOVEC J, KLEINBERG J, FALOUTSOS J. Graph Evolution: Densification and Shrinking Diameters[J/OL]. (2007-03-15)[2019-08-30]. https://dl.acm.org/doi/10.1145/1217299.1217301 |
2. Sino-French Engineer School of Beihang University, Beijing 100191, China
