  Social networks are the major routes for most individuals to exchange their
opinions about new products, social trends and political issues via their
interactions. It is often of significant importance to figure out who initially
diffuses the information, ie, finding a rumor source or a trend setter. It is
known that such a task is highly challenging and the source detection
probability cannot be beyond 31 percent for regular trees, if we just estimate
the source from a given diffusion snapshot. In practice, finding the source
often entails the process of querying that asks "Are you the rumor source?" or
"Who tells you the rumor?" that would increase the chance of detecting the
source. In this paper, we consider two kinds of querying: (a) simple batch
querying and (b) interactive querying with direction under the assumption that
queries can be untruthful with some probability. We propose estimation
algorithms for those queries, and quantify their detection performance and the
amount of extra budget due to untruthfulness, analytically showing that
querying significantly improves the detection performance. We perform extensive
simulations to validate our theoretical findings over synthetic and real-world
social network topologies.
