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