Today, brands promote their products via advertisements shared among online social network users. A significant body of research has been devoted to the problem of selecting a set of initial, strategic adopters that maximizes a promotion campaign's spread in a network. This line of works assumes that (i) a campaign's success depends solely on the network positions of initial adopters, regardless of a post's content perception by users and (ii) the set of initial adopters can be tuned, while the post is fixed. Yet in many real-world settings, the opposite holds: propagation depends on users' preferences, and a campaign's attributes can be tuned, while the set of initial adopters is fixed.
We address the natural problem that arises in such circumstances: Compose a creative advertising campaign, characterized by a limited set of attributes that determine its network-wide attractiveness, and starting out from a given set of initial adopters, so as to maximize its viral spread within the network. To our knowledge, no previous work addresses 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 approach. Our experimental evaluation demonstrates that our Explore-Update algorithm selects near-optimal sets of attributes with real data and runs orders of magnitude faster than the Greedy solution.