Minimizing Seed Set for Viral Marketing

Cheng Long, Raymond Chi-Wing Wong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

42 Citations (Scopus)

Abstract

Viral marketing has attracted considerable concerns in recent years due to its novel idea of leveraging the social network to propagate the awareness of products. Specifically, viral marketing is to first target a limited number of users (seeds) in the social network by providing incentives, and these targeted users would then initiate the process of awareness spread by propagating the information to their friends via their social relationships. Extensive studies have been conducted for maximizing the awareness spread given the number of seeds. However, all of them fail to consider the common scenario of viral marketing where companies hope to use as few seeds as possible yet influencing at least a certain number of users. In this paper, we propose a new problem, called J-MIN-Seed, whose objective is to minimize the number of seeds while at least J users are influenced. J-MIN-Seed, unfortunately, is proved to be NP-hard in this work. In such case, we develop a greedy algorithm that can provide error guarantees for J-MIN-Seed. Furthermore, for the problem setting where J is equal to the number of all users in the social network, denoted by Full-Coverage, we design other efficient algorithms. Extensive experiments were conducted on real datasets to verify our algorithm.
Original languageEnglish
Title of host publication2011 IEEE 11th International Conference on Data Mining
Place of PublicationVancouver, Canada
PublisherAssociation for Computing Machinery (ACM)
Pages427-436
Number of pages10
ISBN (Print)978-1-4577-2075-8
Publication statusPublished - 2011
Externally publishedYes

Fingerprint Dive into the research topics of 'Minimizing Seed Set for Viral Marketing'. Together they form a unique fingerprint.

  • Cite this

    Long, C., & Wong, R. C-W. (2011). Minimizing Seed Set for Viral Marketing. In 2011 IEEE 11th International Conference on Data Mining (pp. 427-436). Association for Computing Machinery (ACM).