  For the purpose of maximizing the spread of influence caused by a certain
small number k of nodes in a social network, we are asked to find a k-subset of
nodes (i.e., a seed set) with the best capacity to influence the nodes not in
it. This problem of influence maximization (IM) has wide application, belongs
to subset problems, and is NP-hard. To solve it, we should theoretically
examine all seed sets and evaluate their influence spreads, which is
time-consuming. Therefore, metaheuristic strategies are generally employed to
gain a good seed set within a reasonable time. We observe that many algorithms
for the IM problem only adopt a uniform mechanism in the whole solution search
process, which lacks a response measure when the algorithm becomes trapped in a
local optimum. To address this issue, we propose a phased hybrid
evaluation-enhanced (PHEE) approach for IM, which utilizes two distinct search
strategies to enhance the search of optimal solutions: a randomized range
division evolutionary (RandRDE) algorithm to improve the solution quality, and
a fast convergence strategy. Our approach is evaluated on 10 real-world social
networks of different sizes and types. Experimental results demonstrate that
our algorithm is efficient and obtains the best influence spread for all the
datasets compared with three state-of-the-art algorithms, outperforms the time
consuming CELF algorithm on four datasets, and performs worse than CELF on only
two networks.
