Chaos,SolitonsandFractals170(2023)113400Optimalprunedtree-cutmapping-basedfastshieldingforlarge-scalenetworksWeiWei,PengpengWang,QinghuiZhang∗KeyLaboratoryofGrainInformationProcessingandControl(HenanUniversityofTechnology),MinistryofEducation,Zhengzhou450001,ChinaHenanProvincialKeyLaboratoryofGrainPhotoelectricDetectionandControl,HenanUniversityofTechnology,Zhengzhou450001,ChinaARTICLEINFOABSTRACTKeywords:Tree-cutmappingNetworkrobustnessLeft-mostpathLarge-scalenetworkConnectivityRandomfailureisacommonthreattoanetwork,wherethefailureofafewedgescandisconnectalarge-scalesparsenetwork.Toenhancetherobustnessofnetwork,theshieldingofimportantedgesisapracticalstrategy,wherethecutisausefulentitytohelplocateimportantedgesinexistingshieldingmethods.However,asthereisnoavailablewaytoquicklylocatetargetcuts,theexistingshieldingalgorithmisnotefficientenoughandcanonlybeappliedtosmall-scalebackbonenetworks.Fortunately,byusingtheoptimalprunedtree-cutmapping,wefoundanefficientandhigh-precisioncutedgeenumerationmethod,whichcanhelpquicklylocatetargetcutsandtheiredgesinalarge-scalenetwork,leadingtoacost-effectiveshieldingplan.Theoreticalanalysisindicatesthatmorethan99%ofcandidatecutscanbefoundwithalimitednumberofpreprocessingpasses,andexperimentalresultsintypicalnetworksshowthatinsmall-scalenetworks,withlittleextracost(<6%),theserialimplementationofthealgorithminanoff-shelfcomputingnodecanbe6ordersofmagnitudefasterthantheoptimalmethod,whileinlarge-scalesparsenetworkswithamillionnodes,itcanalsohelpdefendatleast99.9%ofrandomfailureswithonlytensofsecondsofpreprocessingoverhead.1.IntroductionDuetonaturalandman-madedamage,thecommunicationnetworkisconstantlythreatenedbynetworkfailures,whichcanleadtoseriouslossoftop-levelservices.Networkrobustnessisameasureoftheabilitytocontinuefunctioningwhenpartofthenetworkiseithernaturallydamagedortargetedforattack[1].Itisimportanttoenhancetherobustnessofthenetworkbyemployingdefensivetechniquestowith-standexpectedlevelsoffailure.Extensiveresearchhasbeenconductedacrossmanyfieldsofengineeringandscience,butcriticalresearchgapsremain.Amongmanymeasurementsofnetworkrobustness,edgeconnec-tivityisanimportantandfundamentalmetricthatcanbeseverelydegradedbyvariousglobalnetworkfailuresandleadtodatacommuni-cationbreakdownsacrossthenetwork.Tomaintainedgeconnectivityintheeventofnetworkfailures,edgerewiringorredundantedgepre-deploymentwillbeleveragedfordefense[2].Forexample,rewiringoraddingedgescanhelpimprovethenetworkrobustnessmeasuredbythelargestconnectedcomponentorshortestpathlength[3].Whenredundantresourcesarenotfeasible,amorepracticalwayistoshieldcriticaledgesandmakethemnolongervulnerabletomostnetworkfailures.Thecoreideaistoselectandshieldcriticaledgesforthetargetedpathsandoptimizeoneormoreobjectivesundergivenconstraints[4,5].Toimprovethereliabilityofthepathbetweengivenendsinatelecommunicationnetwork,[4]tookthelayingcostandthenumberofrepairedlinksasoptimizationtargets,modeleditasamulti-objectiveshortestpathproblemandsolveditusingthelabelsettingalgorithm.ThentheapproximateParetofrontfortheobjectiveswasobtainedwithinanacceptablerunningtime.Toimprovetherobustnessofthebackboneopticalnetworkandselectedgestoupgradetohigher-levelavailability,[5]investigatedhowtoobtaintheupgradeplanatthelowestcostunderavailabilityandgeodiversityconstraints.Thearc-basedintegernonlinearprogrammingm...
