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

Research on Influence Maximization Problem Based on Dynamic Networks

作　　者：王学光[1] 

机构地区：[1]华东政法大学信息科学与技术系,上海201620

出　　处：《计算机科学》2012年第6期111-115,共5页Computer Science

基　　金：国家社会科学基金项目(11BFX125)资助

摘　　要：影响扩散是复杂网络上动态过程研究的关键问题之一,而且基于动态网络的影响扩散问题的相关成果很少。讨论了动态独立级联模型和动态线性阈值模型以及基于这两个模型的动态影响最大化问题,提出了一种改进的贪婪算法,该算法消除了随机模型的不确定性并采用连通图方法来提高算法性能,并在不同规模的4个数据集上进行了验证。实验结果表明,与HT算法相比,提出的算法在影响扩散范围方面具有明显的优势,且在时间效率方面要好于HT算法。Influence spread is one of key problems about dynamic process problems on complex networks,and the re- search results of influence maximization problem based on dynamic networks are less. We discussed dynamic independ- ent 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.

关 键 词：动态网络 影响最大化 信息融合模型 启发式算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]