基于动态网络影响扩散问题研究

摘要

影响扩散是复杂网络上动态过程研究的关键问题之一,而且基于动态网络的影响扩散问题的相关成果很少.讨论了动态独立级联模型和动态线性阈值模型以及基于这两个模型的动态影响最大化问题,提出了一种改进的贪婪算法,该算法消除了随机模型的不确定性并采用连通图方法来提高算法性能,并在不同规模的4个数据集上进行了验证.实验结果表明,与HT算法相比,提出的算法在影响扩散范围方面具有明显的优势,且在时间效率方面要好于HT算法.%Influence spread is one of key problems about dynamic process problems on complex networks,and the research results of influence maximization problem based on dynamic networks are less. We discussed dynamic independent cascade model and dynamic linear threshold model and proposed a dynamic influence maximization problem based on above two models. Then, we presented an improved greedy algorithm, which eliminates the uncertainty of stochastic models and improves its performance by using connected graph approach. The algorithm was validated on four datasets with different sizes including AS, EMAIL, DELICIOUS and DBLP. The results show that, the size of influence spread of our algorithm has an obvious advantage and time efficiency is better compared with HT algorithm.