报告题目：Efficient presolving methods for influence maximization problem in social networks

报告人：陈伟坤（北京理工大学数学与统计学院）

主持人：张国涵

报告时间：2021年4月27日下午2:00-4:00

报告地点：主楼1214

报告摘要：

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 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.

报告人介绍：

陈伟坤，北京理工大学数学与统计学院特别副研究员，硕士生导师。2019年在中国科学院数学与系统科学研究院获得博士学位。主要研究兴趣是整数规划理论、算法与软件及其在无线通信与社交网络等领域中的应用。现为北京运筹学会理事，在IEEE Journal on Selected Areas in Communications，Journal of Global Optimization，Science China Mathematics，EURO Journal on Computational Optimization等杂志发表数篇学术论文。2018年获得中国运筹学会”科学技术奖运筹应用奖”，2020年获得中国科学院“中国科学院优秀博士学位论文”。