A probability-driven structure-aware algorithm for influence maximization under independent cascade model
A probability-driven structure-aware algorithm for influence maximization under independent cascade model
复制标题
独立级联模型下影响力最大化的概率驱动结构感知算法
DOI：
10.1016/j.physa.2021.126318
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Yiguang Bai
中科院分区：
文献类型：
--
作者：
Yudong Gong;Sanyang Liu;Yiguang Bai
影响最大化（Influence maximization， IM）是寻找一组节点使影响传播到网络中最大的问题，在最新的研究中面临两个重要而棘手的问题：(i)规模诅咒：随着网络规模的增加，传统的方法在保证准确性上花费了大量的时间，需要重新评估网络中每个节点的影响传播，导致大量的计算开销；（ii）泛化问题：随着对各种网络和传播参数的研究越来越多，很难找到一个在每种拓扑上都表现良好的普遍适用的算法。在本文中，我们提出了一种新的概率驱动结构感知（PDSA）算法，该算法首先根据IC模型的边缘激活概率参数对网络进行裁剪/更新，然后使用图遍历算法（例如广度优先搜索算法）评估每个节点的影响传播分数。同时，我们采用一种基于中心性的独立级联（CIC）模型来近似更真实的传播场景。通过对六个真实世界/合成网络和六个CIC/IC模型的广泛实验，我们证明了PDSA在效果和效率方面比最先进的算法具有更好的性能。即使面对各种复杂的拓扑结构和传播参数，PDSA在解决IM问题方面也表现出出色的鲁棒性。
Influence maximization (IM) is the problem of finding a set of nodes that can achieve the maximal influence spreads into the network, which faces two significant but intractable issues in latest studies: (i) Curse of scales: with the increase of the network scale, traditional methods cost extensive times in guaranteeing accuracy, which re-evaluate influence spread of every node in network, leading to significant computational overhead; (ii) Generalization issue: with more and more studies on various networks and propagation parameters, it is difficult to find a universally appropriate algorithm that performs well in each topology. In this paper, we propose a novel probability-driven structure-aware (PDSA) algorithm, which begins by cutting/updating network according to the edge activation probability parameters of the IC model, and then uses a graph traversal algorithm (e.g., breadth first search algorithm) to evaluate the influence spread scores of each node. Meanwhile, we adopt a kind of centrality-based independent cascade (CIC) model to approximate a more realistic propagation scenario. Through extensive experiments with six real-world/synthetic networks and six CIC/IC models, we demonstrate that PDSA achieves great performance over state-of-the-art algorithms in terms of effect and efficiency. Even facing various complex topologies and propagation parameters, PDSA exhibits excellent robustness in solving IM problems.