Markovian evolving grafer [2] är dynamiska diagrammodeller där länkarna mellan en fast uppsättning noder ändras under tiden enligt en godtycklig Markovian regel. De är extremt allmänna och de kan mycket väl beskriva viktiga dynamiska nätverksscenarier. Vi studerar hastigheten av information som sprids i stationär fas genom att analysera slutförandet av översvämningsmekanismen. Vi bevisar en allmän teorem som etablerar en övre gräns på översvämningstid i någon stationär Markovian utvecklande graf i termer av dess node-expansion egenskaper. Vi tillämpar vårt teorem i två naturliga och relevanta fall av sådana dynamiska grafer: edge-Markovian evolving graphs [24, 7] där sannolikheten för att det finns någon kant vid tiden t beror på förekomsten (eller inte) av samma kant vid tiden t − 1; geometriska Markovian evolving graphs [4, 10, 9] där Markovian beteende genereras av n mobila radiostationer, med fast sändningsradie, som utför n oberoende slumpmässiga promenader över en fyrkantig region av planet. I båda fallen visar sig de erhållna övre gränserna vara nästan tighta, och i själva verket visar de sig vara tighta för ett stort urval av värdena för indataparametrarna.
Ett undantag är arbetet REF, där en övre gräns för översvämningstiden är härledd i termer av nodeexpansion egenskaper hos en allmän stationär Markovian evolv-1536-1276/13$31.00 c 2013 IEEE ing graf.
Information spreading in stationary Markovian evolving graphs
{'venue': '2009 IEEE International Symposium on Parallel & Distributed Processing', 'journal': '2009 IEEE International Symposium on Parallel & Distributed Processing', 'mag_field_of_study': ['Mathematics', 'Computer Science']}