面向不确定性影响源的社会网络影响力传播抑制方法
|
摘要
社会网络中影响力传播的有效抑制是社会网络影响力传播机制研究所关注的问题之一。该文针对未知影响传播源,或传播源信息具有不确定性的情况,提出面向不确定性影响源的影响力传播抑制问题。首先,为有效提高抑制算法的执行效率,讨论竞争线性阈值传播模型下影响源传播能力的近似估计方法,进而提出有限影响源情况下,期望抑制效果最大化的抑制种子集挖掘算法。其次,对于大尺寸不确定性影响源的情况,考虑算法运行效率和抑制效果之间的有效折中,提出基于抽样平均近似的期望抑制效果最大化的抑制种子集挖掘算法。最后,在真实的社会网络数据集上,通过实验测试验证了所提出方法的有效性。
Influence blocking maximization is currently a focused issue in the research area of social networks. This paper considers the issue of influence blocking maximization with uncertain negative influence sources. First, in order to increase efficiency of blocking seeds mining algorithms, the approximate estimation method of influence propagation of negative seeds under the competitive linear threshold model is discussed. Based on the estimation, a blocking seeds mining algorithm for finite uncertain negatively influence sources is proposed to maximize expected influence blocking utility. Second, for the case of huge amount of negatively influence sources with uncertainty, a blocking seeds mining algorithm based on the sampling average approximation approach is proposed to balance the tradeoffs between scalability and effectiveness of the influence blocking maximization. Finally, experiments are carried on real data sets of social networks to verify the feasibility and scalability of the proposed algorithms.
Influence blocking maximization is currently a focused issue in the research area of social networks. This paper considers the issue of influence blocking maximization with uncertain negative influence sources. First, in order to increase efficiency of blocking seeds mining algorithms, the approximate estimation method of influence propagation of negative seeds under the competitive linear threshold model is discussed. Based on the estimation, a blocking seeds mining algorithm for finite uncertain negatively influence sources is proposed to maximize expected influence blocking utility. Second, for the case of huge amount of negatively influence sources with uncertainty, a blocking seeds mining algorithm based on the sampling average approximation approach is proposed to balance the tradeoffs between scalability and effectiveness of the influence blocking maximization. Finally, experiments are carried on real data sets of social networks to verify the feasibility and scalability of the proposed algorithms.
引文
[1]吴信东,李毅,李磊.在线社交网络影响力分析[J].计算机学报,2014,37(4):735-752.doi:10.3724/SP.J.1016.2014.00735.WU Xingdong,LI Yi,and LI Lei.Influence analysis of online social networks[J].Chinese Journal of Computers,2014,37(4):735-752.doi:10.3724/SP.J.1016.2014.00735.
[2]刘业政,李玲菲,姜元春.社会化营销绩效最大化问题及其扩展研究综述[J].电子与信息学报,2016,38(9):2130-2140.doi:10.11999/JEIT160517.LIU Yezheng,LI Lingfei,and JIANG Yuanchun.Review of social marketing performance maximization problem and its extension[J].Journal of Electronics&Information Technology,2016,38(9):2130-2140.doi:10.11999/JEIT160517.
[3]KEMPE D,KLEINBERG J,and 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,New York,2003:137-146.doi:10.1145/956750.956769.
[4]LESKOVEC J,KRAUSE A,GUESTRIN C,et al.Costeffective outbreak detection in networks[C].Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,New York,2007:420-429.doi:10.1145/1281192.1281239.
[5]CHEN Wei,WANG Chi,and WANG Yajun.Scalable influence maximization for prevalent viral marketing in large-scale social networks[C].Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,New York,2010:1029-1038.doi:10.1145/1835804.1835934.
[6]LU Wei,CHEN Wei,and LAKSHMANAN L V S.From competition to complementarity:Comparative influence diffusion and maximization[J].Proceedings of the VLDB Endowment,2015,9(2):60-71.doi:10.14778/2850578.2850581.
[7]SONG Guojie,ZHOU Xiabing,WANG Yu,et al.Influence maximization on large-scale mobile social network:A divideand-conquer method[J].IEEE Transactions on Parallel and Distributed Systems,2015,26(5):1379-1392.doi:10.1109/TPDS.2014.2320515.
[8]许宇光,潘惊治,谢惠扬.基于最小点覆盖和反馈点集的社交网络影响最大化算法[J].电子与信息学报,2016,38(4):795-802.doi:10.11999/JEIT160019.XU Yuguang,PAN Jingzhi,and XIE Huiyang.Minimum vertex covering and feedback vertex set-based algorithm for influence maximization in social network[J].Journal of Electronics&Information Technology,2016,38(4):795-802.doi:10.11999/JEIT160019.
[9]HE Xinran,SONG Guojie,CHEN Wei,et al.Influence blocking maximization in social networks under the competitive linear threshold model[C].9th VLDB Workshop on Secure Data Management,Istanbul,2012:463-474.doi:10.1137/1.9781611972825.40.
[10]NGUYEN N P,YAN G,THAI M T,et al.Containment of misinformation spread in online social networks[C]Proceedings of the 3rd Annual ACM Web Science Conference,Evanston,Illinois,2012:213-222.doi:10.1145/2380718.2380746.
[11]BUDAK C,AGRAWAL D,and EL ABBADI A.Limiting the spread of misinformation in social networks[C]Proceedings of the 20th International Conference on World Wide Web,Hyderabad,India,2011:665-674.doi:10.1145/1963405.1963499.
[12]TSAI J,NGUYEN T H,WELLER N,et al.Game-theoretic target selection in contagion-based domains[J].The Computer Journal,2014,57(6):893-905.doi:10.1093/comjnl/bxt094.
[13]WU Hong,LIU Weiyi,YUE Kun,et al.Maximizing the spread of competitive influence in a social network oriented to viral marketing[C].Proceedings of the 16th International Conference Web-Age Information Management,Qingdao,China,2015:516-519.doi:10.1007/978-3-319-21042-1_53.
[14]LIU Weiyi,YUE Kun,WU Hong,et al.Containment of competitive influence spread in social networks[J].Knowledge-Based Systems,2016,109:266-275.doi:10.1016/j.knosys.2016.07.008.
[15]李劲,岳昆,张德海,等.社会网络中影响力传播的鲁棒抑制方法[J].计算机研究与发展,2016,53(3):601-610.doi:10.7544/issn1000-1239.2016.20148341.LI Jin,YUE Kun,ZHANG Dehai,et al.Robust influence blocking maximization in social networks[J].Journal of Computer Research and Development,2016,53(3):601-610.doi:10.7544/issn1000-1239.2016.20148341.
[16]KLEYWEGT A,SHAPRIO A,and HOMEM-DE-MELLO T.The sample average approximation method for stochastic discrete optimization[J].SIAM Journal on Optimization,2002,12(2):479-502.doi:10.1137/S1052623499363220.
[17]FUJISHIGE S.Submodular Functions and Optimization[M].Amsterdam,Elsevier Science Press,2005,Chapter 3.
[18]SHAPRIO A,DENTCHEVA D,and RUSZCZYNSKI A.Lectures on Stochastic Programming:Modeling and Theory[M].SIAM:Society for Industrial and Applied Mathematics,Philadelphia,PA,USA,SIAM Press,2014,Chapter 1.
1)Twitter,Wiki-Vote下载自:http://snap.stanford.edu/,Net PHY下载自http://research.microsoft.com/en-us/people/weic/projects.aspx
[2]刘业政,李玲菲,姜元春.社会化营销绩效最大化问题及其扩展研究综述[J].电子与信息学报,2016,38(9):2130-2140.doi:10.11999/JEIT160517.LIU Yezheng,LI Lingfei,and JIANG Yuanchun.Review of social marketing performance maximization problem and its extension[J].Journal of Electronics&Information Technology,2016,38(9):2130-2140.doi:10.11999/JEIT160517.
[3]KEMPE D,KLEINBERG J,and 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,New York,2003:137-146.doi:10.1145/956750.956769.
[4]LESKOVEC J,KRAUSE A,GUESTRIN C,et al.Costeffective outbreak detection in networks[C].Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,New York,2007:420-429.doi:10.1145/1281192.1281239.
[5]CHEN Wei,WANG Chi,and WANG Yajun.Scalable influence maximization for prevalent viral marketing in large-scale social networks[C].Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,New York,2010:1029-1038.doi:10.1145/1835804.1835934.
[6]LU Wei,CHEN Wei,and LAKSHMANAN L V S.From competition to complementarity:Comparative influence diffusion and maximization[J].Proceedings of the VLDB Endowment,2015,9(2):60-71.doi:10.14778/2850578.2850581.
[7]SONG Guojie,ZHOU Xiabing,WANG Yu,et al.Influence maximization on large-scale mobile social network:A divideand-conquer method[J].IEEE Transactions on Parallel and Distributed Systems,2015,26(5):1379-1392.doi:10.1109/TPDS.2014.2320515.
[8]许宇光,潘惊治,谢惠扬.基于最小点覆盖和反馈点集的社交网络影响最大化算法[J].电子与信息学报,2016,38(4):795-802.doi:10.11999/JEIT160019.XU Yuguang,PAN Jingzhi,and XIE Huiyang.Minimum vertex covering and feedback vertex set-based algorithm for influence maximization in social network[J].Journal of Electronics&Information Technology,2016,38(4):795-802.doi:10.11999/JEIT160019.
[9]HE Xinran,SONG Guojie,CHEN Wei,et al.Influence blocking maximization in social networks under the competitive linear threshold model[C].9th VLDB Workshop on Secure Data Management,Istanbul,2012:463-474.doi:10.1137/1.9781611972825.40.
[10]NGUYEN N P,YAN G,THAI M T,et al.Containment of misinformation spread in online social networks[C]Proceedings of the 3rd Annual ACM Web Science Conference,Evanston,Illinois,2012:213-222.doi:10.1145/2380718.2380746.
[11]BUDAK C,AGRAWAL D,and EL ABBADI A.Limiting the spread of misinformation in social networks[C]Proceedings of the 20th International Conference on World Wide Web,Hyderabad,India,2011:665-674.doi:10.1145/1963405.1963499.
[12]TSAI J,NGUYEN T H,WELLER N,et al.Game-theoretic target selection in contagion-based domains[J].The Computer Journal,2014,57(6):893-905.doi:10.1093/comjnl/bxt094.
[13]WU Hong,LIU Weiyi,YUE Kun,et al.Maximizing the spread of competitive influence in a social network oriented to viral marketing[C].Proceedings of the 16th International Conference Web-Age Information Management,Qingdao,China,2015:516-519.doi:10.1007/978-3-319-21042-1_53.
[14]LIU Weiyi,YUE Kun,WU Hong,et al.Containment of competitive influence spread in social networks[J].Knowledge-Based Systems,2016,109:266-275.doi:10.1016/j.knosys.2016.07.008.
[15]李劲,岳昆,张德海,等.社会网络中影响力传播的鲁棒抑制方法[J].计算机研究与发展,2016,53(3):601-610.doi:10.7544/issn1000-1239.2016.20148341.LI Jin,YUE Kun,ZHANG Dehai,et al.Robust influence blocking maximization in social networks[J].Journal of Computer Research and Development,2016,53(3):601-610.doi:10.7544/issn1000-1239.2016.20148341.
[16]KLEYWEGT A,SHAPRIO A,and HOMEM-DE-MELLO T.The sample average approximation method for stochastic discrete optimization[J].SIAM Journal on Optimization,2002,12(2):479-502.doi:10.1137/S1052623499363220.
[17]FUJISHIGE S.Submodular Functions and Optimization[M].Amsterdam,Elsevier Science Press,2005,Chapter 3.
[18]SHAPRIO A,DENTCHEVA D,and RUSZCZYNSKI A.Lectures on Stochastic Programming:Modeling and Theory[M].SIAM:Society for Industrial and Applied Mathematics,Philadelphia,PA,USA,SIAM Press,2014,Chapter 1.
1)Twitter,Wiki-Vote下载自:http://snap.stanford.edu/,Net PHY下载自http://research.microsoft.com/en-us/people/weic/projects.aspx