EUVIMEDEUVIMED entdecken
Crossref

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

S. Raghavan, Rui Zhang

INFORMS Journal on Optimization · 2019

DOI: 10.1287/ijoo.2019.0012 ↗

Kurz gefasst

Fachartikel in der Zeitschrift INFORMS Journal on Optimization, 2019. Verfasst von S. Raghavan und 1 weiteren Autor:innen. Die Arbeit wurde bisher 28-mal zitiert (Crossref) und nennt 22 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Raghavan, S., & Zhang, R. (2019). A Branch-and-Cut Approach for the Weighted Target Set Selection Problem on Social Networks. INFORMS Journal on Optimization. https://doi.org/10.1287/ijoo.2019.0012

Vancouver

Raghavan S, Zhang R. A Branch-and-Cut Approach for the Weighted Target Set Selection Problem on Social Networks. INFORMS Journal on Optimization. 2019. doi:10.1287/ijoo.2019.0012

BibTeX
@article{Raghavan2019,
  author = {Raghavan, S. and Zhang, Rui},
  title = {A Branch-and-Cut Approach for the Weighted Target Set Selection Problem on Social Networks},
  journal = {INFORMS Journal on Optimization},
  year = {2019},
  doi = {10.1287/ijoo.2019.0012}
}
Kostenlos starten →