A Branch-and-Cut Approach for the Weighted Target Set Selection Problem on Social Networks Journal Article uri icon

Overview

abstract

  • The study of viral marketing strategies on social networks has become an area of significant research interest. In this setting, we consider a combinatorial optimization problem, referred to as the weighted target set selection (WTSS) problem. Earlier research has 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 the fundamental problems in social network analytics, we seek to develop mathematical programming approaches to solve the WTSS problem exactly. We build upon a tight and compact extended formulation for the WTSS problem on trees described in a companion paper and show that it is also a tight and compact extended formulation for directed acyclic graphs (DAGs). On the basis of the observation that the influence propagation network in any arbitrary graph is acyclic, we add an exponential set of inequalities that enforce this condition and show how to apply the extended formulation for DAGs to arbitrary graphs. Using this idea, we develop and implement a branch-and-cut approach to solve the WTSS problem on arbitrary graphs. Our computational experience on a test-bed of 180 real-world graph instances (with up to approximately 155,000 nodes and 327,000 edges) demonstrates the quality and efficacy of our solution approach. The branch-and-cut approach finds solutions that are on average 0.90% from optimality and solves 60 of the 180 instances to optimality. On the other hand, the best heuristic solutions generated are on average 5.46 times worse than the solutions generated by the branch-and-cut approach.

publication date

  • October 1, 2019

has restriction

  • gold

Date in CU Experts

  • January 15, 2020 7:35 AM

Full Author List

  • Raghavan S; Zhang R

author count

  • 2

Other Profiles

International Standard Serial Number (ISSN)

  • 2575-1484

Electronic International Standard Serial Number (EISSN)

  • 2575-1492

Additional Document Info

start page

  • 304

end page

  • 322

volume

  • 1

issue

  • 4