基于Ad hoc特性的加速演化网络的修复能力

杭州电子科技大学学报(自然科学版)

()JournalofHanzhouDianziUniversitNaturalSciencesgy

Vol．３９No．５　Se２０１９　p．

:/DOI１０．１３９５４．cnki．hdu．２０１９．０５．０１８j

基于Adhoc特性的加速演化网络的修复能力

()杭州电子科技大学理学院,浙江杭州３１００１８

摘要:提出基于具有A建立择优连接、重连接和随机dhoc特性的加速演化网络模型的修复算法,连接这３种新边连接规则,着重研究不同加速网络演化参数以及新边连接规则等对修复策略有效拓扑演化机制中,节点的加入比例越大或删除比例越小时,网络具有更好的修复能力.此外,数值模拟显示:加速演化参数越小时,网络修复能力越强,且此时的修复策略更加适用于随机连接增长网络.

关键词:复杂网络;加速演化;网络修复;抗毁性中图分类号:O１５７．５　　　　文献标志码:A　　　

()文章编号:１００１Ｇ９１４６２０１９０５Ｇ００９８Ｇ０５

性的影响,进而寻求最合适的演化参数,有效调节网络的修复能力与抗毁性.通过仿真模拟发现:

陶梦瑶,覃　森,孙伟刚

０　引　言

]]]]１２３４

、、、入到社会生活的各个方面,如:飞机航线的演变[气温变化[脑网络的研究[病毒的传播[等.事

自从小世界网络模型(和无标度网络模型(被提出以来,复杂网络的研究已经深WS模型)BA模型)

实上,现实中的复杂网络节点与边随着时间的推移均以动态形式呈现,即存在新节点的加入以及旧节点

[]

的离开.近年来,新提出的Adhoc网络模型能较好地描述这一特性.早在２００４年,N．Sarshar等５研]６究了以固定概率随机删除节点对整个网络拓扑的影响;随后,等[对加速连接的AQinS．dhoc网络的７]度分布幂律指数与演化参数之间的关系进行探究;之后,邬琦萍[对Adhoc网络的静态拓扑特征进行]８

,了分析.随着演化规则研究的不断发展,学者们开始关注网络的动力学、抗毁性、鲁棒性等问题[但对]９

年,池丽平[对随机网络在修复策略下的稳定性展开研究,引发学者们对复杂网络修复的研究兴趣.随[０]

——冗余边,后,给出网络修复的一种新的策略—基于此修复策略提出在生成树W．Quattrociocchi等１[１]

拓扑下的网络的修复特性;同时,允许节点在某些条件下自动恢复到活跃状态,得A．Madandzic等１j

它们逆向问题的研究,特别是对网络受到蓄意或随机破坏后自身修复能力的研究仍有待加强.２００６

到动态网络在高、低活动之间不断切换的有趣现象.正如前面所述,当前关于网络演化机理对网络自愈的影响有待深入研究,并且网络链路与节点毁坏后网络修复的基本需求也是一个值得关注的研究内容.本文基于具有A探索网络拓扑演化参数的变化对网络抗毁性规律的影dhoc特性的加速演化网络模型,响,揭示网络拓扑支配网络抗毁性的机理.

１　网络建模与修复算法

１３]

.为了描数据.美国人口逐年变化的趋势与指数函数完美的拟合诠释了此类系统也是加速增长的[

１２]

,现实社会中,学者们发现许多系统具有加速增长的演化趋势[最典型的例子是美国人口的增长

述这类随着时间的推移,网络内部虽然有节点的移除但仍呈现加速增长趋势的网络,本文采用具有

收稿日期:２０１８Ｇ０９Ｇ０７

)基金项目:国家自然科学基金资助项目(６１６７３１４４

,:作者简介:陶梦瑶(女,研究方向:复杂网络.E覃森,副教授,１９９４－)Ｇmailtaomenao０４２８＠１６３．com.通信作者:gy

:.研究方向:复杂网络理论与应用.EＧmailinsen０４２５＠hdu．edu．cnq

第５期陶梦瑶,等:基于Adhoc特性的加速演化网络的修复能力９９

特性的加速演化网络模型,即以一定的节点加入概率cAdhoc１和节点删除概率c２来形象地描述网络

演化过程.如需生成一类复杂网络,则必须限制节点加入的速度大于节点删除的速度,所以需取cc１≫２且在单位时间内新节点以非线性的方式与旧节点进行连接.在所取模型的演化过程中,每个时间步内

θ)一个新的节点携带m(条边以概率c与此同时,网络中的旧节点以概率ct＝m０t１加入到网络中,２被随

.其中,机移出网络(包括其连接的边也同时移除)θ表示加速增长参数且０≤θ≤１,m０表示初始时刻网络中的总节点数.同时,假设每个节点都通过树状拓扑进行通信,这样的构造方式有利于现实生活中操作者有效衡量并且设计线路的建立方案.

１４]

,——利姆算法建立生成树网络[对生成树网络进行探究,同时在生成树中隐藏具有一定价值的链路—

为了进一步研究加速演化中的微观机制对网络修复的影响,本文从A利用普dhoc网络拓扑出发,

冗余链,这种链路可在网络破坏后对网络的连通性进行修复.进一步假设受到破坏后节点间可以通过冗余链与邻近节点进行通信,这种连接协议与实际基础网络更加契合.

()网络冗余度r＝５的一个修复过程如图１所示.图１是一个生成树:a５号节点称为source节点,

９

用来表示网络的根部节点,即可以连接到生成树中所有节点的点,叉号５条虚线表示网络中的冗余链,)代表５到９号节点之间的连边被删除,说明网络遭受蓄意或者随机的破坏.图１(反应了破坏后网络b被分成若干个小的局域网络.其中１到８号节点保持原有的状态表示未被破坏的部分,其余节点表示()被破坏的部分.图１是通过连接协议启用３到１c５这条冗余链修复网络的连通性.这样通过修复系统将重新建立一个新的生成树结构.

图１　复杂网络的修复过程

()生成一个具有加速演化特性的网络并利用普利姆算法得到演化网络的生成树;１

()在得到的生成树中随机选择边进行删除,作为网络遭受攻击后的故障边,得到破坏后的网络的２

基于网络修复的算法步骤如下:

分布情况;

()从最大连通分支中找到度最大的节点作为根部节点并在多个分支中随机添加一定个数的冗３余链;

()从被破坏网络中的某一个节点出发,判断是否可以通过冗余链路或没有被破坏的链路与根部节４点连通;

()如果与根部节点连通,则认为该点以及通向根部节点的边都被修复;５()重复步骤４、步骤５,直至被破坏网络中的节点依次判断结束;６

２　网络修复及实验

()网络的修复能力就是网络修复后与根部节点连通的最大分支所占的比例(７TheProortionOfp

,.简记为P)Clusters

)、构对新加入的节点有不同的连接机制,因此,本文分别对择优连接(重连接Preferentialattachment

通过仿真模拟不同演化参数变化时网络遭受巨大破坏后体现的修复能力.由于演化网络的拓扑结

１００

杭州电子科技大学学报(自然科学版)

２０１９年

２．１　网络演化参数对修复能力的影响

())以及随机连接(模式下的增长网络进行探究.RewiredattachmentRandomconnection

首先探究网络演化过程中节点加入比例c１和节点删除比例c２对网络修复能力的影响.在数值模

拟过程中,取２从初始节点m０＝３出发,通过网络的加速演化增长到０次运行的平均值作为模拟结果,().即通过t步之后节点携带的新边数为m(０t＝m０)

()择优连接模式下,可知:当固定cca１和c２对加速演化网络修复能力的影响如图２所示.由图２２时,随着故障边k的增加,并且随着c在择优连接模式P逐渐下降,P呈现下降的趋势.所以,１的减小,

)下,节点加入演化网络的概率降低时,修复能力变差.相应地,由图２(可知:当固定c随着cb１时,２的减小,在择优连接模式下,演化网络中删除节点的概率降低时,修复能力逐渐P呈现上升的趋势.所以,增强.另外在分析过程中发现c上面所描述的结果不明显.可见:１或者c２的数值间隔比较小的时候,

在择优连接模式下的演化网络中,修复策略能有效抵制c１和c２的变化.).为了减少其他参数对模拟结果的影响,节点为５０即网络的大小N＝５０取r＝０．００的网络(００１,θ＝

图２　择优连接模式下,节点加入比例和节点删除比例对网络修复的影响

在其他演化参数与上述网络模型相同的情况下,分别探究c１和c２对重连接模式下演化网络修复能力的影响,结果如图３所示.此时,重连概率为０．０５.

图３　重连接模式下,节点加入比例和节点删除比例对网络修复的影响

从图３可以得到与择优连接机制下演化网络相类似的结果,c１越大并且c２越小时网络的修复能力越强.这意味着,为了增加一个在重连接模式下动态网络的修复能力,可以适当增加节点加入网络的比例并且相应降低节点删除的比例.

()参数对网络的影响与之前完全相同,但有趣的是:图４中,固定c当k值在很小的时候,aP值已经达２,但是当c随着k值的增加,可见c０时网络的修复能力也是很差的;０时,P的值下降趋势很不明显,２≠２＝)到０．即修复能力很差;在图４(中,固定c当c有类似的结果,即２左右,b)０时,P的值与图４(a１,２≠

在与前述模型相同的情况下,对随机连接模式下的演化网络进行探究,结果如图４所示.显然演化

第５期陶梦瑶,等:基于Adhoc特性的加速演化网络的修复能力１０１

此时网络的修复能力很强.所以对于随机连接模式下的演化网络,只有让节点的删除概率为０时才能达到最好的修复效果,除此之外的删除概率都会对修复能力产生负面的影响.

图４　随机连接模式下,节点加入比例和节点删除比例对网络修复的影响

２．２　加速演化参数对修复能力的影响

述的模型类似,分别对３种连接模式下的演化网络进行探究,结果如图５所示.

为了更加深入地探究演化网络与修复能力之间的关系,本文从加速演化参数θ入手进行探究,与上

图５　３种连接模式下,加速演化参数对网络修复的影响

)小,这种状态在图５(中最明显,可见:当加速演化参数比较小时,网络的修复性能更P值逐渐增大,a好,尤其在择优连接模式中.

结合图５的３个图形可以看出:随着k的增大,但当冗余比例r固定时,随着θ的减P值逐渐下降,

３　结束语

在择优连接、重连接、随机连接模式下,节点加入比例和节点删除比例对网络修复能力的影响呈现相同的趋势;加速演化参数越小时,尤其在随机连接模式下更为明３种连接模式下所呈现的修复能力越强,显.为研究网络自愈与动力学行为、网络控制等之间的内在规律提供一定的理论依据.后期研究将在此基础上进行扩展,对修复策略进行优化.当加权网络遭受攻击时,可以选择最优的链路进行修复,在保证网络正常运行的基础上,降低实际所需成本,达到优化的目的.

本文主要研究A并且建立一种网络的修复策略.通过仿真模拟发现:dhoc网络的动态变化过程,

１０２

杭州电子科技大学学报(自然科学版)

２０１９年

参考文献

[]Z,]１HANGJCAOXB,DUWB,etal．Evolutionofchineseairortnetwork[J．PhsicaA:StatisticalMechanicspy[]周磊,]():龚志强,支蓉,等．基于复杂网络研究中国温度变化的区域特征[物理学报,２J．２００９,５８１０７３５１Ｇ７３５８．

():２０１２,１２３６１０６７Ｇ１０８７．

,():anditsAlications２０１０,３８９１８３９２２Ｇ３９３１．pp

[]S,V[],３TAMCJANSTRAATENECW．TheoranizationofphsioloicalbrainnetworksJ．ClinicalNeurohsiologygpygy[]YANGJ,４YAOC,MAW,etal．Astudfthesreadinchemeforviralmarketinasedonacomlexnetworkyopgsgbp[]S[]５ARSHARN,ROYCHOWDHURYV．ScaleＧfreeandstablestructuresincomlexadhocnetworksJ．Phsicalpy[]Q]６INS,DAIG,WANGL,etal．ScaleＧfreeproertfcomlexadhocnetworkswithacceleratedgrowth[J．pyop[]邬琦萍．]():计算机光盘软件与应用,７Adhoc网络的加速演化研究[J．２０１２５３０．

１Ｇ６．

,PhsicaA:StatisticalMechanicsanditsAlications２００７,３７６:６７９Ｇ６８６．ypp():ReviewE,２００４,６９２１Ｇ８．

[],():modelJ．PhsicaA:StatisticalMechanicsanditsAlications２０１０,３８９４８５９Ｇ８７０．ypp

[]Z[]:８ENGA,LIUW．EnhancinetworkrobustnessaainstmaliciousattacksJ．PhsicalReviewE,２０１２,８５(６)gngy[]池丽平．遭袭复杂网络的修复策略与关联特征研究[武汉:华中师范大学,９D]．２００６．

,():PloSOne２０１４,９２１Ｇ１２．

[]QUA:R]１０TTROCIOCCHIW,CALDARELLIG,SCALAA．SelfＧhealinetworksedundancndstructure[J．gnya[]MA]１１JDANDZICA,PODOBNIKB,BULDYREVSV,etal．Sontaneousrecoverndnamicalnetworks[J．pyiy[]李季,]():汪秉宏,蒋品群,等．节点数加速增长的复杂网络生长模型[物理学报,１２J．２００６,５５８２６３Ｇ２６９．

,():NaturePhsics２０１４,１０１３４Ｇ３８．y

[]B,:[,１３ROCKWELLPJDAVISRA．TimeSeriesTheorndMethodsM]．NewYork:SrinerＧVerla１９９１:６．yapgg

TwentＧEihthAnnualACMSmosiumonTheorfComutin．ACM,１９９６:２９６Ｇ３０３．ygypyopg

[]W//１４ILSONDB．Generatinandomsanninreesmorequicklhanthecovertime[C]Proceedinsofthegrpgtytg

thereairstrateiesonacceleratinarameters．Threemainstreamattachmentmodesofnewaddinpggpg

,,,,,edesi．e．referentialrewiredandrandomconnectionarecomaredtoexlorethebetterreairgpppp,strate．Meanwhiletheevolutionparametersareotimizedtoeffectiveldustreaircaabilitndgypyajppya

reairalorithmisproosedtoemhaticallinvestiatetheinherentmechanismoftheeffectivenessofpgppyg

:,AbstractBasedonanacceleratinvolutionaretworkmodelwithAdhocproertanewnetworkgeynpy

,,TAOMenaoQINSenSUNWeiangygg

(Schoolocience,HanzhouDianziUniversitnzhouZheian１００１８,China)fSgy,Hagjg３

TheReairCaabilitfAdHocAccelerateNetworkppyo

invulnerabilitfnetworks．Numericalsimulationsindicatethatthegreatertheproortionofaddedyop

,,nodesorthesmallerthedeletionratioofnodesthebetterthenetworkreaircaabilit．Inadditionppy,,athesmallertheacceleratinarameterthestronerthenetworkreaircaabilitndthemoregpgppysuitablereairstrateortheacceleratinetworkwithrandomattachment．pgyfgn

:;;;Keordscomlexnetworksacceleratedevolutionnetworkreairresistanceppyw