Optimization Online


An exact algorithm for robust influence maximization

Giacomo Nannicini(nannicini***at***us.ibm.com)
Giorgio Sartor(giorgio.sartor***at***sintef.no)
Emiliano Traversi(traversi***at***lipn.fr)
Roberto Wofler Calvo(wolfler***at***lipn.fr)

Abstract: 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 ($\ge 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.

Keywords: Influence Maximization, Integer Programming, Robust Optimization

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Robust Optimization


Download: [PDF]

Entry Submitted: 06/27/2019
Entry Accepted: 07/01/2019
Entry Last Modified: 06/27/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society