基于时间延迟扩散模型的时间依赖影响力传播

Time-dependent influence propagation based on time-delayed diffusion model

针对社交网络中的影响力最大化问题进行了研究,建立了一种时间依赖影响力最大化问题,并在该问题中引入了新鲜度函数的概念。为了求解该问题,建立了两个考虑时间延迟的扩散模型,并基于扩散函数的子模性和单调性提出了时间依赖的贪婪算法和时间依赖的启发式方法。前者能够很好地用于计算两种扩散模型中的传播价值并保证解的近似比,后者能够减少求解问题的计算时间成本且与模型无关。通过在真实社交网络数据集上进行的实验结果不仅验证了算法的有效性,而且相比于传统方法,提出的模型和方法可以通过选择有影响力的节点获得更高的扩散价值和更低的运行时间。

A research on influence maximization problem in social networks is implemented in this paper. A time-dependent influence maximization problem is established and the concept of freshness function is introduced into the problem. In order to solve this problem, two diffusion models considering time delay are established, and a time-dependent greedy algorithm and a time-dependent heuristic method are proposed based on the submodularity and monotonicity of the diffusion function. The former can be well used to calculate the propagation value of the two diffusion models and ensure the approximate ratio of the solutions, while the latter can reduce the computational cost of solving the problem and is independent of the model. Experimental results on real social network data sets not only verify the effectiveness of the proposed algorithm, but also, compared with traditional methods, the proposed model and method can obtain higher spread value and lower running time by selecting influential nodes.