基于多重图形剖分算法的免疫策略.pdf

《基于多重图形剖分算法的免疫策略.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、68传感器与微系统(TransducerandMicrosystemTechnologies)2010年第29卷第1O期基于多重图形剖分算法的免疫策略胡永生，杨玲玲(滨州学院计算机科学技术系，山东滨州256603)摘要：如何免疫网络中较少数量的节点是当前的热点，目标免疫被认为是当前最好的免疫策略，尤其对于无标度网络。考虑到目标免疫可能把网络分割成较小的单元，而多重图形剖分算法可以把图形分成特定大小的单元，并且单元之间具有很少的边相连。因而，采用多重图形剖分算法来免疫ER网络和BA网络。实验结果表明：该策略是可行的。关键词：目标免疫；多重图形剖分算法；SIS病毒传

2、播模型；ER网络；无标度网络中图分类号：TP393．08文献标识码：A文章编号：1000-9787(2010)10--0068--03Ilmmunmizati0nstrateRybasedOnmultilevelgRraphpartitioningalgorithmHUYong—sheng，YANGLing—ling(DepartmentofComputerScienceandTechnology，BinzhouUniversity，Binzhou256603，China)Abstract：Thequestionofhowtoimmunizeanetworkwi

3、thaminimalnumberofimmunizationdoesisofcurrentinterest．Targetedimmunizationiswidelyregardedasthemostefectivestrategy．especiallyf0rscale·freenetworks．Consideringthestrategycanpartitionthenetworkintosmallsizeclusters，butmultilevelgraphpartitioningalgorithmcandividingtheverticesofagraphi

4、ntosetsofspecifiedsizes，SOthatfewedgescrossbetweensets．MultilevelgraphpartitioningalgorithmisadoptedtoimmunizeaERnetworkandBAnetwork．Experimentalresultsshowthatthisstrategyisfeasible．Keywords：targetedimmunization；multilevelgraphpartitioningalgorithm；SISvirusspreadingmodel；ERnetwork；s

5、cale．freenetwork0引言domregulargraph研究图形分割的逾渗特征发现，图形分割当前网络动力学研究的一个热点是怎样用最少的免疫能有效地提高复杂网络的免疫能力，提出任何把图形分成数量对人群网络和计算机网络进行免疫。为了达到这相等大小单元的过程都具有逾渗相变(percolationphase)种目的，已经提出了很多免疫方法，如，基于全局信息的目f-L=1-2／k，其中是分隔图形的边所占的比率。处于标免疫，基于局部信息的熟人免疫，局域控制免疫很多的网逾渗相变点上，对于理想的分割，S一一，其中，5是分隔单络结构已经被研究，如，随机网络、小世界网络

6、、无标度网元的大小；一，L是单元的直径。络、局域世界演化网络、复合种群网络等。图形分割问题具有相当重要和广泛的应用，包含了根据无标度网络的不均匀性，可以进行有选择的目VLSI设计、科学计算、故障诊断。图形分割问题是把图形标免疫，即首先对节点的重要性(度数大小或介数)进行排分割成特定大小的几个单元，单元之间具有最少的边相连序，然后从大到小，按照一定比例进行免疫，一旦这个节点(edge．cut)。多重剖分算法是基于nesteddissection的改进被免疫，也就意味着给顶点的所有边即可以被删除，得到的算法，其过程是把图形粗化(coarseningphase)成越来

7、越小模型是分隔成大小不等的非独立的单元。为了提高免疫的的图形，把最小的图形用一定的算法来进行分割(partitio—效果，采用多重图形剖分算法，把图形分割成大小相似的单ningphase)，反粗化图形(reversecoarseningphase)，并在过元，并且单元之间的边的数目最少。程中对分割线进行优化，其原理图如图l所示。1多重图形剖分1．1粗化阶段GeraldP教授与其合作者2007年通过研究基于ran一使用最大匹配来通过付给边、顶点以值进行粗化图形。收稿日期：2010-09-06第10期胡永生，等：基于多重图形剖分算法的免疫策略0．50@回0．450．

8、40褂0_35O．3O鑫