Online Influence Maximization (OIM) aims to optimize seed selection strategies for maximizing overall influence with unknown diffusion parameters. Existing research mostly focuses on traditional graph structures under the Independent Cascading (IC) or Linear Threshold (LT) models, known for their submodular properties and guarantees in an offline setting. However, in practice, these models overlook scenarios where individuals organize into interconnected interest-based groups, leading to mutual group influence. Moreover, as group membership expands, the collective influence on external groups grows, showcasing dynamic group effects, which are observed in product promotion in online group chats and research advocacy in co-authorship networks. This study explores influence maximization in hypergraphs, considering dynamic group effects in offline settings (HG-IM) and addressing the Online Influence Maximization (OIM) issue within this framework (HG-OIM). We face two key challenges: (i) Group effects dynamics complicate submodularity analysis. (ii) Existing OIM algorithms struggle with HG-OIM due to complexities in dynamic group effects. Moreover, determining the offline oracle (solution) proves challenging due to our more complicated yet reasonable propagation process compared with traditional IC and LT. To overcome these challenges, we introduce the HLVT diffusion framework to quantify group effects and establish an if-and-only-if (IFF) condition with submodularity. Finally, we present the HG-ETC algorithm for online settings and analyze the offline oracle with a sandwich approach.

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

Dynamic Group Effects Analysis for Online Influence Maximization in Hypergraphs

  • Xinyan Su,
  • Zhiheng Zhang,
  • Jun Li

摘要

Online Influence Maximization (OIM) aims to optimize seed selection strategies for maximizing overall influence with unknown diffusion parameters. Existing research mostly focuses on traditional graph structures under the Independent Cascading (IC) or Linear Threshold (LT) models, known for their submodular properties and guarantees in an offline setting. However, in practice, these models overlook scenarios where individuals organize into interconnected interest-based groups, leading to mutual group influence. Moreover, as group membership expands, the collective influence on external groups grows, showcasing dynamic group effects, which are observed in product promotion in online group chats and research advocacy in co-authorship networks. This study explores influence maximization in hypergraphs, considering dynamic group effects in offline settings (HG-IM) and addressing the Online Influence Maximization (OIM) issue within this framework (HG-OIM). We face two key challenges: (i) Group effects dynamics complicate submodularity analysis. (ii) Existing OIM algorithms struggle with HG-OIM due to complexities in dynamic group effects. Moreover, determining the offline oracle (solution) proves challenging due to our more complicated yet reasonable propagation process compared with traditional IC and LT. To overcome these challenges, we introduce the HLVT diffusion framework to quantify group effects and establish an if-and-only-if (IFF) condition with submodularity. Finally, we present the HG-ETC algorithm for online settings and analyze the offline oracle with a sandwich approach.