Efficient Algorithms for Influence Maximization in Hypergraphs by Stratified Sampling

doi:10.1109/TKDE.2025.3599790

Efficient Algorithms for Influence Maximization in Hypergraphs by Stratified Sampling

0

PRE

AI

DOI：10.1109/TKDE.2025.3599790

Original

Original request for help

Save

Abstract

En 中文

Influence maximization (IM) aims to identify $k$ 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 HyperIM, 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 HyperIM_BRR, 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.

Keywords:

Influence maximization

stratified sampling

hypergraphs

Efficient Algorithms for Influence Maximization in Hypergraphs by Stratified Sampling

Abstract

Journal

Organization

Cited Papers