竞争环境中基于主题偏好的利己信息影响力最大化算法
|
摘要
社会计算领域的影响力传播问题一般仅研究单条信息的最大化传播,但在实际网络环境中,更多的是存在多条具有竞争关系的信息在网络中进行传播,且在传播过程中不同信息会相互影响.竞争环境中的影响力最大化问题即是为某一条竞争信息选择种子节点集合,使之最终影响的节点数目最多.该文针对多条相似信息的竞争传播问题,考虑传播的同步性,建立基于竞争的线性阈值扩展模型;基于用户交互的主题偏好计算不同类别信息下节点间的影响概率,并结合扩展的传播模型和信息扩散的特点,提出基于节点子图的影响力计算方法.以两条竞争信息传播为例,考虑利己信息对竞争信息传播策略的掌握情况,设计两种解决方案:(1)在已知竞争信息A的种子节点选择策略时,提出节点避让的利己信息影响最大化算法NA(Node Avoidance);(2)在未知竞争信息A的种子节点选择策略时,提出使用种子节点选择策略集为信息A选择种子集合,并提出策略无关的利己信息影响最大化算法I3SL(Independent Seed Selection Strategy of Leader).该文在新浪实证数据集上进行了对比实验,结果表明:(1)NA算法在竞争环境中能使利己信息传播范围最广,平均优于其他算法26.2%,且表现出较好的通用性和稳定性;(2)I3SL算法在未知竞争信息的选择策略时也能够保证利己信息的传播范围,平均优于其他算法18.23%;(3)该文所提两种算法在运行时间上较其他启发式算法表现较弱,但两种算法在运行时间和传播范围两方面均取得了较好的平衡.
Traditional influence maximization generally involved the situation of one message spread in propagation model.However,in the actual network,multiple competitive messages are spread synchronously,and influence each other alternately.How to choose the initial set of seeds for each competitive message so as to get the max number of influenced nodes in a competitive environment is an NP-hard problem.To solve the problem happened during simultaneous competitive dissemination,our work considers the synchronization of competitive information dissemination,as well as the law that user's influences of different information are not the same.Few researchers analyze the content of competitive information on the influence of competition.But in fact,users' topic preferences and interactive preferences will be mined through their interactive content.So we allow for the topic preference of interaction between users,then take the advantage of topic model to get the probability between users in the different kinds of information,respectively.Based on that,we define the competition-based linear threshold model to fit the characteristic of information dissemination in this simultaneous competitive dissemination,and followed by the method proposed to calculate the node's influence based on node subgraph.To take an example from the dissemination of two competitive information,we take the mastery of competitors' dissemination strategies into account,and provide two solutions:(1)The Node Avoidance Influence Maximization Algorithm(NA)suppose the competitors' dissemination strategies are known to each other,which would avoid selecting nodes that can maximize the competitors' information diffusion.(2)The Independent Seed Selection Strategy of Leader Influence Maximization Algorithm(I3 SL)we proposed provides a novel solution for the case that the competitors' dissemination strategies are unknown.Experiments are carried out to verify the effectiveness of algorithms on real Weibo data set,and the results under the competition based on linear threshold model show that:(1)In the competitive environment,NA algorithm is superior to the traditional heuristic algorithms in the scope of influence,averaging 26.2% better than other algorithms,with a good performance in universality and stability;(2)The I3 SL algorithm can also guarantee the scope of influence when the selection strategy of competitive information is unknown,averaging 18.23% better than other algorithms.(3)As for the running time,our two algorithms are inferior to the heuristic algorithm,but they still have a better balance between efficiency and scope of influence.
Traditional influence maximization generally involved the situation of one message spread in propagation model.However,in the actual network,multiple competitive messages are spread synchronously,and influence each other alternately.How to choose the initial set of seeds for each competitive message so as to get the max number of influenced nodes in a competitive environment is an NP-hard problem.To solve the problem happened during simultaneous competitive dissemination,our work considers the synchronization of competitive information dissemination,as well as the law that user's influences of different information are not the same.Few researchers analyze the content of competitive information on the influence of competition.But in fact,users' topic preferences and interactive preferences will be mined through their interactive content.So we allow for the topic preference of interaction between users,then take the advantage of topic model to get the probability between users in the different kinds of information,respectively.Based on that,we define the competition-based linear threshold model to fit the characteristic of information dissemination in this simultaneous competitive dissemination,and followed by the method proposed to calculate the node's influence based on node subgraph.To take an example from the dissemination of two competitive information,we take the mastery of competitors' dissemination strategies into account,and provide two solutions:(1)The Node Avoidance Influence Maximization Algorithm(NA)suppose the competitors' dissemination strategies are known to each other,which would avoid selecting nodes that can maximize the competitors' information diffusion.(2)The Independent Seed Selection Strategy of Leader Influence Maximization Algorithm(I3 SL)we proposed provides a novel solution for the case that the competitors' dissemination strategies are unknown.Experiments are carried out to verify the effectiveness of algorithms on real Weibo data set,and the results under the competition based on linear threshold model show that:(1)In the competitive environment,NA algorithm is superior to the traditional heuristic algorithms in the scope of influence,averaging 26.2% better than other algorithms,with a good performance in universality and stability;(2)The I3 SL algorithm can also guarantee the scope of influence when the selection strategy of competitive information is unknown,averaging 18.23% better than other algorithms.(3)As for the running time,our two algorithms are inferior to the heuristic algorithm,but they still have a better balance between efficiency and scope of influence.
引文
[1]Domingos P,Richardson M.Mining the network value of customers//Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.San Francisco,USA,2001:57-66
[2]Kempe D,Kleinberg J,Tardos.Maximizing the spread of influence through a social network//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Washington,USA,2003:137-146
[3]Cao Jiu-Xin,Dong Dan,Xu Shun,et al.A k-core based algorithm for influence maximization in social networks.Chinese Journal of Computers,2015,38(2):238-248(in Chinese)(曹玖新,董丹,徐顺等.一种基于k-核的社会网络影响最大化算法.计算机学报,2015,38(2):238-248)
[4]Li Yue-Zhi,Zhu Yuan-Yuan,Zhong Ming,et al.k-core filtered influence maximization algorithms in social networks.Journal of Computer Applications,2018,38(2):464-470(in Chinese)(李阅志,祝园园,钟鸣.基于k-核过滤的社交网络影响最大化算法.计算机应用,2018,38(2):464-470)
[5]Ma Qian,Ma Jun.Discovering the substitutes for the seeds in influence maximization problems.Chinese Journal of Computers,2017,40(3):674-686(in Chinese)(马茜,马军.在影响力最大化问题中寻找种子节点的替补节点.计算机学报,2017,40(3):674-686)
[6]Chen W,Wang Y,Yang S.Efficient influence maximization in social networks//Proceedings of the 15th ACM SIGKDDInternational Conference on Knowledge Discovery and Data Mining.Paris,France,2009:199-208
[7]Chen W,Wang C,Wang Y.Scalable influence maximization for prevalent viral marketing in large-scale social networks//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Washington,USA,2010:1029-1038
[8]Wang Rui,Liu Yong,Zhu Jing-Hua,et al.Social network information diffusion model based on user’s influence and interesting.Journal on Communications,2017,38(s2):113-121(in Chinese)(王瑞,刘勇,朱敬华等.基于用户影响与兴趣的社交网信息传播模型.通信学报,2017,38(s2):113-121)
[9]Xie Sheng-Nan,Liu Yong,Zhu Jing-Hua,et al.Research on topic-based local influence maximization algorithm in social network.Journal of Frontiers of Computer Science&Technology,2016,10(5):646-656(in Chinese)(谢胜男,刘勇,朱敬华等.社会网中基于主题的局部影响最大化算法研究.计算机科学与探索,2016,10(5):646-656)
[10]Wang Q,Jin Y,Lin Z,et al.Influence maximization in social networks under an independent cascade-based model.Physica A:Statistical Mechanics and Its Applications,2016,444:20-34
[11]Chen W,Yuan Y,Zhang L.Scalable influence maximization in social networks under the linear threshold model//Proceedings of the IEEE International Conference on Data Mining.Sydney,Australia,2010:88-97
[12]Bharathi S,Kempe D,Salek M.Competitive influence maximization in social networks//Proceedings of the International Workshop on Web and Internet Economics.Berlin,Germany,2007:306-311
[13]Grossman D A,Frieder O.Information Retrieval:Algorithms and Heuristics.Berlin,Germany:Springer,2012
[14]Bozorgi A,Samet S,Kwisthout J,et al.Community-based influence maximization in social networks under a competitive linear threshold model.Knowledge-Based Systems,2017,134:149-158
[15]Borodin A,Filmus Y,Oren J.Threshold models for competitive influence in social networks//Proceedings of the International Workshop on Internet and Network Economics.Berlin,Germany,2010:539-550
[16]Carnes T,Nagarajan C,Wild S M,et al.Maximizing influence in a competitive social network:A follower’s perspective//Proceedings of the International Conference on Electronic Commerce.Minneapolis,USA,2007:351-360
[17]Budak C,Agrawal D,El Abbadi A.Limiting the spread of misinformation in social networks.Games&Economic Behavior,2010,70(2):194-227
[18]Zhou W,Jia W,Haghighi M,et al.A sword with two edges:Propagation studies on both positive and negative information in online social networks.IEEE Transactions on Computers,2015,64(3):640-653
[19]Lim Y,Ozdaglar A,Teytelboym A.Competitive rumor spread in social networks.ACM SIGMETRICS Performance Evaluation Review,2017,44(3):7-14
[20]Zhu Y,Li D,Zhang Z.Minimum cost seed set for competitive social influence//Proceedings of the IEEE INFOCOM 2016the IEEE International Conference on Computer Communications.San Francisco,USA,2016:1-9
[21]Liu W,Yue K,Wu H,et al.Containment of competitive influence spread in social networks.Knowledge-Based Systems,2016,109(C):266-275
[22]Ribeiro B,Faloutsos C.Modeling website popularity competition in the attention-activity marketplace//Proceedings of the 8th ACM International Conference on Web Search and Data Mining.Shanghai,China,2015:389-398
[23]Narayanam R,Nanavati A.Viral marketing for product cross-sell through social networks.Machine Learning and Knowledge Discovery in Databases.Berlin,Germany:Springer,2012:581-596
[24]Zhang J,Wang S,Zhan Q,et al.Intertwined viral marketing in social networks//Proceedings of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining.Piscataway,USA,2016:239-246
[25]Wu H,Liu W,Yue K,et al.Selecting Seeds for Competitive Influence Spread Maximization in Social Networks.Social Computing.Singapore:Springer,2016
[26]Beutel A,Prakash B A,Rosenfeld R,et al.Interacting viruses in networks:Can both survive?//Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Beijing,China,2012:426-434
[27]He X,Song G,Chen W,et al.Influence blocking maximization in social networks under the competitive linear threshold model//Proceedings of the 2012SIAM International Conference on Data Mining.Society for Industrial and Applied Mathematics,California,USA,2012:463-474
[28]Tang J,Sun J,Wang C,et al.Social influence analysis in large-scale networks//Proceedings of the 15th ACM SIGKDDInternational Conference on Knowledge Discovery and Data Mining.Paris,France,2009:807-815
[29]Tzoumas V,Amanatidis C,Markakis E.A game-theoretic analysis of a competitive diffusion process over social networks.Internet and Network Economics.Berlin,Germany:Springer,2012:1-14
[30]Barbieri N,Bonchi F,Manco G.Topic-aware social influence propagation models.Knowledge and Information Systems,2013,37(3):555-584
[31]Chen W,Lin T,Yang C.Efficient topic-aware influence maximization using preprocessing.The Computing Research Repository,2014,9197:1-13
[32]Watts D J.A simple model of global cascades on random networks.Proceedings of the National Academy of Sciences,2002,99(9):5766-5771
[33]Granovetter M.Threshold models of collective behavior.American Journal of Sociology,1978,83(6):1420-1443
[34]Diao S M,Liu Y,Zeng Q A.Empirical analysis of relationshipbased user reposting behavior on microblog network.International Journal of Interdisciplinary Telecommunications and Networking,2015,7(3):1-12
[35]Blei D M,Ng A Y,Jordan M I.Latent dirichlet allocation.Journal of Machine Learning Research,2003,3:993-1022
[36]Christakis N A,Fowler J H.Social contagion theory:Examining dynamic social networks and human behavior.Statistics in Medicine,2013,32(4):556
[37]Arney C.Connected:The surprising power of our social networks and how they shape our lives-How your friends’friends’friends affect everything you feel,think,and do.Mathematics and Computer Education,2014,48(2):201
[2]Kempe D,Kleinberg J,Tardos.Maximizing the spread of influence through a social network//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Washington,USA,2003:137-146
[3]Cao Jiu-Xin,Dong Dan,Xu Shun,et al.A k-core based algorithm for influence maximization in social networks.Chinese Journal of Computers,2015,38(2):238-248(in Chinese)(曹玖新,董丹,徐顺等.一种基于k-核的社会网络影响最大化算法.计算机学报,2015,38(2):238-248)
[4]Li Yue-Zhi,Zhu Yuan-Yuan,Zhong Ming,et al.k-core filtered influence maximization algorithms in social networks.Journal of Computer Applications,2018,38(2):464-470(in Chinese)(李阅志,祝园园,钟鸣.基于k-核过滤的社交网络影响最大化算法.计算机应用,2018,38(2):464-470)
[5]Ma Qian,Ma Jun.Discovering the substitutes for the seeds in influence maximization problems.Chinese Journal of Computers,2017,40(3):674-686(in Chinese)(马茜,马军.在影响力最大化问题中寻找种子节点的替补节点.计算机学报,2017,40(3):674-686)
[6]Chen W,Wang Y,Yang S.Efficient influence maximization in social networks//Proceedings of the 15th ACM SIGKDDInternational Conference on Knowledge Discovery and Data Mining.Paris,France,2009:199-208
[7]Chen W,Wang C,Wang Y.Scalable influence maximization for prevalent viral marketing in large-scale social networks//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Washington,USA,2010:1029-1038
[8]Wang Rui,Liu Yong,Zhu Jing-Hua,et al.Social network information diffusion model based on user’s influence and interesting.Journal on Communications,2017,38(s2):113-121(in Chinese)(王瑞,刘勇,朱敬华等.基于用户影响与兴趣的社交网信息传播模型.通信学报,2017,38(s2):113-121)
[9]Xie Sheng-Nan,Liu Yong,Zhu Jing-Hua,et al.Research on topic-based local influence maximization algorithm in social network.Journal of Frontiers of Computer Science&Technology,2016,10(5):646-656(in Chinese)(谢胜男,刘勇,朱敬华等.社会网中基于主题的局部影响最大化算法研究.计算机科学与探索,2016,10(5):646-656)
[10]Wang Q,Jin Y,Lin Z,et al.Influence maximization in social networks under an independent cascade-based model.Physica A:Statistical Mechanics and Its Applications,2016,444:20-34
[11]Chen W,Yuan Y,Zhang L.Scalable influence maximization in social networks under the linear threshold model//Proceedings of the IEEE International Conference on Data Mining.Sydney,Australia,2010:88-97
[12]Bharathi S,Kempe D,Salek M.Competitive influence maximization in social networks//Proceedings of the International Workshop on Web and Internet Economics.Berlin,Germany,2007:306-311
[13]Grossman D A,Frieder O.Information Retrieval:Algorithms and Heuristics.Berlin,Germany:Springer,2012
[14]Bozorgi A,Samet S,Kwisthout J,et al.Community-based influence maximization in social networks under a competitive linear threshold model.Knowledge-Based Systems,2017,134:149-158
[15]Borodin A,Filmus Y,Oren J.Threshold models for competitive influence in social networks//Proceedings of the International Workshop on Internet and Network Economics.Berlin,Germany,2010:539-550
[16]Carnes T,Nagarajan C,Wild S M,et al.Maximizing influence in a competitive social network:A follower’s perspective//Proceedings of the International Conference on Electronic Commerce.Minneapolis,USA,2007:351-360
[17]Budak C,Agrawal D,El Abbadi A.Limiting the spread of misinformation in social networks.Games&Economic Behavior,2010,70(2):194-227
[18]Zhou W,Jia W,Haghighi M,et al.A sword with two edges:Propagation studies on both positive and negative information in online social networks.IEEE Transactions on Computers,2015,64(3):640-653
[19]Lim Y,Ozdaglar A,Teytelboym A.Competitive rumor spread in social networks.ACM SIGMETRICS Performance Evaluation Review,2017,44(3):7-14
[20]Zhu Y,Li D,Zhang Z.Minimum cost seed set for competitive social influence//Proceedings of the IEEE INFOCOM 2016the IEEE International Conference on Computer Communications.San Francisco,USA,2016:1-9
[21]Liu W,Yue K,Wu H,et al.Containment of competitive influence spread in social networks.Knowledge-Based Systems,2016,109(C):266-275
[22]Ribeiro B,Faloutsos C.Modeling website popularity competition in the attention-activity marketplace//Proceedings of the 8th ACM International Conference on Web Search and Data Mining.Shanghai,China,2015:389-398
[23]Narayanam R,Nanavati A.Viral marketing for product cross-sell through social networks.Machine Learning and Knowledge Discovery in Databases.Berlin,Germany:Springer,2012:581-596
[24]Zhang J,Wang S,Zhan Q,et al.Intertwined viral marketing in social networks//Proceedings of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining.Piscataway,USA,2016:239-246
[25]Wu H,Liu W,Yue K,et al.Selecting Seeds for Competitive Influence Spread Maximization in Social Networks.Social Computing.Singapore:Springer,2016
[26]Beutel A,Prakash B A,Rosenfeld R,et al.Interacting viruses in networks:Can both survive?//Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Beijing,China,2012:426-434
[27]He X,Song G,Chen W,et al.Influence blocking maximization in social networks under the competitive linear threshold model//Proceedings of the 2012SIAM International Conference on Data Mining.Society for Industrial and Applied Mathematics,California,USA,2012:463-474
[28]Tang J,Sun J,Wang C,et al.Social influence analysis in large-scale networks//Proceedings of the 15th ACM SIGKDDInternational Conference on Knowledge Discovery and Data Mining.Paris,France,2009:807-815
[29]Tzoumas V,Amanatidis C,Markakis E.A game-theoretic analysis of a competitive diffusion process over social networks.Internet and Network Economics.Berlin,Germany:Springer,2012:1-14
[30]Barbieri N,Bonchi F,Manco G.Topic-aware social influence propagation models.Knowledge and Information Systems,2013,37(3):555-584
[31]Chen W,Lin T,Yang C.Efficient topic-aware influence maximization using preprocessing.The Computing Research Repository,2014,9197:1-13
[32]Watts D J.A simple model of global cascades on random networks.Proceedings of the National Academy of Sciences,2002,99(9):5766-5771
[33]Granovetter M.Threshold models of collective behavior.American Journal of Sociology,1978,83(6):1420-1443
[34]Diao S M,Liu Y,Zeng Q A.Empirical analysis of relationshipbased user reposting behavior on microblog network.International Journal of Interdisciplinary Telecommunications and Networking,2015,7(3):1-12
[35]Blei D M,Ng A Y,Jordan M I.Latent dirichlet allocation.Journal of Machine Learning Research,2003,3:993-1022
[36]Christakis N A,Fowler J H.Social contagion theory:Examining dynamic social networks and human behavior.Statistics in Medicine,2013,32(4):556
[37]Arney C.Connected:The surprising power of our social networks and how they shape our lives-How your friends’friends’friends affect everything you feel,think,and do.Mathematics and Computer Education,2014,48(2):201