Optimizing CELF Algorithm for Influence Maximization Problem in Social Networks

The Influence Maximization Problem in social networks aims to find a minimal set of individuals to produce the highest influence on other individuals in the network. In the last two decades, a lot of algorithms have been proposed to solve the time efficiency and effectiveness challenges of this NP-Hard problem. Undoubtedly, the CELF algorithm (besides the naive greedy algorithm) has the highest effectiveness among them. Of course, the CELF algorithm is faster than the naive greedy algorithm (about 700 times). This superiority has led many researchers to make extensive use of the CELF algorithm in their innovative approaches. However, the main drawback of the CELF algorithm is the very long running time of its first iteration. Because it has to estimate the influence spread for all nodes by expensive Monte-Carlo simulations, similar to the naive greedy algorithm. In this paper, a heuristic approach is proposed, namely Optimized-CELF algorithm, to improve this drawback of the CELF algorithm by avoiding unnecessary Monte-Carlo simulations. It is found that the proposed algorithm reduces the CELF running time, and subsequently improves the time efficiency of other algorithms that employed the CELF as a base algorithm. Experimental results on the wide spectral of real datasets showed that the Optimized-CELF algorithm provided better running time gain, about 88-99% and 56-98% for k=1 and k=50, respectively, compared to the CELF algorithm without missing effectiveness.