Title: Coupon Advertising in Online Social Systems: Algorithms and Sampling Techniques,
Abstract: Online social systems have become important platforms for viral marketing
where the advertising of products is carried out with the communication of
users. After adopting the product, the seed buyers may spread the information
to their friends via online messages e.g. posts and tweets. In another issue,
electronic coupon system is one of the relevant promotion vehicles that help
manufacturers and retailers attract more potential customers. By offering
coupons to seed buyers, there is a chance to convince the influential users who
are, however, at first not very interested in the product. In this paper, we
propose a coupon based online influence model and consider the problem that how
to maximize the profit by selecting appropriate seed buyers. The considered
problem herein is markedly different from other influence related problems as
its objective function is not monotone. We provide an algorithmic analysis and
give several algorithms designed with different sampling techniques. In
particular, we propose the RA-T and RA-S algorithms which are not only provably
effective but also scalable on large datasets. The proposed theoretical results
are evaluated by extensive experiments done on large-scale real-world social
networks. The analysis of this paper also provides an algorithmic framework for
non-monotone submodular maximization problems in social networks.