Influence maximization algorithm on internal decay based on community structure in social network

doi:10.11772/j.issn.1001-9081.2018081695

Abstract

Abstract:

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.

Key words: information spread, influence maximization, social network, community division

摘要：

针对现有网络传播模型忽略了信息传播过程中的信息衰减，传统影响力最大化算法无法有效利用社群结构提高影响力传播范围的问题，提出一种基于社群结构的影响力最大化算法——社群衰减的影响力最大化（IMID）算法。首先对整个社会网络进行社群结构划分，评估社群中节点影响力范围，并考虑社群之间关联点之间的关联概率，在信息传播过程中增加节点之间信息传播衰减度计算。通过实验与分析，该算法不仅降低了时间复杂度，还获得了接近贪心算法的影响力传播范围，影响覆盖率达到90%以上。因此，在核心种子节点集和连接社群之间纽带节点选取若干节点作为初始节点，会让信息以最小的代价在网络中获得广泛传播。

关键词: 信息传播, 影响力最大化, 社会网络, 社群划分

CLC Number:

TP301.6

SUN Zili, PENG Jian, TONG Bo. Influence maximization algorithm on internal decay based on community structure in social network[J]. Journal of Computer Applications, 2019, 39(3): 834-838.

孙子力, 彭舰, 仝博. 社会网络中基于社群衰减的影响力最大化算法[J]. 计算机应用, 2019, 39(3): 834-838.

References

[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 ACM 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, WANG Y 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.

[1]	ZHANG Meng, LI Weihua. Influence maximization algorithm based on user interactive representation [J]. Journal of Computer Applications, 2021, 41(7): 1964-1969.
[2]	SUN Heli, SUN Yuzhu, ZHANG Xiaoyun. Event description generation based on generative adversarial network [J]. Journal of Computer Applications, 2021, 41(5): 1256-1261.
[3]	SUN Heli, XU Tong, HE Liang, JIA Xiaolin. Personalized social event recommendation method integrating user historical behaviors and social relationships [J]. Journal of Computer Applications, 2021, 41(2): 324-329.
[4]	Xujian ZHAO, Chongwei WANG. Storyline extraction method from Weibo news based on graph convolutional network [J]. Journal of Computer Applications, 2021, 41(11): 3139-3144.
[5]	LI Xiangkun, JIA Caiyan. Collaborative filtering method fusing overlapping community regularization and implicit feedback [J]. Journal of Computer Applications, 2021, 41(1): 53-59.
[6]	SHENG Jun, LI Bin, CHEN Ling. Recommendation algorithm based on modularity and label propagation [J]. Journal of Computer Applications, 2020, 40(9): 2606-2612.
[7]	LI Chunying, TANG Yong, XIAO Zhenghong, LI Tiansong. Influential scholar recommendation model in academic social network [J]. Journal of Computer Applications, 2020, 40(9): 2594-2599.
[8]	YANG Shuxin, LIANG Wen, ZHU Kaili. Reverse influence maximization algorithm in social networks [J]. Journal of Computer Applications, 2020, 40(7): 1944-1949.
[9]	YI Dongyi, DENG Genqiang, DONG Chaoxiong, ZHU Miaomiao, LYU Zhouping, ZHU Suisong. Medical insurance fraud detection algorithm based on graph convolutional neural network [J]. Journal of Computer Applications, 2020, 40(5): 1272-1277.
[10]	FENG Liping, HAN Qi, ZHOU Zhigang, BAI Zengliang. Bad information diffusion modeling and optimal control strategy influenced by social networks [J]. Journal of Computer Applications, 2020, 40(3): 735-739.
[11]	SHAN Xiaohuan, ZHANG Zhiguo, SONG Baoyan, REN Chenglin. Activity recommendation method based on directed label graph and user feedback in event-based social network [J]. Journal of Computer Applications, 2020, 40(2): 448-453.
[12]	SUN Heli, SUN Yuzhu, ZHANG Xiaoyun. Social event participation prediction based on event description [J]. Journal of Computer Applications, 2020, 40(11): 3101-3106.
[13]	QIN Haiyan, ZHANG Yonglong, LI Bin. Truthful mechanism for crowdsourcing task assignment in social network [J]. Journal of Computer Applications, 2020, 40(10): 3019-3024.
[14]	SUN Heli, HE Liang, HE Fang, SUN Miaomiao, JIA Xiaolin. Network embedding based tenuous subgraph finding [J]. Journal of Computer Applications, 2020, 40(10): 2929-2935.
[15]	HE Haochen, ZHANG Danhong. Recommendation method based on multidimensional social relationship embedded deep graph neural network [J]. Journal of Computer Applications, 2020, 40(10): 2795-2803.