Til hovedinnhold
Norsk English

An exact algorithm for robust influence maximization

Sammendrag

We propose a Branch-and-Cut algorithm for the robust influence maximization problem. The influence maximization problem aims to identify, in a social network, a set
of given cardinality comprising actors that are able to influence the maximum number
of other actors. We assume that the social network is given in the form of a graph with
node thresholds to indicate the resistance of an actor to influence, and arc weights to
represent the strength of the influence between two actors. In the robust version of the
problem that we study, the node thresholds and arc weights are affected by uncertainty
and we optimize over a worst-case scenario within given robustness budgets. We study
properties of the robust solution and show that even computing the worst-case scenario
for given robustness budgets is NP-hard. We implement an exact Branch-and-Cut as
well as a heuristic Branch-Cut-and-Price. Numerical experiments show that we are
able to solve to optimality instances of size comparable to other exact approaches in
the literature for the non-robust problem, and we can tackle the robust version with
similar performance. On larger instances (≥ 2000 nodes), our heuristic Branch-Cut-and-Price significantly outperforms a 2-opt heuristic. An extended abstract of this
paper appeared in the proceedings of IPCO 2019.

Kategori

Vitenskapelig artikkel

Språk

Engelsk

Forfatter(e)

  • Giacomo Nannicini
  • Giorgio Sartor
  • Emiliano Traversi
  • Roberto Wolfler-Calvo

Institusjon(er)

  • USA
  • SINTEF Digital / Mathematics and Cybernetics
  • Université Sorbonne Paris Nord
  • Università degli Studi di Cagliari

År

2020

Publisert i

Mathematical programming

ISSN

0025-5610

Årgang

183

Side(r)

419 - 453

Vis denne publikasjonen hos Cristin