Flooding in weighted sparse random graphs

DOI10.1137/120865021MaRDI QIDQ5300477zbMATH OpenOpenAlexFDO

Authors Hamed Amini, Moez Draief, Marc Lelarge

Publication date 27 June 2013

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1011.5994

zbMATH Keywords

branching processesbroadcastconfiguration modeldistances in weighted graphsflooding

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Stochastic network models in operations research (90B15)

Abstract: In this paper, we study the impact of edge weights on distances in diluted random graphs. We interpret these weights as delays, and take them as i.i.d exponential random variables. We analyze the weighted flooding time defined as the minimum time needed to reach all nodes from one uniformly chosen node, and the weighted diameter corresponding to the largest distance between any pair of vertices. Under some regularity conditions on the degree sequence of the random graph, we show that these quantities grow as the logarithm of $n$, when the size of the graph $n$ tends to infinity. We also derive the exact value for the prefactors. These allow us to analyze an asynchronous randomized broadcast algorithm for random regular graphs. Our results show that the asynchronous version of the algorithm performs better than its synchronized version: in the large size limit of the graph, it will reach the whole network faster even if the local dynamics are similar on average.

Recommendations

• Flooding in weighted random graphs
• Flooding and diameter in general weighted random graphs
• The flooding time in random graphs
• First passage percolation on sparse random graphs with boundary weights
• The diameter of weighted random graphs

Cited in

(12)

• The flooding time in random graphs
• Floodings of metric graphs
• Viral processes by random walks on random regular graphs
• The diameter of weighted random graphs
• Information Spreading in a Large Population of Active Transmitters and Passive Receivers
• Flooding edge weighted graphs
• Flooding edge or node weighted graphs
• Flooding and diameter in general weighted random graphs
• Flooding in weighted random graphs
• First passage percolation on sparse random graphs with boundary weights
• On the Push&Pull Protocol for Rumor Spreading
• Probability-graphons: limits of large dense weighted graphs

This page was built for publication: Flooding in weighted sparse random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5300477)