  Viral marketing is becoming important due to the popularity of online social
networks (OSNs). Companies may provide incentives (e.g., via free samples of a
product) to a small group of users in an OSN, and these users provide
recommendations to their friends, which eventually increases the overall sales
of a given product. Nevertheless, this also opens a door for "malicious
behaviors": dishonest users may intentionally give misleading recommendations
to their friends so as to distort the normal sales distribution. In this paper,
we propose a detection framework to identify dishonest users in OSNs. In
particular, we present a set of fully distributed and randomized algorithms,
and also quantify the performance of the algorithms by deriving probability of
false positive, probability of false negative, and the distribution of number
of detection rounds. Extensive simulations are also carried out to illustrate
the impact of misleading recommendations and the effectiveness of our detection
algorithms. The methodology we present here will enhance the security level of
viral marketing in OSNs.
