基于网络熵的小世界网络演化分析

0AASRI Procedia  5 ( 2013 )  274 – 28002212-6716 © 2013 The Authors. Published by Elsevier B.Vunder responsibility of American Applied Science Research Institute doi:10.1016/j.aasri.2013.10.0890ScienceDirect02013 AASRI Conference on Parallel and Distributed Computing and Systems0基于小世界网络演化的分析0网络熵0Liangxun Shuo, Yiying Chen, Zexin Zhang和Wenbin Li*0信息与网络安全实验室，石家庄经济学院，河北石家庄050031，中国0摘要0在规模自由或小世界网络的建模算法中，对节点的修改表示系统组成部分的新陈代谢，而对边的修改则代表系统结构的新陈代谢。由于节点和边的修改，网络结构以及网络的熵都会发生变化。因此，本文使用网络熵来描述系统的代谢过程。基于网络熵，对WS模型进行了分析。结论是，首先WS网络的网络熵变化呈U型。其次，在相同条件下，p的值影响熵图的下降和上升速率。而K决定了从下降到上升的时间。01. 引言01998年和1999年发表在《自然》和《科学》上的两篇文章被认为是小世界网络和无标度网络的开创性研究。0小世界网络[1]和无标度网络[2]的开创性研究。从那时起，复杂网络的实证研究越来越多，引起了复杂网络研究的热潮。0* WenbinLi。电话：+86-0311-87207591；传真：+86-0311-87208591。电子邮件地址：mr.liwb@gmail.com。0在线提供：www.sciencedirect.com0根据知识共享署名-非商业性使用-禁止演绎许可协0根据知识共享署名-非商业性使用-禁止演绎许可协议进行开放获取。0根据知识共享署名-非商业性使用-禁止演绎许可协议进行开放获取。0275  Liangxun Shuo et al. /  AASRI Procedia  5 ( 2013 )  274 – 2800不同网络的结构特征以及各种网络建模算法的发布，引起了复杂网络研究的热潮。目前，复杂网络的研究主要集中在三个领域[3]：网络模型的演化、复杂网络的稳定性、复杂网络的动力学。复杂网络的创建是指网络的形成过程。创建算法被称为复杂网络的演化模型。近年来，这个领域是最活跃的研究领域之一。这个领域的研究主要集中在：网络形成机制的规律、随机图的生成机制和模型、小世界网络的生成机制和模型、无标度网络的生成机制和模型、演化网络的形成机制和确定性网络的形成机制等。尽管这个领域的研究结果相当丰富，但仍然存在一些问题[3]：需要进一步研究小世界效应的新机制，缺乏符合真实系统三个统计特性的随机网络模型；对演化网络拓扑的分析方法的理解仍需探索；考虑动力学和其他因素的模型较少；对现实生活中特定网络的幂律形成机制仍需深入研究。本文重点探讨了WS小世界网络的形成机制，以理解经典演化算法。基于图熵，分析了WS模型生成的网络的特征。对于研究人员来说，本文的方法和结论对进一步解决建模复杂网络的问题具有参考价值。对于提出新的复杂网络模型，本文提供了新的视角。在我们看来，这是一次新的尝试。02. 网络熵与WS模型的分析0从网络的角度来看，系统的生成和演化可以总结为两个方面：一是节点的变化，二是连接的变化[4]。前者代表系统组成部分的新陈代谢，后者代表系统结构的新陈代谢。自然而然地，我们想知道在系统的代谢过程中熵是如何变化的。它是增加、减少、循环或不规则变化？只有对代谢过程有全面的了解，才能对系统进行“控制”。这种“控制”体现在设计更加现实的网络模型中。WS、NW[5]、BA模型（或其他模型）由于网络的节点或边的变化，网络的熵随着结构的变化而变化。因此，使用网络熵来描述系统的代谢过程是很自然的。02.1. 网络熵0假设在系统S中存在多个事件，用S =0n0i01 1，那么Ei的信息量为0i b E p I i log (1)0其中，b为2或自然常数e。从公式（1）可以看出，较小概率事件所携带的信息量大于较大概率事件所携带的信息量。熵被定义为整个系统S的平均信息量，即： (3) 0276     Liangxun Shuo et al. /  AASRI Procedia  5 ( 2013 )  274 – 2800n0n0i E i s p p p I H i 1 1 log     (2)0熵反映了系统的有序程度。熵越大，系统越无序。很容易知道，当所有概率相等时，熵达到最大值。当pi=0（i=1，...，n）时，熵达到最小值0，即Hs>=0。具有N个节点（即S）的复杂网络，其网络熵被定义并归一化为：0其中，pi定义为0n0i i i i d01 / di 表示第i个节点的度。02.2. 基于网络熵的分析算法0为了分析WS模型[1]，我们提出了算法1。在网络演化的过程中，网络熵不断变化。算法1会逐个记录在过程中生成的网络熵。网络熵的趋势反映了WS模型在生成过程中所经历的熵的变化。根据网络熵的变化，可以分析WS模型的特征，从而可以改进甚至提出一个新的模型。算法1中第1行定义的链表用于记录每次迭代中计算出的网络熵。第3行用于选择要重新连接的边e。当满足条件（即1-p<=p'）时，e将被连接（见第6~9行）。1-p越大，p越小。而p'落在阴影区域的可能性较小。换句话说，在较小的p下，IF语句执行的可能性较小。这意味着重新连接e的可能性较小。相反，1-p越小，重新连接e的可能性越大。每次重新连接都意味着网络熵的变化。在重新连接边之后，将计算“新”网络的网络熵（见第11行）。计算得到的网络熵将保存到链表中（见第12行）。链表中记录的网络熵清楚地反映了系统形成过程中的代谢趋势。0算法1. 基于网络熵的WS模型分析算法0输入: 由N个节点组成的环形邻居耦合网络，其中每个节点i与其邻居节点相邻，i = 1, 2,..., K /2，其中K是偶数。这里，K = 2 k (1 <= k <= N / 2)。输出: 网络熵的链接列表。过程:   1.初始化网络熵的链接列表L; //i表示网络中的第i条边  2. FOR(i = 1; i <= N * k; ++i)  3.选择第i条边（表示为e），假设其两个节点分别为：e i 0 ，e i 1 ;  4. 在范围（0,1]内生成一个随机数p';  5. IF(1 - p < p') THEN  //以概率p'随机重新连接网络的每条边0277  梁勋硕等. AASRI Procedia 5 (2013) 274-28006.       随机选择一个节点e，假设它是e i 0 ;  7.       // P表示所有节点的集合  8.在P中随机选择一个节点（假设它是e' i 1 ），e' i 1 不能与e i 0 之前连接过;   9.        将e i 0 与e'i 1 连接;  10.      删除e;  11.      计算当前小世界网络的网络熵;  12.将以上网络熵添加到链接列表L中;02.3. 实验结果和分析0本文在基于算法1的WS模型上进行了一系列实验，旨在揭示主要参数对结构的影响。同时，基于网络熵的变化，对WS模型进行了分析。我们主要考虑了n、K和p的各种组合。实验I.它包括九个小实验。在这九个实验中，n固定为100，分别将K和p设置为三个不同的值。具体而言，k分别设置为2、8或40，p =0.1、0.5或0.9。图1(a)-(d)显示了这九个实验的结果。从这个图中不难得出以下结论：1）总体而言，在建模的早期阶段，网络熵呈下降趋势。然而，它在后期呈上升趋势。总体而言，变化呈U形。2）在相同的n和K条件下，较大的p使网络熵的变化点从下降转为上升的时间更早。3）在参数适当的情况下，熵在网络演化到一定程度时最终会接近初始水平。4）当迭代次数和p值设置为足够大时，熵在算法完成大约一半的迭代时呈下降趋势转为上升趋势。5）对于特定的n、p、K，在演化的后期阶段，网络熵回到较大的值，表明网络再次变得更加规则（即，每个节点的度变得更加均匀）。我们解释这一现象为：通过重新洗牌（边重新连接），网络从初始规则演化到新的规则。图1(c)显示了红色曲线（代表K = 40，n = 100，p =0.1的实验结果）呈直线。因此，我们在图1(d)中分别给出了该实验结果。从图1(d)可以观察到，该实验的网络熵的变化是明显的。实验II：它也包括9个小实验。在这九个实验中，n固定为1000，K分别设置为4、20或100。与实验I相比，这个实验中n的值变大了，相应地，K也变大了。p的设置与实验I相同。图1(e)-(i)显示了实验II的结果。这些结果再次证实了实验I的结论。也就是说，总体而言，网络熵的趋势与n、K和p无关。这些图符合U形定律（即，从下降到上升，最后稳定）。为了更清楚地显示K = 100，n = 1000，p =0.1的实验结果，给出了图1(i)。实验III：它包括三个小实验。在这些实验中，n固定为较大的值10000，K固定为较小的值4。分别设置p =0.1、0.5或0.9。在这3个小实验中，发现当n足够大时，网络熵的总体趋势与前两个实验相同。0278     梁勋硕等. AASRI Procedia 5 (2013) 274-2800   (a)                                                  (b)0                                    (c)                                                           (d)0                                                     (e)                                                               (f)0279  梁勋硕等. AASRI Procedia 5 (2013) 274-2800   (h)                                                  (i)0图1. 实验中的网络熵趋势0从上述结果得出的结论如下。1）在相同条件下，p值影响熵的平坦程度。具体而言，p值越大，网络熵的图形越陡峭，反之，越平坦。2）在相同条件下，K值影响到下降过程中的时间。具体而言，K值越大，时间越向前，反之，越向后。前面提到，WS网络是通过预先给定的规则网络的“重新连接边”来构建的。根据这一点，可以推测上述结论的原因如下。1）在相同条件下，较大的p意味着重新连接选定边的概率更大。重新连接的边的数量对网络熵具有更大的潜在影响。必然地，这使得网络熵的变化趋势更加明显。2）在相同条件下，对于一个节点，较大的K意味着与其相连的其他节点更多。此外，网络中的边也更多。总体而言，将发生更多的重新连接。因此，更有可能引起网络熵的变化。这必然会使网络熵的变化趋势从下降到上升的时间不可避免地推迟。03. 结论0本文分析了小世界网络建模算法。基于网络熵，研究了WS网络建立过程中网络熵的趋势。对于WS模型，p和K对其网络熵有一定影响。总体而言，WS模型的网络熵趋势呈现U形。进一步的研究包括：无标度网络的网络熵趋势如何？从网络熵的角度，我们将考虑设计一种新的小世界网络建模算法。0参考文献0[1] D.J. Watts , S.H. Strogatz. 小世界网络的集体动力学. 自然, 393, 1998: 440-442.   [2] A. L. Barabasi,R.Albert and H. Jeong. 无标度随机网络的平均场理论, 物理学报 A 272, 1999: 173-187.0280     梁勋硕等. AASRI Procedia 5 (2013) 274-2800[3] 张展钊. 复杂网络演化模型. 大连理工大学博士学位论文, 2006.  [4] 苗德胜. 系统科学大学演讲.人民大学出版社, 北京, 2007.  [5] 何天才. 复杂网络模型. 经济市场. 2007, (2): 81-85.  [6] 王晓峰, 李欣, 陈荣.复杂网络理论与应用, 清华大学出版社, 北京, 2006.  [7] M. E. J. Newman, D. J. Watts.小世界网络模型的重整化群分析, 物理学报 263, 1999: 341-346.  [8] A. Barrat, M. Weigt.关于小世界网络的特性, 欧洲物理杂志 B 13, 2000:547.  [9] M. E. J. Newman. 复杂网络的结构和功能. SIAM综述, 2003, 45:167-256.