通信学报2026，Vol.47Issue(7)：80-95,16.DOI:10.11959/j.issn.1000-436x.TXXB260210
基于高阶反向影响采样的无向超图影响力最大化算法
Influence maximization algorithm for undirected hypergraphs based on higher-order reverse influence sampling
摘要
Abstract
Existing studies on undirected hypergraph influence maximization generally lack in-depth analysis and effec-tive modeling of hypergraph higher-order structures,making it difficult to characterize the complex group-level informa-tion diffusion mechanisms.Meanwhile,most existing algorithms rely heavily on local topological features and fail to capture collective behaviors.To address these issues,information diffusion in undirected hypergraphs was investigated systematically,two typical group-based information diffusion processes were formalized,and an undirected hypergraph independent cascade model was proposed.Based on this model and the classic reverse influence sampling framework,a hypergraph influence maximization algorithm based on higher-order reverse influence sampling was developed,and is was theoretically proved that it achieved a(1-1/e-ε)approximation to the optimal solution.Experiments on eight real-world hypergraph datasets show that the proposed method significantly outperforms all baseline approaches,improving the influence spread by up to 42.85%.Meanwhile,its average runtime is only 0.7%of the CELF algorithm and is compa-rable to heuristic-based methods.关键词
影响力最大化/无向超图/独立级联模型/反向影响采样/社交网络Key words
influence maximization/undirected hypergraph/independent cascade model/reverse influence sampling/so-cial network分类
信息技术与安全科学引用本文复制引用
芮晓彬,吉嘉欣,方强鹏,时纪龙,王志晓..基于高阶反向影响采样的无向超图影响力最大化算法[J].通信学报,2026,47(7):80-95,16.基金项目
国家自然科学基金资助项目(No.62402496) （No.62402496）
江苏省基础研究计划资助项目(No.BK20242084) The National Natural Science Foundation of China(No.62402496),The Basic Research Program of Jiangsu Province(No.BK20242084) （No.BK20242084）
