基于网络熵的并行和分布式计算与系统 - AASRI Procedia 2013

© 2013 Liangxun Shou，YiYing Chen，Zexin Zhang and Wenb in Li. Elsevier B. V.出版，美国应用科学研究所负责选择和/或同行评审可在www.sciencedirect.com在线获取ScienceDirectAASRI Procedia 5（2013）274 - 2802013年AASRI并行和分布式计算与系统基于网络熵Liangxun Shuo，Yiying Chen，Zexin Zhang，Wenbin Li*石家庄经济学院信息网络安全实验室，河北石家庄050031摘要在无标度网络或小世界网络的建模算法中，节点的变化反映了系统组件的新陈代谢，而边的变化则反映了系统结构的新陈代谢。由于节点和边的修改，网络结构以及网络的熵发生了变化。因此，本文采用网络熵来描述系统的代谢过程，并在此基础上对WS模型进行了分析。结果表明：WS网络的网络熵呈U型变化;第二，在相同条件下，p的值影响熵图中的减少和增加的速率。而K决定了从下降到上升的变化时机。© 2013作者。由Elsevier B. V.在CC BY-NC-ND许可下开放获取。由美国应用科学研究所负责选择和/或同行评审关键词：复杂网络;熵; WS模型1. 介绍1998年和1999年发表在《Nature》和《Science》上的两篇文章被认为是小世界网络[1]和无标度网络[2]的开创性工作。此后，* 李文斌。联系电话：电话：0311 -87207591传真：0311 -87208591电子邮件地址：mr. libert@gmail.com。2212-6716 © 2013作者出版社：Elsevier B.V. 在CC BY-NC-ND许可下开放访问。美国应用科学研究所负责的选择和/或同行评审doi：10.1016/j.aasri.2013.10.089Liangxun Shuo等/ AASRI Procedia 5（2013）274275我不同网络的结构特征和各种网络建模算法相继问世，引起了复杂网络研究的热潮。目前，对复杂网络的研究主要集中在三个方面[3]：网络模型的演化、复杂网络的稳定性、复杂网络动力学。复杂网络的生成是指网络的形成过程。该生成算法被称为复杂网络的演化模型。这是近年来研究最为活跃的领域之一。这方面的研究主要集中在：网络形成机制的规律、随机映射的生成机制与模型、小世界网络的生成机制与模型、无标度网络的生成机制与模型、演化网络的生成机制和确定性网络的生成机制等方面，虽然这方面的研究成果相当丰富，但仍存在一些问题[3]：对小世界效应新机制的研究尚需进一步深入，缺乏公认的具有真实系统三种统计性质的随机网络模型;对网络拓扑演化分析方法的理解尚需探索;考虑动力学等因素的模型较少;对现实生活中特定网络幂律的形成机制尚需深入研究。本文主要研究WS小世界网络的形成机理，以理解经典的进化算法。基于图熵分析了WS模型生成网络的特征。一方面，对于研究者来说，本文的方法和结论有助于进一步解决复杂网络建模领域的问题。另一方面，它为提出新的复杂网络模型提供了新的视角。我们认为，这是一种新的尝试。2. 网络熵与WS模型从网络的角度来看，系统的生成和演化可以概括为两个方面：第一是节点的变化;第二是连接的变化[4]。前者代表系统组分的新陈代谢，后者代表系统结构的新陈代谢，自然，我们想知道熵在系统的新陈代谢过程中是如何变化的。它是增加、减少、周期性或不规则地变化？只有对新陈代谢有充分的了解，才有可能对系统进行“控制”。这种“控制”体现在设计更逼真的网络模型上。在WS、NW [5]、BA模型（或其他模型）中，由于网络的节点或边的变化，网络的熵随结构的变化而变化。因此，利用网络熵刻画系统的代谢过程是一件很自然的事情。2.1. 网络熵设系统S中存在多个事件，记为S={E1，.，En}，概率事件Ei的发生是pi，并且piI1IElogbpi1，则Ei的信息量为（一）其中，b是2或自然常数e。从e.q.不难看出。（1）小概率事件所携带的信息量大于大概率事件所携带的信息量。熵被定义为整个系统S的平均信息量，即：276Liangxun Shuo等/ AASRI Procedia 5（2013）274nHspiIEi1npilogbpiI1（二）熵反映了系统的有序程度。熵越大，系统越无序。是不难知道，当所有的概率相等时，熵取最大值。当pi= 0（i= 1，.，n）时，熵取最小值0，即Hs> = 0。具有N个节点（即S）的复杂网络，其网络熵定义和归一化为：（三）其中，pi被定义为ndi/dii1d i表示第i个节点的度。2.2. 基于网络熵为了分析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行）。链表中记录的网络熵清晰地反映了系统形成过程中的代谢趋势。算法1. 基于网络熵输入：由N个节点组成的最近邻耦合网络，每个节点i与其相邻节点相邻，i= 1，2，.，K/2，其中K是偶数。这里，K=2k（1<=k=N/2）。输出：网络熵工艺流程：1.初始化网络熵链表L//i表示网络2中的第i个边。FOR（i=1;i=N*k;++i）3.为了选择第i条边（记为e），假设它的两个节点分别为：ei0，ei1;4.产生范围（0，1]内的随机数p5.如果（1-pp'）则//以概率p随机重新布线网络的每条边我Liangxun Shuo等/ AASRI Procedia 5（2013）2742776.随机选取e的一个节点，假设为ei0;7.//P表示所有节点8.在P中随机选择一个节点（假设是e'i1），e'i1不能事先与ei0连接;9.连接ei0和e'i1;10.删除e;11.计算当前小世界网络的网络熵;12.将上述网络熵添加到链表L中;2.3. 实验结果及分析本文在算法1的基础上对WS模型进行了一系列实验，旨在揭示主要参数对模型结构的影响。同时，基于网络熵的变化，对WS模型进行了分析。我们主要考虑n、K和p的各种组合。实验一它包括九个小实验。在9个实验中，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）中可以看出，这个实验的网络熵的变化是明显的。实验二：包括9个小实验。在九个实验中，n固定为1000，K分别设置为4、20或100。与实验I相比，本实验中的n值变大，相应地，K也变大。p的设置与实验Ⅰ相同。图1（e）-（i）显示了实验II的结果。这些结果再次证实了实验I的结论。也就是说，总的来说，网络熵的趋势与n、K和p无关。这些数字服从U形定律（即，从下降到上升，最后到稳定）。同样，为了更清楚地显示K= 100，n= 1000，p= 0.1的实验结果，给出了图1（i）。实验三：包括三个小实验。在这些实验中，n固定为大值10000，K固定为小值4。分别地，p= 0.1、0.5或0.9。在这3个小实验中，发现当n足够大时，网络熵的总体趋势与前两个实验相同278Liangxun Shuo等/ AASRI Procedia 5（2013）274(a)（b）第（1）款(c)（d）其他事项(e)（f）第（1）款Liangxun Shuo等/ AASRI Procedia 5（2013）274279(h)（一）Fig. 1.实验中的网络熵趋势从上述结果得出的结论如下。1)在相同条件下，p值影响熵的平坦度.具体来说，p越大，网络熵的图就越陡。相反，它更平坦。2）在相同条件下，K值影响下跌进入上升的时机具体来说，K更大;时间更靠前。相反，它更落后。如前所述，WS网络是通过预先给定的规则网络的“重新连接边”来构建的。据此，得出上述结论的原因可以推测如下。1)在相同条件下，p越大，表示重新连接所选边的概率越大。重连边数对网络熵有较大的潜在影响。这必然使得网络熵的变化趋势更加明显。2)在相同条件下，对于一个节点，K越大，意味着连接到它的节点越多，网络中的边也越多。总的来说，将出现更多的重新连接。因此，它更有可能导致网络熵的变化。这必然会使网络熵发生明显的变化。网络熵变较平缓，由降到升的时间必然推迟。3. 结论分析了小世界网络建模算法。以网络熵为基础，研究了WS网络建立过程中网络熵的变化趋势。对于WS模型，p和K对其网络熵有一定的影响。总体来看，WS模型的网络熵的变化趋势呈U型。进一步的研究包括：无标度网络的网络熵的变化趋势如何？本文从网络熵的角度出发，考虑设计一种新的小世界网络建模算法。引用[1] D.J. Watts，S.H.斯特罗加茨小世界网络的集体动力学Nature 393，1998：440-442。[2] A. L. Barabasi，R.Albert和H.郑无标度随机网络的平均场理论，Physica A 272，1999：173-187。280Liangxun Shuo等/ AASRI Procedia 5（2013）274[3] Z. Z.张某复杂网络演化模型大连理工大学博士学位论文，2006。(in中文版）[4] D. S. 苗系统科学大学演讲。中国人民大学出版社，北京，2007年。[5] T. C. 他外复杂网络模型经济市场。2007，（2）：81-85.（中文）[6] X.F.的缩写Wang，X.利河，巴西-地尘复杂网络理论与应用，清华大学出版社，北京，2006。(in中文版）[7] M. E. J. Newman，D. J·瓦茨。小世界网络模型的重正化群分析，物理。A 263，1999：341-346。[8] A. 巴拉特，M.重量关于小世界网络的性质，Europe.Phys. J. B13，2000：547.[9] M. E. J. 纽曼复杂网络的结构与功能SIAM review，2003，45：167-256.