摘要
针对随时间进化的动态社交网络展开影响最大化问题的研究,目标是基于线性阈值传播模型,挖掘影响力最大的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 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.
作者
朱敬华
李亚琼
王亚珂
杨艳
ZHU Jinghua;LI Yaqiong;WANG Yake;YANG Yan(School of Computer Sci.and Technol.,Heilongjiang Univ.,Harbin 150080,China)
出处
《工程科学与技术》
EI
CAS
CSCD
北大核心
2019年第1期181-188,共8页
Advanced Engineering Sciences
基金
国家自然科学基金资助项目(61100048
61370222)
黑龙江省自然科学基金资助项目(F2016034
F2018028)
关键词
动态社会网
影响最大化
线性阈值模型
剪枝策略
dynamic social networks
influence maximization
linear threshold model
pruning strategy
