Rumor Source Detection With Multiple Observations Under Adaptive Diffusions
Rumor Source Detection With Multiple Observations Under Adaptive Diffusions
复制标题
DOI：
10.1109/tnse.2020.3022621
复制
发表时间：
2020-06
影响因子：
6.6
通讯作者：
Miklós Z. Rácz;Jacob Richey
中科院分区：
文献类型：
--
作者：
Miklós Z. Rácz;Jacob Richey
最近的工作是由匿名消息传递平台融合的，引入了自适应扩散协议，可以使谣言的来源混淆：“快照对手”，访问“感染”节点的子图的“快照对手”不能比随机猜测来源的实体更好节点。在两个独立的快照中，（2）已经有三个观察结果，有一个简单的算法，可以找到概率持续的规则，而不论自适应扩散协议如何单个快照）这些结果引起了关于匿名性鲁棒性在社交网络中传播时的疑问。
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.