基于线性阈值模型的动态社交网络影响最大化算法
Influence Maximization Algorithm for Dynamic Social Networks Based on Linear Threshold Model
作者：朱敬华(黑龙江大学 计算机科学与技术学院, 黑龙江 哈尔滨 150080)；李亚琼(黑龙江大学 计算机科学与技术学院, 黑龙江 哈尔滨 150080)；王亚珂(黑龙江大学 计算机科学与技术学院, 黑龙江 哈尔滨 150080)；杨艳(黑龙江大学 计算机科学与技术学院, 黑龙江 哈尔滨 150080)
Author：ZHU Jinghua(School of Computer Sci. and Technol., Heilongjiang Univ., Harbin 150080, China)；LI Yaqiong(School of Computer Sci. and Technol., Heilongjiang Univ., Harbin 150080, China)；WANG Yake(School of Computer Sci. and Technol., Heilongjiang Univ., Harbin 150080, China)；YANG Yan(School of Computer Sci. and Technol., Heilongjiang Univ., Harbin 150080, China)
收稿日期：2017-09-08 年卷（期）页码：2019,51(1):181-188
期刊名称：工程科学与技术
Journal Name：Advanced Engineering Sciences
关键字：动态社会网;影响最大化;线性阈值模型;剪枝策略
Key words：dynamic social networks;influence maximization;linear threshold model;pruning strategy
基金项目：国家自然科学基金资助项目（61100048；61370222）；黑龙江省自然科学基金资助项目（F2016034；F2018028）
中文摘要
针对随时间进化的动态社交网络展开影响最大化问题的研究，目标是基于线性阈值传播模型，挖掘影响力最大的k个种子用户，从种子用户发起传播，最大化影响传播范围。提出一种基于线性阈值模型的动态社交网络影响最大化算法（linear threshold dynamic influence maximization，LTDIM）。首先，给出动态社交网络影响最大化问题的形式化定义，提出利用活边路径获取初始种集的方法；然后，分析网络的各种拓扑变化，提出种集的增量式更新方法；最后，基于节点度和影响力增量提出DP（degree pruning）和IIP（influence increment pruning）剪枝策略进一步提高时间效率。实验使用4个真实的社交网络数据，考察在8个网络快照上算法的运行时间和影响传播范围。实验结果表明，本文算法的影响传播范围接近于静态启发式算法，运行时间大幅度减少，验证了算法的时间高效性和可扩展性。"
英文摘要
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 topkmost 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.
【关闭】
