Flooding in weighted sparse random graphs

DOI10.1137/120865021zbMATH Open1282.60010arXiv1011.5994OpenAlexW2000985696MaRDI QIDQ5300477FDOQ5300477

Authors: Hamed Amini, Moez Draief, Marc Lelarge 

Publication date: 27 June 2013

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

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.

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

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

zbMATH Keywords

branching processesbroadcastconfiguration modelfloodingdistances in weighted graphs

Mathematics Subject Classification ID

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

Cited In (11)

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

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)