###
工程科学与技术:2019,51(1):181-188
←前一篇   |   后一篇→
本文二维码信息
码上扫一扫!
基于线性阈值模型的动态社交网络影响最大化算法
(黑龙江大学 计算机科学与技术学院, 黑龙江 哈尔滨 150080)
Influence Maximization Algorithm for Dynamic Social Networks Based on Linear Threshold Model
(School of Computer Sci. and Technol., Heilongjiang Univ., Harbin 150080, China)
摘要
图/表
参考文献
相似文献
本文已被:浏览 1680次   下载 1181
投稿时间:2017-09-08    修订日期:2018-07-02
中文摘要: 针对随时间进化的动态社交网络展开影响最大化问题的研究,目标是基于线性阈值传播模型,挖掘影响力最大的k个种子用户,从种子用户发起传播,最大化影响传播范围。提出一种基于线性阈值模型的动态社交网络影响最大化算法(linear threshold dynamic influence maximization,LTDIM)。首先,给出动态社交网络影响最大化问题的形式化定义,提出利用活边路径获取初始种集的方法;然后,分析网络的各种拓扑变化,提出种集的增量式更新方法;最后,基于节点度和影响力增量提出DP(degree pruning)和IIP(influence increment pruning)剪枝策略进一步提高时间效率。实验使用4个真实的社交网络数据,考察在8个网络快照上算法的运行时间和影响传播范围。实验结果表明,本文算法的影响传播范围接近于静态启发式算法,运行时间大幅度减少,验证了算法的时间高效性和可扩展性。"
Abstract: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.
文章编号:201700728     中图分类号:TP311    文献标志码:
基金项目:国家自然科学基金资助项目(61100048;61370222);黑龙江省自然科学基金资助项目(F2016034;F2018028)
作者简介:朱敬华(1976-),女,教授,博士,硕士生导师.研究方向:社会网;数据挖掘;无线传感器网络.E-mail:zhujinghua@hlju.edu.cn
引用文本:
朱敬华,李亚琼,王亚珂,杨艳.基于线性阈值模型的动态社交网络影响最大化算法[J].工程科学与技术,2019,51(1):181-188.
ZHU Jinghua,LI Yaqiong,WANG Yake,YANG Yan.Influence Maximization Algorithm for Dynamic Social Networks Based on Linear Threshold Model[J].Advanced Engineering Sciences,2019,51(1):181-188.