论文标题
在自适应扩散下进行多个观察结果的谣言来源检测
Rumor source detection with multiple observations under adaptive diffusions
论文作者
论文摘要
最近的工作是由匿名消息传递平台激励的，引入了自适应扩散协议，这些协议可以混淆谣言的来源：一个“快照对手”，访问“感染”节点的子图的“快照对手”不能比随机猜测源节点的实体更好地做得更好。如果对手可以访问多个独立快照，会发生什么？我们研究了这个问题，何时是基础图是无限$ d $的树木。我们表明，（1）在两个独立的快照的情况下，仍然可以使用一种弱的源混淆形式，但是（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.
