Scholarlink

<p>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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\((1-1/e)\)</EquationSource> </InlineEquation> 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: <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(955.24 \pm 0.74\)</EquationSource> </InlineEquation>; RIS: <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(951.27 \pm 2.22\)</EquationSource> </InlineEquation>). 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Heuristic centrality methods challenge greedy optimization in influence maximization

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年4月11日

查看全文
  • Laiali Almazaydeh,
  • Arar Al Tawil,
  • Amneh Shaban,
  • Rabiah Al-Qudah

摘要

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.