Weighted Target Set Selection on Social Networks
Viral marketing and influence maximization on social networks has become a problem of significant interest. We consider a problem in this setting referred to as the weighted target set selection (WTSS) problem. Earlier research focused on approximation algorithms for the unweighted case of the problem which is known to be NP hard. Motivated by the desire to develop a better understanding of fundamental problems in social network analytics, we seek to develop mathematical programming approaches to solve the WTSS problem exactly. Our paper makes three contributions. First, we propose a polynomial time algorithm for the WTSS problem on trees. More importantly, we present a tight and compact extended formulation for the WTSS problem on trees. Specifically, we provide an extended linear programming formulation whose projection onto the space of the natural node variables is the convex hull of feasible target set vectors. We also project the formulation onto the space of the natural node variables and describe the polytope of the WTSS problem on trees. We build upon the result for trees in two ways. First, we provide a description of the polytope of the WTSS problem on cycles based on lifting a set of valid inequalities that are natural analogues in cycles to inequalities in the tree polytope. Next, based on the observation that the influence propagation network is acyclic we add an exponential set of inequalities that enforce this condition and show how to apply the extended formulation for the tree case to general graphs. Using this approach we design and implement a branch and cut approach to solve the WTSS problem on general graphs and share our computational experience on networks with up to 10,000 nodes.