ReliabilityEngineeringandSystemSafety232(2023)109082PTUM:Efficientshieldingoflarge-scalenetworkthroughprunedtree-cutmapping✩WeiWei,YutingLiu,WeidongYang∗KeyLaboratoryofGrainInformationProcessingandControl(HenanUniversityofTechnology),MinistryofEducation,Zhengzhou450001,ChinaHenanKeyLaboratoryofGrainPhotoelectricDetectionandControl,HenanUniversityofTechnology,Zhengzhou450001,ChinaARTICLEINFOABSTRACTKeywords:NetworkrobustnessPrunedtree-cutmappingShieldingLarge-scalenetworkConnectivityAsonerealisticwaytoimprovetherobustnessofnetwork,theprotectionofcriticallinkswillhelpbuildresilientlinkstructuretodefendagainstrandomlinkfailure,especiallyinsparsenetworkwherefewsimultaneousbrokenlinkscandivideitintodisconnectedparts.Thereareseveralwaystoselectthesetoflinkstoshield,whereselectinglinksbygraphcutsisapracticalone.However,duetothecomputationalcomplexityofcutenumeration,theexistingalgorithmscannothandlelarge-scalenetworksinacceptabletime.Fortunately,betweentheprunedtreesandcuts,wefoundanefficientmappingschematoenumeratesmallcuts,whichcanhelpselectthecandidatelinksquicklyinlarge-scalesparsenetwork,andthelinksetwillbefurtherrefinedtofindthesetwithminimalshieldingcost.Theexperimentalresultsshowthatcomparedwiththeexistingoptimalalgorithm,theaccelerationratioof5ordersofmagnitudecanbeobtainedeasilywithlittleexcesscost,andtheshieldingsolutioncanprotectmorethan99.9%vulnerablenodepairs.Furthermore,thetimecanbereducedtotensofsecondsbyparallelizationfortheready-to-parallelizealgorithm.1.IntroductionThefailureofcommunicationnetworkcanseverelyaffecttheiravailability,andthuscanseverelyaffecttheperformanceofservicesandapplicationsbuiltuponthenetwork.Networkrobustnesscanberegardedasitsabilitytocopewiththevarioustypesoffailuresthatcanoccurinthenetwork,suchasintendedattacksornaturaldisasters.Itisimportanttoimprovethenetworkrobustnesstopreventthesetypesofattacksanddisastersfromdisconnectingthenetwork.Significantresearchhasbeenconductedintheseareas,thestudycanhelpproduceusefultoolsinthecharacterizationandutilizationofcomplexinter-connectedsystemssuchasinfrastructure,communicationandsocialnetworks,whilethegapsinthesurveyingliteraturestillexist[1].Therearealreadyplentyofmetricsusedfornetworkrobustnessas-sessment[2],whilesomeindirectmetricscanaffectrobustnessinspe-cificscenarios,suchastheinter-networkassortativity[3].Astraight-forwardwaytoenhancerobustnessisthroughimprovingthesemetrics,wherethewidelyoptimizedmetricisR[2].Thelargestcomponentofanetwork,knownasthelargestconnectedcomponent(LCC),isausefulindicatorofthenetworkstatus.Byiterativelydeletingthehighest-degreenodes,theaverageratioofLCCsizeamongalltheiterationscanbedefinedasthemetricR.[4]developedadeeplearningpolicythataimstoimprovetheresilienceoftheInternetofThings(IoT)networktopology.ItwasimplementedbyadoptingaR-improvingreinforcementmethodthatcanbeusedtopreventcyber-attacks.[5]proposeda✩ThispaperwassupportedbytheNationalNaturalandScienceFoundationofChina(62172141,62006071,61772173,61973104,61803146),NaturalscienceprojectofZhengzhouscienceandTechnologyBureau(21ZZXTCX20),HenanExcellentYoungScientistsFund(212300410036),theKeyLaboratoryofGrainInformationProcessingandControl(HenanUniversityofTechnology),theMinistryofEducation(KFJJ2022002),BackboneTeacherTrainingProgramofHenanUniversityofTechnology(2012012),YoungBackboneTeacherTrainingProgramofHenan...
