W&M Featured Events

Location

Abstract:

The study of viral marketing strategies on social networks has become an area of significant research interest. Roughly, these problems seek to identify which individuals in a social network to target so that a given proportion of the target population is influenced at minimum cost. Motivated by the desire to develop a better understanding of fundamental problems in social network analytics, we study problems in this domain and seek to develop mathematical programming approaches to solve them exactly. In this talk, we focus on a combinatorial optimization problem 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. Our work makes three contributions. First, we propose a polynomial time algorithm for the WTSS problem on trees. Second, 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. Third, we focus on general graphs and build upon the result for trees. 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 arbitrary graphs. Using this idea, we design and implement a branch-and-cut approach to solve the WTSS problem on arbitrary graphs and share our computational experience on simulated and real-world networks with up to 10,000 nodes. Extensions of this work to related problems and variants will be discussed.

Contact

Anh Ninh

This Event Appears On

• W&M Featured Events
• Arts & Sciences Events
• Mathematics Events