Abstract

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.

Short CV

Panagiotis (Panos) Karras is an Associate Professor of Computer Science at Aalborg University. He earned a Ph.D. in Computer Science from the University of Hong Kong and an M. Eng. in Electrical and Computer Engineering from the National Technical University of Athens. He has held positions at the Skolkovo Institute of Science and Technology, Rutgers Business School, the National University of Singapore, the University of Zurich, and the Technical University of Denmark. Panos' interests are in the confluence of data management, data mining, and database security. His work has introduced algorithms and systems that allow for the satisfaction of efficiency, accuracy, privacy, integrity, and adaptability requirements in data representation, indexing, and querying. Panos has published over 50 research articles and received over 1500 citations. He has been awarded with the 2008 Hong Kong Young Scientist Award; supported by Singapore’s Lee Kuan Yew Endowment Fund; and has worked with the MIT Skoltech Initiative. He regularly serves as a program committee member and referee for the major international conferences and journals in the above areas.

Host: Prof. Dr. Emmanuel Müller