基于线性阈值模型的动态社交网络影响最大化算法
|
摘要
针对随时间进化的动态社交网络展开影响最大化问题的研究,目标是基于线性阈值传播模型,挖掘影响力最大的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.
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.
引文
[1]Zhou Shengfu,Yue Kun,Fang Qiyun,et al.An efficient algorithm for influence maximization under linear threshold model[C]//Proceedings of the 26th Control and Decision Conference.Changsha:IEEE,2014:5352-5357.
[2]Guo Jing,Zhang Peng,Fang Binxing.Personalized key propagating users mining based on LT model[J].Chinese Journal of Computers,2014,37(4):809-818.[郭静,张鹏,方滨兴,等.基于LT模型的个性化关键传播用户挖掘[J].计算机学报,2014,37(4):809-818.]
[3]Kempe D,Kleinberg J,Tardosé.Maximizing the spread of influence through a social network[C]//Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.NewYork:ACM,2003:137-146.
[4]Chen Wei,Yuan Yifei,Zhang Li.Scalable influence maximization in social networks under the linear threshold model[C]//Proceedings of the 2010 IEEE International Conference on Data Mining.Sydney:IEEE,2011:88-97.
[5]Goyal A,Lu Wei,Lakshmanan L V S.SIMPATH:An efficient algorithm for influence maximization under the linear threshold model[C]//Proceedings of the 2011 IEEE 11th International Conference on Data Mining.Vancouver:IEEE,2012:211-220.
[6]Zhu Jinghua,Yin Xuming,Wang Yake,et al.Structural holes theory-based influence maximization in social network[M]//Wireless Algorithms,Systems,and Applications.Cham:Springer,2017:860-864.
[7]Gayraud N T H,Pitoura E,Tsaparas P.Diffusion maximization in evolving social networks[C]//Proceedings of the2015 ACM on Conference on Online Social Networks.New York:ACM,2015:125-135.
[8]Zhuang Honglei,Sun Yihan,Tang Jie,et al.Influence maximization in dynamic social networks[C]//Proceedings of the 2013 IEEE 13th International Conference on Data Mining.Shenzhen:IEEE,2014:1313-1318.
[9]Tong Guangmo,Wu Weili,Tang Shaojie,et al.Adaptive influence maximization in dynamic social networks[J].IEEE/ACM Transactions on Networking,2015,25(1):112-125.
[10]Liu Xiaodong,Liao Xiangke,Li Shanshan,et al.On the shoulders of giants:Incremental influence maximization in evolving social networks[J/OL].Complexity,2017[2017-08-01].http://dx.doi.org/10.1155/2017/5049836.
[11]Bao Yixin,Wang Xiaoke,Wang Zhi,et al.Online influence maximization in non-stationary social networks[C]//Proceedings of the 2016 IEEE/ACM 24th International Symposium on Quality of Service.Beijing:IEEE,2016:1-6.
[2]Guo Jing,Zhang Peng,Fang Binxing.Personalized key propagating users mining based on LT model[J].Chinese Journal of Computers,2014,37(4):809-818.[郭静,张鹏,方滨兴,等.基于LT模型的个性化关键传播用户挖掘[J].计算机学报,2014,37(4):809-818.]
[3]Kempe D,Kleinberg J,Tardosé.Maximizing the spread of influence through a social network[C]//Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.NewYork:ACM,2003:137-146.
[4]Chen Wei,Yuan Yifei,Zhang Li.Scalable influence maximization in social networks under the linear threshold model[C]//Proceedings of the 2010 IEEE International Conference on Data Mining.Sydney:IEEE,2011:88-97.
[5]Goyal A,Lu Wei,Lakshmanan L V S.SIMPATH:An efficient algorithm for influence maximization under the linear threshold model[C]//Proceedings of the 2011 IEEE 11th International Conference on Data Mining.Vancouver:IEEE,2012:211-220.
[6]Zhu Jinghua,Yin Xuming,Wang Yake,et al.Structural holes theory-based influence maximization in social network[M]//Wireless Algorithms,Systems,and Applications.Cham:Springer,2017:860-864.
[7]Gayraud N T H,Pitoura E,Tsaparas P.Diffusion maximization in evolving social networks[C]//Proceedings of the2015 ACM on Conference on Online Social Networks.New York:ACM,2015:125-135.
[8]Zhuang Honglei,Sun Yihan,Tang Jie,et al.Influence maximization in dynamic social networks[C]//Proceedings of the 2013 IEEE 13th International Conference on Data Mining.Shenzhen:IEEE,2014:1313-1318.
[9]Tong Guangmo,Wu Weili,Tang Shaojie,et al.Adaptive influence maximization in dynamic social networks[J].IEEE/ACM Transactions on Networking,2015,25(1):112-125.
[10]Liu Xiaodong,Liao Xiangke,Li Shanshan,et al.On the shoulders of giants:Incremental influence maximization in evolving social networks[J/OL].Complexity,2017[2017-08-01].http://dx.doi.org/10.1155/2017/5049836.
[11]Bao Yixin,Wang Xiaoke,Wang Zhi,et al.Online influence maximization in non-stationary social networks[C]//Proceedings of the 2016 IEEE/ACM 24th International Symposium on Quality of Service.Beijing:IEEE,2016:1-6.