Taylorletthesunshinein

ANetworkEfficiencyMeasurewithApplicationstoCriticalInfrastructureNetworksAnnaNagurneyQiangQiangIsenbergSchoolofManagementUniversityofMassachusetts–Amherst4thInternationalConferenceonComputationalManagementScience,April20-22,2007,Geneva,SwitzerlandFundingforourresearchhasbeenprovidedby:NationalScienceFoundationAT&TFoundationJohnF.
SmithMemorialFund-UniversityofMassachusettsatAmherstMetroRailNetworkIridiumSatelliteConstellationNetworkSatelliteandUnderseaCableNetworksBritishElectricityGridSomeCriticalInfrastructureNetworksNetworkVulnerabilityRecentdisastershavedemonstratedtheimportanceaswellasthevulnerabilityofnetworksystems.
Forexample:–HurricaneKatrina,August23,2005–ThebiggestblackoutinNorthAmerica,August14,2003–9/11TerroristAttacks,September11,2001EarthquakeDamageprcs.
org.
pkTsunamiletthesunshinein.
wordpress.
comStormDamagewww.
srh.
noaa.
govInfrastructureCollapsewww.
10-7.
comAnUrgentNeedforaNetworkEfficiency/PerformanceMeasureInordertobeabletoassesstheperformance/efficiencyofanetwork,itisimperativethatappropriatemeasuresbedevised.
Appropriatenetworkmeasurescanassistintheidentificationoftheimportanceofnetworkcomponents,thatis,nodesandlinks,andtheirrankings.
Suchrankingscanbeveryhelpfulinthecaseofthedeterminationofnetworkvulnerabilitiesaswellaswhentoreinforce/enhancesecurity.
RecentLiteratureonNetworkVulnerabilityLatoraandMarchiori(2001,2002,2004)Barrat,BarthélemyandVespignani(2005)Dall'Asta,Barrat,BarthélemyandVespignani(2006)ChassinandPosse(2005)Holme,Kim,YoonandHan(2002)Sheffi(2005)TaylorandD'este(2004)Jenelius,PetersenandMattson(2006)Murray-TuiteandMahmassani(2004)TransportationNetworkEquilibriumParadigmWehaverecentlyshownthat,ashypothesizedover50yearsagobyBeckmann,McGuire,andWinsten(1956),thatelectricpowergenerationanddistributionnetworkscanbereformulatedandsolvedastransportationnetworks,Wu,Nagurney,Liu,andStranlund,TransportationResearchD(2006),Nagurneyetal.
,TransportationResearchD,inpress.
Wehavedemonstratedthatfinancialnetworkswithintermediationcanbereformulatedandsolvedastransportationnetworkproblems;LiuandNagurney,ComputationalManagementScience,inpress.
TheTransportationNetworkEquilibriumReformulationofElectricPowerSupplyChainNetworksElectricPowerSupplyTransportationChainNetworkNetworkNagurneyetal,toappearinTransportationResearchETheTransportationNetworkEquilibriumReformulationoftheFinancialNetworkEquilibriumModelwithIntermediationLiuandNagurney,toappearinComputationalManagementScienceTransportationsciencehashistoricallybeenthedisciplinethathaspushedthefrontiersintermsofmethodologicaldevelopmentsforsuchproblems(whichareoftenlarge-scale)beginningwiththeworkofBeckmann,McGuire,andWinsten(1956).
VIFormulationofTransportationNetworkEquilibrium(Dafermos(1980),Smith(1979))TheNetworkEfficiencyMeasureofLatoraandMarchiori(2001)LatoraandMarchiori(2001)proposedanetworkefficiencymeasure(theL-Mmeasure)asfollows:OurResearchonNetworkEfficiencyandNetworkVulnerabilityANetworkEfficiencyMeasurewithApplicationtoCriticalInfrastructureNetworks,NagurneyandQiang(2007a),toappearinJournalofGlobalOptimization.
ATransportationNetworkEfficiencyMeasurethatCapturesFlows,Behavior,andCostswithApplicationstoNetworkComponentImportanceIdentificationandVulnerability,NagurneyandQiang(2007b),toappearinProceedingsofthePOMS18thAnnualConference,May4toMay7,2007.
AUnifiedNetworkPerformanceMeasurewithImportanceIdentificationandtheRankingofNetworkComponents(2007),OptimizationLetters,inpress.
TheNagurneyandQiangNetworkEfficiencyMeasureNagurneyandQiang(2007a)(theN-QMeasure)proposedanetworkefficiencymeasurefornetworkswithfixeddemand,whichcapturesthedemandandflowinformationunderthenetworkequilibrium.
ImportanceofaNetworkComponentTheApproachtoStudytheImportanceofNetworkComponentsTheeliminationofalinkistreatedintheN-Qmeasurebyremovingthatlinkwhiletheremovalofanodeismanagedbyremovingthelinksenteringandexitingthatnode.
InthecasethattheremovalresultsinnopathconnectinganO/Dpair,wesimplyassignthedemandforthatO/Dpairtoanabstractpathwithacostofinfinity.
Hence,ourmeasureiswell-definedeveninthecaseofdisconnectednetworks.
TheL-MMeasurevs.
theN-QMeasureExample1AssumeanetworkwithtwoO/Dpairs:w1=(1,2)andw2=(1,3)withdemandsgiven,respectively,bydw1=100anddw2=20.
ThepathforeachO/Dpairis:forw1,p1=a;forw2,p2=b.
Theequilibriumpathflowsarexp1*=100,xp2*=20.
TheequilibriumpathtravelcostisCp1=Cp2=20.
123abca(fa)=0.
01fa+19cb(fb)=0.
05fb+19ImportanceandRankingofLinksandNodesLinkImportanceValuefromtheN-QMeasureImportanceValuefromtheN-QMeasurea0.
83331b0.
16672NodeImportanceValuefromtheN-QMeasureImportanceRankingfromtheN-QMeasure11120.
8333230.
16673Example2Thenetworktopologyisthefollowing:w1=(1,19),w2=(1,20)dw1=dw2=100LinkCostFunctionsImportanceandRankingofLinksExample2LinkImportanceRankings00.
10.
20.
30.
40.
50.
60.
70.
80.
9127261224342352267211020825919182812161113141517LinkImportanceValuesExample3:theBraess(1968)NetworkAssumeanetworkwithasingleO/Dpair(1,4).
Thereare2pathsavailabletotravelers:p1=(a,c)andp2=(b,d).
Foratraveldemandof6,theequilibriumpathflowsarexp1*=xp2*=3.
TheequilibriumpathtravelcostisCp1=Cp2=83.
1234abcdca(fa)=10facb(fb)=fb+50cc(fc)=fc+50cd(fd)=10fdAddingaLinkIncreasesTravelCostforAll!
Addinganewlinkcreatesanewpathp3=(a,e,d).
Theoriginalflowdistributionpatternisnolongeranequilibriumpattern,sinceatthislevelofflow,thecostonpathp3,Cp3=70.
Thenewequilibriumflowpatternnetworkisxp1*=xp2*=xp3*=2.
TheequilibriumpathtravelcostisCp1=Cp2=Cp3=92.
1234abcdece(fe)=fe+10FourDemandRangesDemandRangeI:dw∈[0,80/31)–Onlyp1andp2areusedandtheBraessParadoxdoesnotoccurDemandRangeII:dw∈[80/31,40/11]–Onlyp1andp2areusedandtheBraessParadoxoccursDemandRangeIII:dw∈(40/11,80/9]–AllpathsareusedandtheBraessParadoxstilloccursDemandRangeIV:dw∈(80/9,∞)–Onlyp1andp2areusedandtheBraessParadoxvanishesImportanceRankingofLinksintheBraessNetwork01234abcdeLinkRankingImportanceRankinginDemandRangeIImportanceRankinginDemandRangeIIImportanceRankinginDemandRangeIIIImportanceRankinginDemandRangeIVImportanceRankingofNodesintheBraessNetwork01231234NodeRankingImportanceRankinginDemandRangeIImportanceRankinginDemandRangeIIImportanceRankinginDemandRangeIIIImportanceRankinginDemandRangeIVDiscussionLinksbandcarelessimportantinDemandRangeIthanDemandRangeII,IIIandIVbecausetheycarryzeroflowinDemandRangeIExample4:AnElectricPowerSupplyChainNetworkSupernetworkTransformationExample1fromNagurney,Liu,CojocaruandDaniele,TRE(2005)FiveDemandRangesDemandRangeI:dw∈[0,1]DemandRangeII:dw∈(1,4/3]DemandRangeIII:dw∈(4/3,7/3]DemandRangeIV:dw∈(7/3,11/3]DemandRangeV:dw∈(11/3,∞)ImportanceRankingofLinksintheElectricPowerSupplyChainNetwork01234abcdefLinkRankingImportanceRankinginDemandRangeIImportanceRankinginDemandRangeIIImportanceRankinginDemandRangeIIIImportanceRankinginDemandRangeIVImportanceRankinginDemandRangeVImportanceRankingofNodesintheElectricPowerSupplyChainNetwork01234PowerGenerator1PowerSupplier1PowerSupplier2PowerSupplier3DemandMarket1NodeRankingImportanceRankinginDemandRangeIImportanceRankinginDemandRangeIIImportanceRankinginDemandRangeIIIImportanceRankinginDemandRangeIVImportanceRankinginDemandRangeVDiscussionLinksaanddarethemostimportantlinksandpowersupplier1isrankedthesecondduetothefactthatpathp1,whichconsistsoflinksaanddandpowersupplier1carrythelargestamountofflow.
TheAdvantagesoftheNagurneyandQiangNetworkEfficiencyMeasureItcapturesflows,costs,andbehavioroftravelers,inadditiontonetworktopology;Theresultingimportancedefinitionofnetworkcomponentsisapplicableandwell-definedeveninthecaseofdisconnectednetworks;Itcanbeusedtoidentifytheimportance(andranking)ofeithernodes,orlinks,orboth;andItcanbeappliedtoassesstheefficiency/performanceofawiderangeofcriticalinfrastructurenetworks.
Itistheunifiedmeasurethatcanbeusedtoassessthenetworkefficiencywitheitherfixedorelasticdemands.
ThankYou!
Formoreinformation,seehttp://supernet.
som.
umass.
eduTheVirtualCenterforSupernetworks