Vi tar upp frågan om att förstå effekten av det underliggande nätverket topologi på spridningen av ett virus och spridningen av information när användare är mobila utför oberoende slumpmässiga promenader på en graf. I detta syfte föreslår vi en enkel modell av infektion som gör det möjligt att studera tillfälligheten av två slumpmässiga vandrare på en godtycklig graf. Genom att studera slumpen tid av en mottaglig och en infekterad individ både rör sig i grafen vi får uppskattningar av infektionsannolikheten. Det viktigaste resultatet av detta dokument är att fastställa hur nätverkets topologi påverkar infektionssannolikheten. Mer exakt visar vi att för homogena grafer, inklusive regelbundna grafer och den klassiska Erdős-Rényi-modellen, är tillfällighetstiden omvänt proportionell mot antalet noder i grafen. Vi studerar sedan modellen på power-law grafer, som uppvisar heterogena konnektivitetsmönster, och visar förekomsten av en fasövergång för slumpen tid beroende på parametern i makt-lagen för examensfördelningen. Vi gör slutligen en preliminär analys för fallet med k slumpmässiga vandrare och ger övre gränser på konvergenstiden för både den fullständiga grafen och regelbundna grafer.
Med hjälp av sina resultat härledde Draief och Ganesh REF den övre gränsen för den förväntade tiden att alla partiklar är infekterade för fullständiga grafer och regelbundna grafer.
A random walk model for infection on graphs: spread of epidemics & rumours with mobile agents