Rumor Spreading and Invasion Percolation
DOI:
https://doi.org/10.51408/1963-0042Keywords:
Gossip problem, Information dissemination, Invasion percolationAbstract
We study the models of rumor spreading and invasion bond percolation aimed at the revelation of possible connections between them. Rumor spreading model describes the dissemination of a rumor due to the periodical repetition of sequential phone calls, whereas the invasion bond percolation refers to the spread of liquid in the porous environment. During a round of the rumor spreading, each node performs a call only once, meanwhile transmitting all the information that it knows at the moment of the call to its neighbors. The rumor reaches the receiver node during one round if there is a chain of successive calls between the source of the rumor and that node. The sequence of calls is taken uniformly at random from the set of all possible sequences (permutations of nodes). We compare the propagation of the rumor spreading with the invasion bond percolation in order to put forth necessary improvements of the percolation rules to map one model onto another, and vice versa
References
B.Baker and R. Shostak, Gossips and telephones", Discrete Math., vol. 2, pp. 191-193, 1972
R.T.Bumby, Aproblem with telephones", SIAM J. Alg. Disc. Meth. vol.2, pp. 13-18, 1981.
A.Hajnal,E.C. Milner and E.Szemeredi, Acure for the telephone disease", Canad. Math. Bull., vol.15, pp. 447-450, 1976.
T.Tijdeman,On a telephone problem", Nieuw Arch. Wisk., vol.3, pp. 188-191, 1971
A.Seress, Quick gossiping by conference calls", SIAM J. Disc. Math., vol.1,pp. 109-120, 1988
D.B. West, Gossiping without duplicate transmissions",SIAM J. Alg. Disc. Meth., vol.3, pp. 418-41, 1982.
D.B.West, Aclass of solutions to the gossip problem, part I", Disc. Math., vol.39, no. 3, pp. 307-326, 1982; part II", Disc. Math., vol. 40, no. 1, pp. 87-1 13, 1982; part III", Disc. Math., vol. 40, no. 2-3, pp. 285-310, 1982.
G.Fertin and A. Respaud, A survey on KnÄodel graphs", Discrete Applied Mathematics vol. 137, no.2, pp. 173-195, 2003.
R.Labahn, Kernels of minimum size gossip schemes", Discr. Math., vol. 143, pp. 99-139, 1995.
R.Labahn, Some minimum gossip graphs", Networks, vol. 23, pp. 333-341, 1993.
G.Fertin and R. Labahn, Compounding of gossip graphs", Networks, vol.36, pp. 126-137, 2000.
Z. Ho and M.Shigeno, N ew bounds on the minimum number of calls in failure-tolerant Gossiping",Networks, vol. 53, pp. 35-38, 2009
K. A.Berman and M. H awrylycz, Telephone problems with failures", SIAM J.Alg. Disc. Meth., vol.7, pp. 13-17, 1986.
R.W.H addad, S.Roy and A. A.Schaffer, On gossiping with faulty telephone lines", SIAM J. Alg. Disc. Meth., vol.8, pp. 439-445, 1987.
T.H asunuma and H.N agamochi, Improved bounds for minimum fault-tolerant gossip graphs", LNCS, vol.6986, pp. 203-214, 2011.
L. Gargano,Tighter time bounds on fault-tolerant broadcasting and gossiping", Networks, vol.22 pp.469-486, 1992
K. Menger,Zur allgemeinen Kurventheorie", Fund. Math., vol. 10, pp. 96-115, 1927.
D J. D aley and D.G. Kendall,Epidemics and rumors", Nature, vol. 204, 1118, 1964, DOI: 10.1038/2041118a0
R.Karp, C.Schindelhauer, S. Shenker and B. Vocking,Randomized rumor spreading", In Foundations of Computer Science, Proceedings. 41st Annual Symposium on IEEE, pp. 565-574, 2000
D Wilkinson and J.F.Willemsen, Invasion percolation: a new form of percolation theory", Journal of Physics A: Mathematical and General, vol. 16, no. 14, pp. 33-65, 1983.
R.Chandler, J.Koplik, K. Lerman, J. Willemsen, Capillary displacement and percolation in porous media", Journal of Fluid Mechanics vol. 119, 249-267, 1982.
A.-L.Barabasi, D ensity functional and density matrix method scaling linearly with the N umber of atoms", Phys. Rev. Lett., 76, 3750, 1996.
R.C.Prim,Shortest connection networks and some generalizations", Bell System Technical Journal, vol. 36, no. 6, pp. 189-1401, 1957.
V.H.Hovnanyan, Su. S.Poghosyan and V.S.Poghosyan, New methods of construction of fault-tolerant Gossip graphs", IEEEP roceedings of the International Conference on Computer Science and Information Technologies (CSIT'2013), 10.1109/CS ITechnol.2013.6710341 DOI: 10.1109/CSITechnol.2013.6710341
V.H. Hovnanyan, Su.S.Poghosyan and V.S.Poghosyan, Method of Local Interchange to Investigate Gossip Problems",Transactions of IIAP of the NAS of RA, Mathematical Problems of Computer Science, vol. 40, pp. 5-12, 2013
V.H.Hovnanyan, Su.S. Poghosyan and V.S.Poghosyan, Method of Local Interchange for the Investigation of Gossip Problems: part 2", Transactions of IIAP of the NAS of RA, Mathematical P roblems of Computer Science, vol. 41, pp. 15-22, 2014.
V.H.Hovnanyan, Su.S.Poghosyan and V.S.Poghosyan, Graph Plotter: a Software Tool for the Investigation of Fault-tolerant Gossip Graphs", Proceedings of International Conference CSIT-2013, pp. 20-22
V.H.Hovnanyan, Su. Poghosyan and V.Poghosyan, Fault-tolerant Gossip Graphs Based on Wheel Graphs", Transactions of IIAP of the NAS of RA, Mathematical Problems of Computer Science, vol. 42, pp. 43-53, 2014.
V.H.Hovnanyan, Su.Poghosyan and V.Poghosyan, Open problems in gossip/broadcast schemes and the possible application of the method of local interchange",Proceedings of International Conference CSIT 2015, pp. 73-78
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
