社会网络中基于社群衰减的影响力最大化算法

doi:10.11772/j.issn.1001-9081.2018081695

计算机应用 ›› 2019, Vol. 39 ›› Issue (3): 834-838.DOI: 10.11772/j.issn.1001-9081.2018081695

社会网络中基于社群衰减的影响力最大化算法

孙子力, 彭舰, 仝博

四川大学计算机学院, 成都 610065

收稿日期:2018-08-15 修回日期:2018-08-30 出版日期:2019-03-10 发布日期:2019-03-11
通讯作者: 彭舰
作者简介:孙子力(1991-),男,山东烟台人,硕士研究生,主要研究方向:大数据与云计算;彭舰(1970-),男,四川成都人,教授,博士,CCF高级会员,主要研究方向:大数据与云计算、无线传感器网络、移动计算;仝博(1989-),男,天津人,博士研究生,主要研究方向:大数据与云计算。

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

SUN Zili, PENG Jian, TONG Bo

College of Computer Science, Sichuan University, Chengdu Sichuan 610065, China

Received:2018-08-15 Revised:2018-08-30 Online:2019-03-10 Published:2019-03-11

摘要/Abstract

摘要：

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

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

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

中图分类号:

TP301.6

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

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.

参考文献

[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]	张萌, 李维华. 用户互动表示下的影响力最大化算法[J]. 计算机应用, 2021, 41(7): 1964-1969.
[2]	孙鹤立, 孙玉柱, 张晓云. 基于生成对抗网络的事件描述生成[J]. 计算机应用, 2021, 41(5): 1256-1261.
[3]	冯丽萍, 韩琦, 周志刚, 白增亮. 社交网络影响的不良信息扩散建模及最优控制策略[J]. 计算机应用, 2020, 40(3): 735-739.
[4]	孙鹤立, 孙玉柱, 张晓云. 基于事件描述的社交事件参与度预测[J]. 计算机应用, 2020, 40(11): 3101-3106.
[5]	秦海燕, 章永龙, 李斌. 社会网络下分配众包任务的真实机制[J]. 计算机应用, 2020, 40(10): 3019-3024.
[6]	张宪立, 唐建新, 曹来成. 基于反向PageRank的影响力最大化算法[J]. 计算机应用, 2020, 40(1): 96-102.
[7]	刘威, 张明新, 安德智. 面向微博话题的用户影响力分析算法[J]. 计算机应用, 2019, 39(1): 213-219.
[8]	李敏佳, 许国艳, 朱帅, 张网娟. 基于结构洞和度折扣的影响力最大化算法[J]. 计算机应用, 2018, 38(12): 3419-3424.
[9]	郑晓雪, 张大方, 刁祖龙. 基于用户身份特征的多标签分类算法[J]. 计算机应用, 2017, 37(6): 1697-1701.
[10]	李志明, 唐永中. 基于社交网络和关联数据的服务网络构建方法[J]. 计算机应用, 2017, 37(2): 468-472.
[11]	刘院英, 郭景峰, 魏立东, 胡心专. 成本控制下的快速影响最大化算法[J]. 计算机应用, 2017, 37(2): 367-372.
[12]	郑永广, 岳昆, 尹子都, 张学杰. 大规模社交网络中高效的关键用户选取方法[J]. 计算机应用, 2017, 37(11): 3101-3106.
[13]	王珊珊, 冷甦鹏. 面向移动社会网络的好友推荐方法[J]. 计算机应用, 2016, 36(9): 2386-2389.
[14]	徐涛, 孟野. 踪迹聚类下组织实体的重要度排序方法[J]. 计算机应用, 2016, 36(5): 1284-1289.
[15]	李源昊, 陆平, 吴一凡, 韦薇, 宋国杰. 面向移动社会网络的用户年龄与性别特征识别[J]. 计算机应用, 2016, 36(2): 364-371.

社会网络中基于社群衰减的影响力最大化算法

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics