Rumor source detection for rumor spreading on random increasing trees. (English) Zbl 1306.05223

Fuchs, Michael; Yu, Pei-Duo

Electron. Commun. Probab. 20, Paper No. 2, 12 p. (2015).

Summary: In recent papers, D. Shah and T. Zaman [“Detecting sources of computer viruses in networks: theory and experiment”, in: Proceedings of the ACM SIGMETRICS international conference on measurement and modeling of computer systems, SIGMETRICS 10. New York, NY: Association for Computing Machinery (ACM). 203–2014 (2010; doi:10.1145/1811099.1811063); “Rumors in a network: who’s the culprit?”, IEEE Trans. Inform. Theory 57, No. 8, 5163–5181 (2011; doi:10.1109/TIT.2011.2158885)] proposed the rumor center as an effective rumor source estimator for rumor spreading on random graphs. They proved for a very general random tree model that the detection probability remains positive as the number of nodes to which the rumor has spread tends to infinity. Moreover, they derived explicit asymptotic formulas for the detection probability of random \(d\)-regular trees and random geometric trees. In this paper, we derive asymptotic formulas for the detection probability of grown simple families of random increasing trees. These families of random trees contain important random tree models as special cases, e.g., binary search trees, recursive trees and plane-oriented recursive trees. Our results show that the detection probability varies from 0 to 1 across these families. Moreover, a brief discussion of the rumor center for unordered trees is given as well.

MSC:

05C80	Random graphs (graph-theoretic aspects)
05C05	Trees
60C05	Combinatorial probability

Keywords:

rumor spreading; rumor center; detection probability; random increasing trees