Rumor source obfuscation on irregular trees

Anonymous messaging applications have recently gained popularity as a means for sharing opinions without fear of judgment or repercussion. Messages in these applications propagate anonymously (without authorship metadata) over a network that is typically defined by social connections or physical proximity. However, recent advances in rumor source detection show that the source of such an anonymous message can be inferred by statistical inference attacks. Adaptive diffusion was recently proposed as a solution that achieves optimal source obfuscation over regular trees. However, in real social networks, node degrees different from node to node, and adaptive diffusion can be significantly sub-optimal. This gap increases as the degrees become more irregular. In order to quantify this gap, we model the underlying network as coming from standard branching processes with i.i.d. degree distributions. Building upon the analysis techniques from branching processes, we give an analytical characterization of the dependence between the probability of detection achieved by adaptive diffusion and the degree distribution. Further, this analysis provides a key insight: passing a rumor to a friend who has many friends makes the source more ambiguous. This leads to a new family of protocols that we call Preferential Attachment Adaptive Diffusion (PAAD). When messages are propagated according to PAAD, we give both the MAP estimator for finding the source and also an analysis of the probability of detection achieved by this adversary. The analytical results are not directly comparable, since the adversary's observed information has a different distribution under adaptive diffusion than under PAAD. Instead, we present results from numerical experiments that suggest that PAAD achieves a lower probability of detection, at the cost of increased communication for coordination.