Heuristic centrality methods challenge greedy optimization in influence maximization

Influence maximization is a process where a small number of nodes are selected from social networks to maximize the spread of information. Many of the algorithms designed are supported by strong theory, but we do not know enough about their practical performance. This paper presents an extensive empirical analysis of eight representative algorithms from three paradigms: greedy optimization (CELF++), sampling-based approximation (RIS, IMM) and structural heuristics (Degree, PageRank, Betweenness, Dangling, and GCCDC). We tested Facebook social network subgraphs containing 200, 400, 600, 800, and 1,000 nodes through 10 independent runs under the Independent Cascade model for each configuration to obtain statistically reliable results. The findings indicate a significant disparity between theoretical guarantees and actual performance: despite achieving $$(1-1/e)$$ of CELF++ approximation guarantee, CELF++ only achieves 11.2% of the spread attainable using sampling-based algorithms this gap is likely due to an insufficient number of Monte Carlo simulations and implementation constraints as opposed to a fundamental algorithmic flaw. Across all network scales, the sampling-based methods showed nearly optimal performance (IMM: $$955.24 \pm 0.74$$; RIS: $$951.27 \pm 2.22$$). Importantly, PageRank achieved 96.3% of IMM’s spread quality while being 794 times faster than the latter, which further proves that complex algorithms aren’t necessary for competing results. Betweenness centrality was found to perform as effectively as PageRank among new centrality measures while Dangling centrality and GCCDC performed as effectively as Degree centrality. All the differences in performance were found to be significantly different. The experimental results show that certain simple heuristics can outperform highly-optimized methods in practice and that theoretical guarantees do not always correlate with reality.