Rumor Source Detection with Multiple Observations under Adaptive Diffusions

Miklós Z. Rácz, Jacob Richey

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Article number9187692
Pages (from-to)1-12
Number of pages12
JournalIEEE Transactions on Network Science and Engineering
Volume8
Issue number1
DOIs
StatePublished - Jan 1 2021

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Computer Science Applications
  • Computer Networks and Communications

Keywords

  • Information diffusion
  • social networks
  • source detection
  • source obfuscation

Cite this