Selecting observers for source localization via error exponents

Abstract

In today's large social and technological networks, since it is unfeasible to observe all the nodes, the source of diffusion is determined based on the observations of a subset of nodes. The probability of source localization error depends on the particular choice of observer nodes. We propose a criterion for observer node selection based on the minimal pairwise Chernoff distance between distributions of different source candidates. The proposed approach is optimal for the fastest error decay with vanishing noise. Although suboptimal for non-negligible noise, through simulation, we demonstrate its applicability in achieving low error probability. We also analyze the effect of network topology on the resulting error by bounding the smallest Chernoff distance for some specific networks.