Optimization Online


Efficient Presolving Methods for Influence Maximization Problem in Social Networks

Sheng-Jie Chen (shengjie_chen***at***lsec.cc.ac.cn)
Wei-Kun Chen (chenweikun***at***bit.edu.cn)
Yu-Hong Dai (dyh***at***lsec.cc.ac.cn)
Jian-Hua Yuan (jianhuayuan***at***bupt.edu.cn)
Hou-Shan Zhang (houshan_zhang***at***bupt.edu.cn)

Abstract: The influence maximization problem (IMP) is a hot topic, which asks for identifying a limited number of key individuals to spread influence in a social network such that the expected number of influenced individuals is maximized. The stochastic maximal covering location problem (SMCLP) formulation is a mixed integer programming formulation that approximates the IMP by the Monte-Carlo sampling. However, the SMCLP formulation cannot be solved efficiently using existing exact algorithms due to its large problem size. In this paper, we concentrate on deriving presolving methods to reduce the problem size and hence enhance the capability of employing exact algorithms in solving the IMP. In particular, we propose two effective presolving methods, called the strongly connected nodes aggregation (SCNA) and the isomorphic nodes aggregation (INA). The SCNA enables us to build a new SMCLP formulation that is much more compact than the existing one. For the INA, an analysis is given on the one-way bipartite social network. Specifically, we show that under certain conditions, the problem size of the reduced SMCLP formulation depends only on the size of the given network but not on the number of samplings and this reduced formulation is strongly polynomial-time solvable. Finally, we integrate the proposed presolving methods SCNA and INA into the Benders decomposition algorithm, which is recognized as one of the state-of-the-art exact algorithms for solving the IMP. Numerical results demonstrate that with the SCNA and INA, the Benders decomposition algorithm is much more effective in solving the IMP in terms of solution time.

Keywords: Benders decomposition, Influence maximization, Integer programming, Presolving methods, Social network, Stochastic programming

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Citation: S.-J. Chen, W.-K. Chen, Y.-H. Dai, J.-H. Yuan, and H.-S. Zhang. Efficient Presolving Methods for Influence Maximization Problem in Social Networks. Beijing Institute of Technology, 2021.

Download: [PDF]

Entry Submitted: 01/01/2021
Entry Accepted: 01/02/2021
Entry Last Modified: 01/03/2021

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