DocumentCode :
640274
Title :
Rumor source detection under probabilistic sampling
Author :
Karamchandani, Nikhil ; Franceschetti, Massimo
Author_Institution :
Dept. of EE, Univ. of California Los Angeles, Los Angeles, CA, USA
fYear :
2013
fDate :
7-12 July 2013
Firstpage :
2184
Lastpage :
2188
Abstract :
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.
Keywords :
estimation theory; geometry; information theory; polynomials; probability; trees (mathematics); exponential growth; geometric trees; optimal estimation; polynomial growth; probabilistic sampling; rumor source detection; unidentified source; Computational modeling; Educational institutions; Exponential distribution; Information theory; Probabilistic logic; Random variables; Silicon;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Information Theory Proceedings (ISIT), 2013 IEEE International Symposium on
Conference_Location :
Istanbul
ISSN :
2157-8095
Type :
conf
DOI :
10.1109/ISIT.2013.6620613
Filename :
6620613
Link To Document :
بازگشت