Random Information Spread in Networks
From MaRDI portal
Publication:6220171
arXiv1008.2081MaRDI QIDQ6220171FDOQ6220171
Raymond Lapus, Frank Simon, Peter Tittmann
Publication date: 12 August 2010
Abstract: Let G=(V,E) be an undirected loopless graph with possible parallel edges and s and t be two vertices of G. Assume that vertex s is labelled at the initial time step and that every labelled vertex copies its labelling to neighbouring vertices along edges with one labelled endpoint independently with probability p in one time step. In this paper, we establish the equivalence between the expected s-t first arrival time of the above spread process and the notion of the stochastic shortest s-t path. Moreover, we give a short discussion of analytical results on special graphs including the complete graph and s-t series-parallel graphs. Finally, we propose some lower bounds for the expected s-t first arrival time.
This page was built for publication: Random Information Spread in Networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6220171)
