基于线性阈值模型的动态社交网络影响最大化算法

针对随时间进化的动态社交网络展开影响最大化问题的研究,目标是基于线性阈值传播模型,挖掘影响力最大的k个种子用户,从种子用户发起传播,最大化影响传播范围。提出一种基于线性阈值模型的动态社交网络影响最大化算法（linear threshold dynamic influence maximization,LTDIM）。首先,给出动态社交网络影响最大化问题的形式化定义,提出利用活边路径获取初始种集的方法;然后,分析网络的各种拓扑变化,提出种集的增量式更新方法;最后,基于节点度和影响力增量提出DP（degree pruning）和IIP（influence increment pruning）剪枝策略进一步提高时间效率。实验使用4个真实的社交网络数据,考察在8个网络快照上算法的运行时间和影响传播范围。实验结果表明,本文算法的影响传播范围接近于静态启发式算法,运行时间大幅度减少,验证了算法的时间高效性和可扩展性。"

Influence Maximization Algorithm for Dynamic Social Networks Based on Linear Threshold Model

In order to solve the influence maximization problem in evolving social network, a dynamic influence maximization algorithm based on the linear threshold model was proposed in this paper. The goal of influence maximization was to mine out the top k most influential seed users and maximize the spread of influence through them. An algorithm called LTDIM was proposed based on the linear threshold model. Specially, firstly, the formal definition of dynamic influence maximization problem was given and the initial seeding method based on alive edge path was proposed. Then, according to the analysis of various network topology changes, an incremental seeds updating algorithm was presented. Finally, to further improve the time efficiency, two pruning strategies DP (degree pruning) and IIP (influence increment pruning) based on nodes degree and influence increment were devised. Experiments on the eight network snapshots of four real social networks evaluated the algorithm performance in terms of running time and influence spread. Experimental results demonstrated that compared with the state-of-the-art static heuristic algorithms, the algorithms proposed in the paper can achieve a great deal of speedup in running time while maintaining matching performance in terms of influence spread.