Abstract
How do we create content that will become viral in a whole network after we share it with friends or followers? Significant research activity has been dedicated to the problem of strategically selecting a seed set of initial adopters so as to maximize a meme’s spread in a network. This line of work assumes that the success of such a campaign depends solely on the choice of a tunable seed set of adopters, while the way users perceive the propagated meme is fixed. Yet, in many real-world settings, the opposite holds: a meme’s propagation depends on users’ perceptions of its tunable characteristics, while the set of initiators is fixed.
In this paper, we address the natural problem that arises in such circumstances: Suggest content, expressed as a limited set of attributes, for a creative promotion campaign that starts out from a given seed set of initiators, so as to maximize its expected spread over a social network. To our knowledge, no previous work ad-
dresses this problem. We find that the problem is NP-hard and inapproximable. As a tight approximation guarantee is not admissible, we design an efficient heuristic, Explore-Update, as well as a conventional Greedy solution. Our experimental evaluation demonstrates that Explore-Update selects near-optimal attribute sets with real data, achieves 30% higher spread than baselines, and runs an order of magnitude faster than the Greedy solution.
In this paper, we address the natural problem that arises in such circumstances: Suggest content, expressed as a limited set of attributes, for a creative promotion campaign that starts out from a given seed set of initiators, so as to maximize its expected spread over a social network. To our knowledge, no previous work ad-
dresses this problem. We find that the problem is NP-hard and inapproximable. As a tight approximation guarantee is not admissible, we design an efficient heuristic, Explore-Update, as well as a conventional Greedy solution. Our experimental evaluation demonstrates that Explore-Update selects near-optimal attribute sets with real data, achieves 30% higher spread than baselines, and runs an order of magnitude faster than the Greedy solution.
Original language | English |
---|---|
Title of host publication | Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval |
Number of pages | 10 |
Publisher | Association for Computing Machinery |
Publication date | 2017 |
Pages | 565-574 |
ISBN (Print) | 978-1-4503-5022-8 |
DOIs | |
Publication status | Published - 2017 |
Event | The 40th International ACM SIGIR Conference on Research and Development in Information Retrieval - Shinjuku, Tokyo, Japan Duration: 7 Aug 2017 → 11 Aug 2017 Conference number: 40 http://sigir.org/sigir2017/ |
Conference
Conference | The 40th International ACM SIGIR Conference on Research and Development in Information Retrieval |
---|---|
Number | 40 |
Location | Shinjuku |
Country/Territory | Japan |
City | Tokyo |
Period | 07/08/2017 → 11/08/2017 |
Internet address |