社会网络中基于社群衰减的影响力最大化算法
|
摘要
针对现有网络传播模型忽略了信息传播过程中的信息衰减,传统影响力最大化算法无法有效利用社群结构提高影响力传播范围的问题,提出一种基于社群结构的影响力最大化算法——社群衰减的影响力最大化(IMID)算法。首先对整个社会网络进行社群结构划分,评估社群中节点影响力范围,并考虑社群之间关联点之间的关联概率,在信息传播过程中增加节点之间信息传播衰减度计算。通过实验与分析,该算法不仅降低了时间复杂度,还获得了接近贪心算法的影响力传播范围,影响覆盖率达到90%以上。因此,在核心种子节点集和连接社群之间纽带节点选取若干节点作为初始节点,会让信息以最小的代价在网络中获得广泛传播。
The existing network spread model ignores the information attenuation in the process of information spread, and the traditional influence maximization algorithm cannot effectively use the community structure to improve the influence spread range. To solve these problems, an algorithm of Influence Maximization on Internal Decay(IMID) based on community structure was proposed. Firstly, the community structure of a whole social network was divided and the influence range of nodes in the community was evaluated. Then, with spread probability of association points between the communities considered, the attenuation degree of information spread between nodes was calculated. Experimental and analysis results show that the proposed algorithm not only reduces the time complexity, but also obtains the influence transmission range near that of greedy algorithm, with influence coverage over 90%. Therefore, with several nodes selected as the initial nodes between the core seed node set and connected communities, information will be widely spread in the network at the minimum cost.
The existing network spread model ignores the information attenuation in the process of information spread, and the traditional influence maximization algorithm cannot effectively use the community structure to improve the influence spread range. To solve these problems, an algorithm of Influence Maximization on Internal Decay(IMID) based on community structure was proposed. Firstly, the community structure of a whole social network was divided and the influence range of nodes in the community was evaluated. Then, with spread probability of association points between the communities considered, the attenuation degree of information spread between nodes was calculated. Experimental and analysis results show that the proposed algorithm not only reduces the time complexity, but also obtains the influence transmission range near that of greedy algorithm, with influence coverage over 90%. Therefore, with several nodes selected as the initial nodes between the core seed node set and connected communities, information will be widely spread in the network at the minimum cost.
引文
[1]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 Knowledge Discovery and Data Mining.New York:ACM,2003:137-146.
[2]LESKOVEC J,KRAUSE A,GUESTRIN C,et al.Cost-effective outbreak detection in networks[C]//Proceedings of the 2007 ACMrithms SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM,2007:420-429.
[3]GOYAL A,LU W,LAKSHMANAN L V S.CELF++:optimizing the greedy algorithm for influence maximization in social networks[C]//Proceedings of the 2011 International Conference Companion on World Wide Web.New York:ACM,2011:47-48.
[4]CHEN W,WANG Y,YANG S.Efficient influence maximization in social networks[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM,2009:199-208.
[5]ZHU T,WANG B,WU B,et al.Maximizing the spread of influence ranking in social networks[J].Information Sciences,2014,278:535-544.
[6]LAMBA H,NARAYANAM R.A novel and model independent approach for efficient influence maximization in social networks[C]//Proceedings of the 2013 International Conference on Web Information Systems Engineering,LNCS 8181.Berlin:Springer,2013:73-87.
[7]郭浩,陆余良,王宇,等.基于信息传播的微博用户影响力度量[J].山东大学学报(理学版),2012,47(5):78-83.(GUO H,LU Y L,WANG Y,et al.Measuring user influence of a microblog based on information diffusion[J].Journal of Shandong University(Natural Science),2012,47(5):78-83.)
[8]WANG Y,CONG G,SONG G,et al.Community-based greedy algorithm for mining top-K influential nodes in mobile social networks[C]//Proceedings of the 2010 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM,2010:1039-1048.
[9]YU H,KIM S K,KIM J.Scalable and parallelizable processing of influence maximization for large-scale social networks[C]//Proceedings of the 2013 IEEE International Conference on Data Engineering.Washington,DC:IEEE Computer Society,2013:266-277.
[10]吴凯,季新生,郭进时,等.基于微博网络的影响力最大化算法[J].计算机应用,2013,33(8):2091-2094.(WU K,JI X S,GUO J S,et al.Influence maximization algorithm for micro-blog network[J].Journal of Computer Applications,2013,33(8):2091-2094.)
[11]FISCHETTI M,KAHR M,LEITNER M,et al.Least cost influence propagation in(social)networks[J].Mathematical Programming,2018,170(1):293-325.
[12]田家堂,王轶彤,冯小军.一种新型的社会网络影响最大化算法[J].计算机学报,2011,34(10):1956-1965.(TIAN J T,WANGY T,FENG X J.A new hybrid algorithm for influence maximization in social networks[J].Chinese Journal of Computers,2011,34(10):1956-1965.)
[13]TONG G,WU W,TANG S,et al.Adaptive influence maximization in dynamic social networks[J].IEEE/ACM Transactions on Networking,2017,25(1):112-125.
[14]LI Y,FAN J,WANG Y,et al.Influence maximization on social graphs:a survey[J].IEEE Transactions on Knowledge and Data Engineering,2018,30(10):1852-1872.
[2]LESKOVEC J,KRAUSE A,GUESTRIN C,et al.Cost-effective outbreak detection in networks[C]//Proceedings of the 2007 ACMrithms SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM,2007:420-429.
[3]GOYAL A,LU W,LAKSHMANAN L V S.CELF++:optimizing the greedy algorithm for influence maximization in social networks[C]//Proceedings of the 2011 International Conference Companion on World Wide Web.New York:ACM,2011:47-48.
[4]CHEN W,WANG Y,YANG S.Efficient influence maximization in social networks[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM,2009:199-208.
[5]ZHU T,WANG B,WU B,et al.Maximizing the spread of influence ranking in social networks[J].Information Sciences,2014,278:535-544.
[6]LAMBA H,NARAYANAM R.A novel and model independent approach for efficient influence maximization in social networks[C]//Proceedings of the 2013 International Conference on Web Information Systems Engineering,LNCS 8181.Berlin:Springer,2013:73-87.
[7]郭浩,陆余良,王宇,等.基于信息传播的微博用户影响力度量[J].山东大学学报(理学版),2012,47(5):78-83.(GUO H,LU Y L,WANG Y,et al.Measuring user influence of a microblog based on information diffusion[J].Journal of Shandong University(Natural Science),2012,47(5):78-83.)
[8]WANG Y,CONG G,SONG G,et al.Community-based greedy algorithm for mining top-K influential nodes in mobile social networks[C]//Proceedings of the 2010 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM,2010:1039-1048.
[9]YU H,KIM S K,KIM J.Scalable and parallelizable processing of influence maximization for large-scale social networks[C]//Proceedings of the 2013 IEEE International Conference on Data Engineering.Washington,DC:IEEE Computer Society,2013:266-277.
[10]吴凯,季新生,郭进时,等.基于微博网络的影响力最大化算法[J].计算机应用,2013,33(8):2091-2094.(WU K,JI X S,GUO J S,et al.Influence maximization algorithm for micro-blog network[J].Journal of Computer Applications,2013,33(8):2091-2094.)
[11]FISCHETTI M,KAHR M,LEITNER M,et al.Least cost influence propagation in(social)networks[J].Mathematical Programming,2018,170(1):293-325.
[12]田家堂,王轶彤,冯小军.一种新型的社会网络影响最大化算法[J].计算机学报,2011,34(10):1956-1965.(TIAN J T,WANGY T,FENG X J.A new hybrid algorithm for influence maximization in social networks[J].Chinese Journal of Computers,2011,34(10):1956-1965.)
[13]TONG G,WU W,TANG S,et al.Adaptive influence maximization in dynamic social networks[J].IEEE/ACM Transactions on Networking,2017,25(1):112-125.
[14]LI Y,FAN J,WANG Y,et al.Influence maximization on social graphs:a survey[J].IEEE Transactions on Knowledge and Data Engineering,2018,30(10):1852-1872.