TY - JOUR
T1 - Rumor source detection for rumor spreading on random increasing trees
AU - Fuchs, Michael
AU - Yu, Pei Duo
PY - 2015/1/1
Y1 - 2015/1/1
N2 - In a recent paper, Shah and Zaman 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.
AB - In a recent paper, Shah and Zaman 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.
KW - Detection probability
KW - Random increasing trees
KW - Rumor center
KW - Rumor spreading
UR - http://www.scopus.com/inward/record.url?scp=84920532076&partnerID=8YFLogxK
U2 - 10.1214/ECP.v20-3743
DO - 10.1214/ECP.v20-3743
M3 - Article
AN - SCOPUS:84920532076
VL - 20
SP - 1
EP - 12
JO - Electronic Communications in Probability
JF - Electronic Communications in Probability
SN - 1083-589X
ER -