Rumor source detection under probabilistic sampling

Consider a network where an unidentified source starts a rumor. The rumor spreads along the edges of the network to other nodes in the network. After a sufficiently long amount of time, we observe a subset of the nodes that have heard the rumor, and using this information wish to identify the source. Optimal estimators were recently proposed for regular (exponential growth) and irregular geometric (polynomial growth) trees when all nodes that heard the rumor reveal themselves. We provide the extension to the case in which nodes reveal whether they have heard the rumor with probability p, independent of each other. For geometric trees and p > 0, we achieve the same performance as the optimal estimator with p = 1. For regular trees, the estimator can achieve performance within ε of the optimal, provided that p is larger than a threshold.