Understanding Influence Maximization via Higher-Order Decomposition
This work addresses the problem of more accurate influence spread prediction in online social networks for researchers and practitioners, but it is incremental as it builds on existing IM methods by incorporating higher-order analysis.
The paper tackles the problem of Influence Maximization (IM) by addressing the neglect of higher-order interactions between seeds, which causes deviations in influence spread, and proposes the SIM algorithm that improves performance by over-selecting nodes and strategic pruning, achieving superior effectiveness and competitive efficiency in experiments.
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.