復(fù)雜網(wǎng)絡(luò)上的隨機游走

RandomwalksoncomplexnetworksZhongzhiZHANG(章忠志)SchoolofComputerScience,FudanUniversityEmail:zhangzz@Homepage:/~zhangzz/2024/9/9FutureworkIntroductiontorandomwalksongraphsApplicationsofrandomwalksTrappingongraphs:IntroductionandReviewContentsTrappingoncomplexnetworks2/432024/9/9-RandomWalksonGraphsKindsofrandomwalks:

Unbiasedrandomwalks,biasedrandomwalks,self-avoidwalks(自規(guī)避隨機游走),quantumwalks,ect3/432024/9/9RandomWalksonGraphsAtanynode,gotooneoftheneighborsofthenodewithequalprobability.-4/432024/9/9RandomWalksonGraphsAtanynode,gotooneoftheneighborsofthenodewithequalprobability.-5/432024/9/9RandomWalksonGraphsAtanynode,gotooneoftheneighborsofthenodewithequalprobability.-6/432024/9/9RandomWalksonGraphsAtanynode,gotooneoftheneighborsofthenodewithequalprobability.-7/432024/9/9RandomWalksonGraphsAtanynode,gotooneoftheneighborsofthenodewithequalprobability.-8/432024/9/9ImportantparametersofrandomwalksPrimaryIndicatorsMeanCommutetime

C(s,t):Stepsfromstot,andthengoback

C(t,s)=F(s,t)+F(t,s)MeanReturntime

T(s,s):meantimeforreturningtonodes

forthefirsttimeafterhavingleftitFirst-PassageTime

F(s,t):ExpectednumberofstepstoreachtstartingatsCovertime,survivalproblity,……NewJ.Phys.7,26(2005)9/43FPTforgeneralgraphsistheLaplacianmatrixdefinedasPseudoinverseoftheLaplacianmatrix2024/9/910/43N:

NodenumberFPTforcompletegraphStudyrandomwalksonsimplestructureisofexceptionalimportance.2024/9/911/43FPTforalineargraph2024/9/912/432024/9/9ApplicationsofrandomwalksCommunitydetection

Recommendationsystems

Electricalnetworks

SpanningtreesInformationRetrievalNaturalLanguageProcessingMachineLearningGraphpartitioning

Ineconomics:randomwalkhypothesisPageRankalgorithm13/432024/9/9ApplicationtoCommunitydetectionWorldWideWebProteininteractionnetworksMetabolicnetworksSocialnetworksBiologicalnetworksFoodWebsPropertiesofcommunitymaybequitedifferentfromtheaveragepropertyofnetwork.Morelinks“inside”than“outside”14/432024/9/9ApplicationtorecommendationsystemsIEEETrans.Knowl.DataEng.19,355(2007)Helpforsettingupefficientrecommendationsystems15/432024/9/9ConnectionswithelectricalnetworksEveryedge–aresistorof1ohm.Voltagedifferenceof1voltbetweenuandv.R(u,v)–inverseofelectricalcurrentfromutov._uv+

C(u,v)=F(s,t)+F(t,s)=2mR(u,v),

R(u,v)=C(u,v)/(2m)dzisdegreeofz,misthenumberofedges16/432024/9/9Formulasforeffectiveresistance17/432024/9/9RandomwalksandspanningtreesSpanningtrees

EPL(EurophysicsLetters),2010,90:6800218/432024/9/9Trappingproblem:Randomwalks

ongraphswithanimmobiletrapTrappingtimefornodeidenotedbyAveragetrappingtime

Researchgoal:obtainthedependenceofaveragetrappingtimeonthesystemsize19/432024/9/9Previouswork

TrappingonSierpinskigasket

PhysicalReviewE,2002,65:021105

20/432024/9/9Previouswork:TrappingonT-fractal

PhysicalReviewE,2008,77:011128

21/432024/9/9Previouswork:

Trappingonregularlattices

JournalofMathematicalPhysics,1969,10:75322/432024/9/9OurworkRandomwalksonscale-freenetworksApseudofractalscale-freewebApolloniannetworksModularscale-freenetworksKochnetworksAfractalscale-freenetworkScale-freenetworkswiththesamedegreesequences23/432024/9/9MaincontributionsMethodsforfindingMeanfirst-passagetime(MFPT)BackwardequationsGeneratingfunctionsLaplacianspectraElectricalnetworksUncovertheimpactsofstructuresonMFPTScale-freebehaviorModularstructureFractalstructureUnveiltheeffectoftraplocationonATTRelaterandomwalkstoHanoiTowersGame24/432024/9/9Walksonpseudofractalscale-freewebPhysicalReviewE,2009,79:021127.Contributions：(1)Newmethod(2)Newfindings25/432024/9/9WalksonApolloniannetworkEPL,2009,86:10006.Themostefficientstructurefordiffusion26/432024/9/9Walksonmodularscale-freenetworksPhysicalReviewE,2009,80:051120.

Generatingfunctionmethod27/432024/9/9ATTonuncorrelatedscale-freenetworksPhysicalReviewE,2009,79:061113.InuncorrelatedrandomSFwebs,28/432024/9/9PhysicalReviewE,2009,79:061113.WalksontheKochnetwork29/432024/9/9Chaos,2010,20:043112JournalofPhysicsA,2010,43:39510230/43ImpactofdegreeheterogeneityonMFPTSong,Havlin,andMakse,Nature(2005).Box-coveringmethod

Meanmass(numberofnodes)withinabox:DefinitionoffractalnetworksMetabolicnetworkProteininteractionnetworkHollywoodfilmactorsnetworkEffectoffractalityonMFPT2024/9/931/43WWW2024/9/9Walksonafractalscale-freenetworkEPL(EurophysicsLetters),2009,88:10001.32/432024/9/9Walksonscale-freenetworkswithidenticaldegreesequencesPhysicalReviewE,2009,79:031110.33/432024/9/9Walksonscale-freenetworkswithidenticaldegreesequencesPhysicalReviewE,2009,80:061111Advantages：(1)withoutcrossingedges(2)alwaysconnected.34/432024/9/9InfluenceoftrappositiononMFPTonvariousnetworks35/432024/9/9SignificantimpactoftrappositiononMFPTinnon-fractalscale-freetreesJournalofMathematicalPhysics,2009,50:033514.JournalofPhysicsA,2011,44:07510236/432024/9/9SignificantimpactoftrappositiononMFPTinscale-freeKochnetworksEuropeanPhysicalJournalB,2011,(inpress).MeanreceivingtimeMeansendingtimeGlobalmeanfirst-passagetime37/432024/9/9NoessentialimpactoftrappositiononMFPTinfractalscale-freetreesJournalofPhys