Efficient Algorithms for Influence Maximization in Hypergraphs by Stratified Sampling

Influence maximization (IM) aims to identify <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula> vertices that maximize influence spread across a network. While well-studied in regular graphs, IM in hypergraphs presents unique challenges: conventional graph-based IM methods fail to capture hypergraph-specific structural properties, and existing hypergraph IM algorithms lack theoretical guarantees for time complexity and approximation quality. We address these gaps with <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">HyperIM</i>, a novel algorithm leveraging stratified sampling to generate random reversible reachable sets for efficient seed selection. Our key innovation lies in dual-perspective stratified sampling: assigning sampling probabilities based on vertex structural properties while applying size-adaptive sampling strategies. This approach optimizes seed selection, reduces computational costs, and provides rigorous theoretical guarantees. We further propose <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">HyperIM_BRR</i>, which optimizes the required number of reversible reachable sets, achieving substantial cost reduction without sacrificing accuracy. Extensive experiments on real-world hypergraphs demonstrate that our algorithms significantly outperform state-of-the-art methods, delivering faster execution times and superior influence spread.