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

原文链接

原文求助

摘要

En 中文

影响最大化（IM）旨在识别$k$个顶点以最大化网络中的影响扩散。尽管在常规图上已有深入研究，但超图中的IM面临独特挑战：基于常规图的IM方法无法捕捉超图特有的结构属性，且现有的超图IM算法在时间复杂度和近似质量方面缺乏理论保证。我们通过HyperIM算法填补这些空白，该算法利用分层抽样生成随机的可逆可达集以实现高效的种子选择。我们的关键创新在于双视角分层抽样：基于顶点结构属性分配抽样概率，同时采用大小自适应抽样策略。该方法优化了种子选择，降低了计算成本，并提供了严谨的理论保证。我们进一步提出HyperIM_BRR算法，通过优化所需的可逆可达集数量，在不牺牲准确性的情况下显著降低成本。在真实超图上的广泛实验表明，我们的算法显著优于当前最先进方法，实现了更快的执行时间和更优的影响扩散效果。

Keyword:

Influence maximization

stratified sampling

hypergraphs

Efficient Algorithms for Influence Maximization in Hypergraphs by Stratified Sampling

摘要

期刊

机构

引用论文