Optimization Online


An Efficient Linear Programming Based Method for the Influence Maximization Problem in Social Networks

Evren GŁney (guneye***at***mef.edu.tr)

Abstract: The influence maximization problem (IMP) aims to determine the most influential individuals within a social network. In this study first we develop a binary integer program that approximates the original problem by Monte Carlo sampling. Next, to solve IMP efficiently, we propose a linear programming relaxation based method with a provable worst case bound that converges to the current state-of-the-art (1-1/e) bound asymptotically. Experimental analysis indicate that the new method is superior to the state-of-the-art in terms of solution quality and this is one of the few studies that provides approximate optimal solutions for certain real life social networks

Keywords: Influence maximization, binary integer programming, sample average approximation, pipage method

Category 1: Combinatorial Optimization (Approximation Algorithms )

Category 2: Integer Programming (0-1 Programming )

Category 3: Network Optimization

Citation: Technical Report -TRIE1801- MEF University, Department of Industrial Engineering, 2018/07

Download: [PDF]

Entry Submitted: 10/25/2018
Entry Accepted: 10/25/2018
Entry Last Modified: 06/20/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