Understanding Influence Maximization via Higher-Order Decomposition
Understanding Influence Maximization via Higher-Order Decomposition
复制标题
DOI：
10.1137/1.9781611977653.ch86
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
Zonghan Zhang;Zhiqian Chen
中科院分区：
文献类型：
--
作者：
Zonghan Zhang;Zhiqian Chen
鉴于其在在线社交网络上的广泛应用，影响力最大化（IM）在过去几十年中获得了相当大的关注。由于IM的复杂性，目前的研究大多集中在估计节点的一阶贡献，以选择一个种子集，忽略了不同的种子之间的高阶相互作用。因此，实际的影响力传播经常偏离预期，并且仍然不清楚种子集如何定量地促成这种偏离。为了解决这一不足，这项工作剖析的影响施加在单个种子和他们的高阶相互作用，利用Sobol指数，方差为基础的敏感性分析。为了适应IM上下文，种子选择被描述为二进制变量，并被分成不同阶数的分布。基于我们的分析与各种Sobol指数，IM算法被称为SIM提出了改善目前的IM算法的性能，通过过度选择节点，其次是战略修剪。实例研究表明，对碰撞效应的解释可以独立地识别种子间的关键高阶相互作用。通过在合成图和真实图上的实验，证明了SIM具有上级的有效性和竞争力。
Given its vast application on online social networks, Influence Maximization (IM) has garnered considerable attention over the last couple of decades. Due to the intricacy of IM, most current research concentrates on estimating the first-order contribution of the nodes to select a seed set, disregarding the higher-order interplay between different seeds. Consequently, the actual influence spread frequently deviates from expectations, and it remains unclear how the seed set quantitatively contributes to this deviation. To address this deficiency, this work dissects the influence exerted on individual seeds and their higher-order interactions utilizing the Sobol index, a variance-based sensitivity analysis. To adapt to IM contexts, seed selection is phrased as binary variables and split into distributions of varying orders. Based on our analysis with various Sobol indices, an IM algorithm dubbed SIM is proposed to improve the performance of current IM algorithms by over-selecting nodes followed by strategic pruning. A case study is carried out to demonstrate that the explanation of the impact effect can dependably identify the key higher-order interactions among seeds. SIM is empirically proved to be superior in effectiveness and competitive in efficiency by experiments on synthetic and real-world graphs.