CAM Seminar——Efficient presolving methods for influence maximization problem in social networks
报告人：Weikun Chen (Beijing Institute of Technology)
时间：2021-10-26 10:30-11:30
地点：Room 1560, Sciences Building No. 1
摘要：The influence maximization problem (IMP) aims to identify a limited set 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 talk, 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), to reduce the problem size of the SMCLP formulation. 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. To show the performance impact of the proposed presolving methods SCNA and INA, we integrate them 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 proposed presolving methods SCNA and INA, the Benders decomposition algorithm is much more effective in solving the IMP in terms of solution time.
