关联影响力传播最大化方法
|
摘要
社会网络中影响力传播最大化是社会网络分析领域所关注的重要问题。针对多个影响力同时进行传播,且影响力间存在传播促进的情况,提出关联影响力传播最大化问题。首先,对经典线性阈值模型进行扩展,提出关联影响力线性阈值模型对关联影响力传播过程进行建模;其次,定义了关联影响力传播最大化问题,证明了该问题是NP-hard的,以及问题目标函数满足子模性;再次,针对该问题提出基于结点激活贡献估计的求解算法;然后,利用结点激活贡献估计存在相互独立性,进一步提出了并行化求解算法,并在Spark GraphX并行图计算框架上实现了该算法;最后,在真实的社会网络数据集上,通过实验测试验证了所提出方法的有效性。
Influence maximization is currently a focused problem in the research area of social networks.This paper considers the problem of correlated influence maximization(CIM) where multiple influence diffusion processes promote with each other.First,a correlated linear threshold model(CLT) is presented by extending the classic linear threshold model to model the diffusion processes of correlated influences.Then,the correlated influence maximization under CLT is proven to be NP-hard and the objective function to be submodular respectively.An algorithm which is based on the estimation of activation contributions of vertices(ACA) under CLT is proposed to solve CIM.Since the estimations of activation contribution for different nodes are independent with each other,a parallel ACA which is implemented based on Spark GraphX is furthermore presented to solve CIM.Finally,experiments are carried on real data sets of social networks to verify the feasibility and scalability of the proposed algorithms.
Influence maximization is currently a focused problem in the research area of social networks.This paper considers the problem of correlated influence maximization(CIM) where multiple influence diffusion processes promote with each other.First,a correlated linear threshold model(CLT) is presented by extending the classic linear threshold model to model the diffusion processes of correlated influences.Then,the correlated influence maximization under CLT is proven to be NP-hard and the objective function to be submodular respectively.An algorithm which is based on the estimation of activation contributions of vertices(ACA) under CLT is proposed to solve CIM.Since the estimations of activation contribution for different nodes are independent with each other,a parallel ACA which is implemented based on Spark GraphX is furthermore presented to solve CIM.Finally,experiments are carried on real data sets of social networks to verify the feasibility and scalability of the proposed algorithms.
引文
[1]Wu Xingdong,Li Yi,Li Lei.Influence analysis of online social networks[J].Chinese Journal of Computers,2014,37(4):735-752.
[2]Kempe D,Kleinberg J,Tardosé.Maximizing the spread of influence through a social network[C]//Proceedings of the9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Washington,Aug 24-27.New York:ACM,2003:137-146.
[3]Chen Wei,Wang Chi,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,Washington,Jul 25-28,2010.New York:ACM,2010:1029-1038.
[4]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.
[5]Chen Hao,Wang Yitong.Threshold-based heuristic algorithm for influence maximization[J].Journal of Computer Research and Development,2012,49(10):2181-2188.
[6]He Xinran,Song Guojie,Chen Wei,et al.Influence blocking maximization in social networks under the competitive linear threshold model[C]//Proceedings of the 12th SIAMInternational Conference on Data Mining,Anaheim,Apr26-28,2012.Philadelphia:SIAM,2012:463-474.
[7]Nguyen N P,Yan Guanhua,Thai M T,et al.Containment of misinformation spread in online social networks[C]//Proceedings of the 3rd Annual ACM Web Science Conference,Evanston,Jun 22-24.New York:ACM,2012:213-222.
[8]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.
[9]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.
[10]Liu Weiyi,Yue Kun,Wu Hong,et al.Containment of competitive influence spread in social networks[J].KnowledgeBased Systems,2016,109:266-275.
[11]Li Hui,Bhowmick S S,Cui Jiangtao,et al.GetReal:towards realistic selection of influence maximization strategies in competitive networks[C]//Proceedings of the 2015 ACMSIGMOD International Conference on Management of Data,Melbourne,May 31-Jun 4,2015.New York:ACM,2015:1525-1537.
[12]Narayanam R,Nanavati A A.Viral marketing for product cross-sell through social networks[C]//LNCS 7524:Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases,Bristol,Sep 24-28,2012.Berlin,Heidelberg:Springer,2012:581-596.
[13]Lu Wei,Chen Wei,Lakshmanan L V S.From competition to complementarity:comparative influence diffusion and maximization[J].Proceedings of the VLDB Endowment,2015,9(2):60-71.
[14]Zarezade A,Khodadadi A,Farajtabar M,et al.Correlated cascades:compete or cooperate[J].ar Xiv:1510.00936,2015.
[15]The Apache Software Foundation.Apache spark-lightningfast cluster computing[EB/OL].[2017-07-20].http://spark.apache.org/.
[16]Fujishige S.Submodular functions and optimization[M].Amsterdam:Elsevier Science Publishers,2005.
[17]Stanford University.Stanford network analysis project[EB/OL].[2017-07-20].http://snap.stanford.edu/.
[18]Datatang(Beijing)Technology Co.,Ltd.A data set of supermarket shopping records[EB/OL].[2017-07-20].http://www.datatang.com/.
[1]吴信东,李毅,李磊.在线社交网络影响力分析[J].计算机学报,2014,37(4):735-752.
[5]陈浩,王轶彤.基于阈值的社交网络影响力最大化算法[J].计算机研究与发展,2012,49(10):2181-2188.
[9]李劲,岳昆,张德海,等.社会网络中影响力传播的鲁棒抑制方法[J].计算机研究与发展,2016,53(3):601-610.
[18]数据堂(北京)科技股份有限公司.某超市购物数据集[EB/OL].[2017-07-20].http://www.datatang.com/.
[2]Kempe D,Kleinberg J,Tardosé.Maximizing the spread of influence through a social network[C]//Proceedings of the9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Washington,Aug 24-27.New York:ACM,2003:137-146.
[3]Chen Wei,Wang Chi,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,Washington,Jul 25-28,2010.New York:ACM,2010:1029-1038.
[4]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.
[5]Chen Hao,Wang Yitong.Threshold-based heuristic algorithm for influence maximization[J].Journal of Computer Research and Development,2012,49(10):2181-2188.
[6]He Xinran,Song Guojie,Chen Wei,et al.Influence blocking maximization in social networks under the competitive linear threshold model[C]//Proceedings of the 12th SIAMInternational Conference on Data Mining,Anaheim,Apr26-28,2012.Philadelphia:SIAM,2012:463-474.
[7]Nguyen N P,Yan Guanhua,Thai M T,et al.Containment of misinformation spread in online social networks[C]//Proceedings of the 3rd Annual ACM Web Science Conference,Evanston,Jun 22-24.New York:ACM,2012:213-222.
[8]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.
[9]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.
[10]Liu Weiyi,Yue Kun,Wu Hong,et al.Containment of competitive influence spread in social networks[J].KnowledgeBased Systems,2016,109:266-275.
[11]Li Hui,Bhowmick S S,Cui Jiangtao,et al.GetReal:towards realistic selection of influence maximization strategies in competitive networks[C]//Proceedings of the 2015 ACMSIGMOD International Conference on Management of Data,Melbourne,May 31-Jun 4,2015.New York:ACM,2015:1525-1537.
[12]Narayanam R,Nanavati A A.Viral marketing for product cross-sell through social networks[C]//LNCS 7524:Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases,Bristol,Sep 24-28,2012.Berlin,Heidelberg:Springer,2012:581-596.
[13]Lu Wei,Chen Wei,Lakshmanan L V S.From competition to complementarity:comparative influence diffusion and maximization[J].Proceedings of the VLDB Endowment,2015,9(2):60-71.
[14]Zarezade A,Khodadadi A,Farajtabar M,et al.Correlated cascades:compete or cooperate[J].ar Xiv:1510.00936,2015.
[15]The Apache Software Foundation.Apache spark-lightningfast cluster computing[EB/OL].[2017-07-20].http://spark.apache.org/.
[16]Fujishige S.Submodular functions and optimization[M].Amsterdam:Elsevier Science Publishers,2005.
[17]Stanford University.Stanford network analysis project[EB/OL].[2017-07-20].http://snap.stanford.edu/.
[18]Datatang(Beijing)Technology Co.,Ltd.A data set of supermarket shopping records[EB/OL].[2017-07-20].http://www.datatang.com/.
[1]吴信东,李毅,李磊.在线社交网络影响力分析[J].计算机学报,2014,37(4):735-752.
[5]陈浩,王轶彤.基于阈值的社交网络影响力最大化算法[J].计算机研究与发展,2012,49(10):2181-2188.
[9]李劲,岳昆,张德海,等.社会网络中影响力传播的鲁棒抑制方法[J].计算机研究与发展,2016,53(3):601-610.
[18]数据堂(北京)科技股份有限公司.某超市购物数据集[EB/OL].[2017-07-20].http://www.datatang.com/.