资源描述：
《2012 - Pedro C. Pinto - Locating the Source of Diffusion in Large-Scale Networks》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、1LocatingtheSourceofDiffusioninLarge-ScaleNetworksPedroC.Pinto,1PatrickThiran,1MartinVetterli11ÉcolePolytechniqueFédéraledeLausanne(EPFL),Lausanne,SwitzerlandHowcanwelocalizethesourceofdiffusioninacomplexnetwork?Duetothetremendoussizeofmanyrealnetworks—suchastheInt
2、ernetorthehumansocialgraph—itisusuallyinfeasibletoobservethestateofallnodesinanetwork.Weshowthatitisfundamentallypossibletoestimatethelocationofthesourcefrommeasurementscollectedbysparsely-placedobservers.Wepresentastrategythatisoptimalforarbitrarytrees,achievingma
3、ximumprobabilityofcorrectlocalization.WedescribeαefficientimplementationswithcomplexityO(N),whereα=1forarbitrarytrees,andα=3forarbitrarygraphs.Inthecontextofseveralcasestudies,wedeterminehowlocalizationaccuracyisaffectedbyvarioussystemparameters,includingthestructur
4、eofthenetwork,thedensityofobservers,andthenumberofobservedcascades.Localizingthesourceofacontaminantoravirusisanex-informationsourcevtv3,o23observero2tremelydesirablebutchallengingtask.Innature,manyanimalsv2areintrinsicallycapableofperformingsourcelocalization.tv2,
5、o1Throughchemotaxis,forexample,certainbacteriacananalyzeo1s∗v5concentrationgradientsaroundtheminordertoquicklymovetv1,o1v4towardsthesourceofanutrient,orquicklyavoidthesourcev1ofapoison[1,2].AnimalssuchasthePacificsalmonandthetv4,o3tv5,o3greenseaturtlesarecapableofus
6、ingolfactiontonavigateino3odorplumes,forforagingorreproductiveactivities[3,4].Incertainsystems,however,thetaskoflocalizingthesourcehastobeperformedinanetwork,ratherthaninthecontinuousspace.Thisisthecase,forexample,whenaninfectiousdiseasespreadsthroughhumanpopulatio
7、nsacrossalargeregion,asFigure1.SourceestimationonanarbitrarygraphG.Attheunknowntimet=t∗,theinformationsources∗initiatesthediffusion.TheblueobservedwiththeworldwideH1N1viruspandemicin2009.edgesdenotethoseoverwhichinformationhasalreadypropagated.InthisHerethesystemis
8、moreconvenientlymodelledasanetworkexample,therearethreeobservers,whichmeasurefromwhichneighboursofinterconnectedpeople,andsourcelocalizationreduc
