基于两阶段启发的社交网络影响最大化算法
|
摘要
社交网络中影响最大化问题的研究一直是社交网络分析的重点之一,其技术在人们生活的很多领域中具有应用价值.针对现有影响最大化算法存在时间复杂度高、算法精度低和不稳定的问题,文中利用线性阈值模型的能够将影响力累积的特性,提出一种基于度和影响力的混合启发式算法—DIH(Degree and Influence Heuristic)算法.该算法综合考虑网络的传播特性和结构特性,基于线性阈值模型将整个影响最大化计算分为两个启发阶段:首先进行度折启发,在激活节点的同时将节点的影响力积累,然后进行影响力启发,将度折启发期间积累的影响力爆发,从而激活更多的节点.为保证算法的效率,本文在影响力启发阶段设计了一种近似估计节点影响力的计算方法.最后,本文在三个不同的真实网络中验证了算法的有效性.
The study of influence maximization is the focus of the social network analysis,and its theory has a great significance in our lives.There still exist some problems to be solved in its application,such as high time complexity,low precision and instability.To solve these problems,this paper proposes a hybrid heuristic algorithm named Degree and Influence Heuristic(DIH).According to the accumulation caused by using linear threshold model features,the computation of influence maximization is broken up into two stages:the degree discount heuristics and influence-based heuristics.We first employ the degree discount heuristics to active nodes and accumulate influence of nodes.Then,we present an approximate evaluation method to activate more nodes during the stage of influencebased heuristics.The experimental results on three different real datasets show the effectiveness of the proposed algorithm.
The study of influence maximization is the focus of the social network analysis,and its theory has a great significance in our lives.There still exist some problems to be solved in its application,such as high time complexity,low precision and instability.To solve these problems,this paper proposes a hybrid heuristic algorithm named Degree and Influence Heuristic(DIH).According to the accumulation caused by using linear threshold model features,the computation of influence maximization is broken up into two stages:the degree discount heuristics and influence-based heuristics.We first employ the degree discount heuristics to active nodes and accumulate influence of nodes.Then,we present an approximate evaluation method to activate more nodes during the stage of influencebased heuristics.The experimental results on three different real datasets show the effectiveness of the proposed algorithm.
引文
[1]Domingos P,Richardson M.Mining the network value of customers[C].Proceedings of the 7th ACM SIGKDD International Conference on Know ledge Discovery and Data M ining,San Francisco:Association for Computing M achinery,2001:57-66.
[2]Richardson M,Domingos P.Mining knowledge-sharing sites for viral marketing[C].Proceedings of the 8th ACM SIGKDD International Conference on Know ledge Discovery and Data M ining,New York:Association for Computing M achinery,2002:61-70.
[3]Li H,Bhowmick S,Sun A,et al.Conformity-aware influence maximization in online social networks[J].Vldb Journal—the International Journal on Very Large Data Bases,2014,24(1):117-141.
[4]Cao Jiu-xin,Dong Dan,Xu Shun,et al.A k-core based algorithm for influence maximization in social network[J].Chinese Journal of Computer,2015,38(2):238-248.
[5]Kempe D,Kleinberg J,Tardos E.Maximizing the spread of influence through a social network[C].Proceedings of the 9th ACM SIGKDD International Conference on Know ledge Discovery and Data M ining,New York:Association for Computing M achinery,2003:137-146.
[6]Leskovec J,Krause A,Guestrin C,et al.Cost-effective outbreak detection in networks[C].Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,New York:Association for Computing Machinery,2007:420-429.
[7]Chen W,Wang Y,Yang S.Efficient influence maximization in social networks[C].Proceedings of the 15th ACM SIGKDD International Conference on Know ledge Discovery and Data M ining,New York:Association for Computing M achinery,2009:199-208.
[8]Zhou S,Yue K,Fang Q,et al.An efficient algorithm for influence maximization under linear threshold model[C].Proceedings of the26th Chinese Control and Decision Conference,Washington:IEEE Computer Society,2014:5352-5357.
[9]Zhou C,Zhang P,Guo J,et al.UBLF:An upper bound based approach to discover influential nodes in social networks[C].Proceedings-IEEE 13th International Conference on Data M ining,NJ:Institute of Electrical and Electronics Engineers,2013:907-916.
[10]Goyal A,Lu W,Lakshmanan L V S.CELF++:optimizing the greedy algorithm for influence maximization in social networks[C].Proceedings of the 20th International Conference Companion on World Wide Web,New York:Association for Computing M achinery,2011:47-48.
[11]Wasserman and Faust.Social network analysis:methods and applications[J].American Ethnologist,1997,24(1):219-220.
[12]Estevez P A,Vera P,Saito K.Selecting the most influential nodes in social networks[C].The 2007 International Joint Conference on Neural Networks,NJ:Institute of Electrical and Electronics Engineers,2007:2397-2402.
[13]Jiang Q,Song G,Cong G,et al.Simulated annealing based influence maximization in social networks[C].Proceedings of the 25th AAAI Conference on Artificial Intelligence and the 23rd Innovative Applications of Artificial Intelligence Conference.CA:AI Access Foundation,2011:127-132.
[14]Chen W,Yuan Y,Zhang L.Scalable influence maximization in social networks under the linear threshold model[C].Proceedings of the 10th IEEE International Conference on Data M ining,NJ:Institute of Electrical and Electronics Engineers,2010:88-97.
[4]曹玖新,董丹,徐顺,等.一种基于k-核的社会网络影响最大化算法[J].计算机学报,2015,38(2):238-248.
[2]Richardson M,Domingos P.Mining knowledge-sharing sites for viral marketing[C].Proceedings of the 8th ACM SIGKDD International Conference on Know ledge Discovery and Data M ining,New York:Association for Computing M achinery,2002:61-70.
[3]Li H,Bhowmick S,Sun A,et al.Conformity-aware influence maximization in online social networks[J].Vldb Journal—the International Journal on Very Large Data Bases,2014,24(1):117-141.
[4]Cao Jiu-xin,Dong Dan,Xu Shun,et al.A k-core based algorithm for influence maximization in social network[J].Chinese Journal of Computer,2015,38(2):238-248.
[5]Kempe D,Kleinberg J,Tardos E.Maximizing the spread of influence through a social network[C].Proceedings of the 9th ACM SIGKDD International Conference on Know ledge Discovery and Data M ining,New York:Association for Computing M achinery,2003:137-146.
[6]Leskovec J,Krause A,Guestrin C,et al.Cost-effective outbreak detection in networks[C].Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,New York:Association for Computing Machinery,2007:420-429.
[7]Chen W,Wang Y,Yang S.Efficient influence maximization in social networks[C].Proceedings of the 15th ACM SIGKDD International Conference on Know ledge Discovery and Data M ining,New York:Association for Computing M achinery,2009:199-208.
[8]Zhou S,Yue K,Fang Q,et al.An efficient algorithm for influence maximization under linear threshold model[C].Proceedings of the26th Chinese Control and Decision Conference,Washington:IEEE Computer Society,2014:5352-5357.
[9]Zhou C,Zhang P,Guo J,et al.UBLF:An upper bound based approach to discover influential nodes in social networks[C].Proceedings-IEEE 13th International Conference on Data M ining,NJ:Institute of Electrical and Electronics Engineers,2013:907-916.
[10]Goyal A,Lu W,Lakshmanan L V S.CELF++:optimizing the greedy algorithm for influence maximization in social networks[C].Proceedings of the 20th International Conference Companion on World Wide Web,New York:Association for Computing M achinery,2011:47-48.
[11]Wasserman and Faust.Social network analysis:methods and applications[J].American Ethnologist,1997,24(1):219-220.
[12]Estevez P A,Vera P,Saito K.Selecting the most influential nodes in social networks[C].The 2007 International Joint Conference on Neural Networks,NJ:Institute of Electrical and Electronics Engineers,2007:2397-2402.
[13]Jiang Q,Song G,Cong G,et al.Simulated annealing based influence maximization in social networks[C].Proceedings of the 25th AAAI Conference on Artificial Intelligence and the 23rd Innovative Applications of Artificial Intelligence Conference.CA:AI Access Foundation,2011:127-132.
[14]Chen W,Yuan Y,Zhang L.Scalable influence maximization in social networks under the linear threshold model[C].Proceedings of the 10th IEEE International Conference on Data M ining,NJ:Institute of Electrical and Electronics Engineers,2010:88-97.
[4]曹玖新,董丹,徐顺,等.一种基于k-核的社会网络影响最大化算法[J].计算机学报,2015,38(2):238-248.