TY - JOUR
T1 - Rumor Source Detection with Multiple Observations under Adaptive Diffusions
AU - Rácz, Miklós Z.
AU - Richey, Jacob
N1 - Funding Information:
Manuscript received June 26, 2020; revised August 26, 2020; accepted August 31, 2020. Date of publication September 7, 2020; date of current version March 17, 2021. The work of Miklos Z. Rácz was supported in part by NSF under Grant DMS 1811724 and in part by a Princeton SEAS Innovation Award. Recommended for acceptance by Prof. Xianbin Cao. (Corresponding author: Miklos Racz.) Miklós Z. Rácz is with Princeton University, Princeton, NJ 08544 USA (e-mail: [email protected]).
Publisher Copyright:
© 2013 IEEE.
PY - 2021/1/1
Y1 - 2021/1/1
N2 - Recent work, motivated by anonymous messaging platforms, has introduced adaptive diffusion protocols which can obfuscate the source of a rumor: a 'snapshot adversary' with access to the subgraph of 'infected' nodes can do no better than randomly guessing the entity of the source node. What happens if the adversary has access to multiple independent snapshots? We study this question when the underlying graph is the infinite d-regular tree. We show that (1) a weak form of source obfuscation is still possible in the case of two independent snapshots, but (2) already with three observations there is a simple algorithm that finds the rumor source with constant probability, regardless of the adaptive diffusion protocol. We also characterize the tradeoff between local spreading and source obfuscation for adaptive diffusion protocols (under a single snapshot). These results raise questions about the robustness of anonymity guarantees when spreading information in social networks.
AB - Recent work, motivated by anonymous messaging platforms, has introduced adaptive diffusion protocols which can obfuscate the source of a rumor: a 'snapshot adversary' with access to the subgraph of 'infected' nodes can do no better than randomly guessing the entity of the source node. What happens if the adversary has access to multiple independent snapshots? We study this question when the underlying graph is the infinite d-regular tree. We show that (1) a weak form of source obfuscation is still possible in the case of two independent snapshots, but (2) already with three observations there is a simple algorithm that finds the rumor source with constant probability, regardless of the adaptive diffusion protocol. We also characterize the tradeoff between local spreading and source obfuscation for adaptive diffusion protocols (under a single snapshot). These results raise questions about the robustness of anonymity guarantees when spreading information in social networks.
KW - Information diffusion
KW - social networks
KW - source detection
KW - source obfuscation
UR - http://www.scopus.com/inward/record.url?scp=85102981060&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85102981060&partnerID=8YFLogxK
U2 - 10.1109/TNSE.2020.3022621
DO - 10.1109/TNSE.2020.3022621
M3 - Article
AN - SCOPUS:85102981060
SN - 2327-4697
VL - 8
SP - 1
EP - 12
JO - IEEE Transactions on Network Science and Engineering
JF - IEEE Transactions on Network Science and Engineering
IS - 1
M1 - 9187692
ER -