基于库仑力模型的动态社会网络积极影响力最大化算法

doi:10.11959/j.issn.1000-0801.2020162

电信科学 ›› 2020, Vol. 36 ›› Issue (6): 107-118.doi: 10.11959/j.issn.1000-0801.2020162

基于库仑力模型的动态社会网络积极影响力最大化算法

卢敏¹,陈光鲁¹,杨晓慧¹,黄淳岚¹,乐光学^1,²

¹ 江西理工大学理学院，江西赣州 341000
² 嘉兴学院数理与信息工程学院，浙江嘉兴 314001

修回日期:2020-05-18 出版日期:2020-06-20 发布日期:2020-06-18
作者简介:卢敏（1964- ），男，江西理工大学理学院教授，主要研究方向为网络通信及电子材料器件等|陈光鲁（1995- ），男，江西理工大学理学院硕士生，主要研究方向为社会网络和数据挖掘|杨晓慧（1996- ），女，江西理工大学理学院硕士生，主要研究方向为边缘计算|黄淳岚（1997- ），女，江西理工大学理学院硕士生，主要研究方向为移动云计算|乐光学（1963- ），男，嘉兴学院数理与信息工程学院教授，主要研究方向为多云融合与协同服务、无线mesh网络与移动云计算、混成与嵌入式系统
基金资助:
国家自然科学基金资助项目(11704163);江西省教育厅重点研究项目(GJJ160594)

Dynamic social network active influence maximization algorithm based on Coulomb force model

Min LU¹,Guanglu CHEN¹,Xiaohui YANG¹,Chunlan HUANG¹,Guangxue YUE^1,²

¹ College of Science,Jiangxi University of Science and Technology,Ganzhou 341000,China
² College of Mathematical Information and Engineering,Jiaxing University,Jiaxing 314001,China

Revised:2020-05-18 Online:2020-06-20 Published:2020-06-18
Supported by:
The National Natural Science Foundation of China(11704163);Key Research Project of Education Commission of Jiangxi Province(GJJ160594)

摘要/Abstract

摘要：

影响力最大化问题已经成为社会网络中重要的研究内容，其影响力传播模型和求解算法是关键的核心问题。为了提高预测传播结果的准确度，引入传播过程中激活节点数量动态变化与节点间信任关系对IC模型进行改进，结合社会影响力与库仑力之间的相似性，提出一种基于信任关系的动态社会库仑力（dynamic social Coulomb forces based on trust relationship，DSC-TR）模型，构建一种优化的随机贪心（random greedy， RG-DPIM）算法求解影响最大化问题。仿真实验结果表明，DSC-TR模型的预测准确度明显优于SC-B、IC模型；RG-DPIM算法性能优于G-DPIM、IPA、TDIA算法。

关键词: 社会网络, 影响最大化, 库仑力, 传播模型, 信任关系

Abstract:

The problem of maximizing influence has become an important research content in social networks,and its influence propagation model and solving algorithm are the key core issues.In order to improve the accuracy of predicting the propagation results,the dynamic change of the number of activated nodes and the trust relationship between the nodes during the propagation process were introduced to improve the IC model.Combining the similarity between social influence and Coulomb force,a dynamic based on trust relationship was proposed,a dynamic social coulomb forces based on trust relationships (DSC-TR) model was proposed,and an optimized random greedy (RG-DPIM) algorithm was constructed to solve the problem of maximum impact.Simulation results show that the prediction accuracy of the DSC-TR model is obviously better than that of SC-B and IC models.The performance of RG-DPIM algorithm is obviously better than that of G-DPIM,IPA and TDIA algorithms.

Key words: social network, influence maximization, Coulomb force, diffusion model, trust relationship

中图分类号:

TP393

卢敏,陈光鲁,杨晓慧,黄淳岚,乐光学. 基于库仑力模型的动态社会网络积极影响力最大化算法[J]. 电信科学, 2020, 36(6): 107-118.

Min LU,Guanglu CHEN,Xiaohui YANG,Chunlan HUANG,Guangxue YUE. Dynamic social network active influence maximization algorithm based on Coulomb force model[J]. Telecommunications Science, 2020, 36(6): 107-118.

图/表 12

表1

图1

图2

图3

图4

表2

表3

图5

图6

图7

图8

图9

参考文献 28

[1]	韩忠明, 陈炎, 刘雯 ,等. 社会网络节点影响力分析研究[J]. 软件学报, 2017,28(1): 84-104.
	HAN Z M , CHEN Y , LIU W ,et al. Research on node influence analysis in social networks[J]. Journal of Software, 2017,28(1): 84-104.
[2]	马茜, 马军 . 在影响力最大化问题中寻找种子节点的替补节点[J]. 计算机学报, 2017,40(3): 674-686.
	MA Q , MA J . Discovering the substitutes for the seeds in influence maximization problem[J]. Chinese Journal of Computers, 2017,40(3): 674-686.
[3]	琚春华, 鲍福光, 许翀寰 . 基于社会网络协同过滤的社会化电子商务推荐研究[J]. 电信科学, 2014,30(9): 82-86.
	JU C H , BAO F G , XU C H . Research on social network collaborative filtering based e-commerce recommending[J]. Telecommunications Science, 2014,30(9): 82-86.
[4]	HOSSEINI-POZVEH M , ZAMANIFAR K ， NAGHSH-NILCHI A R . Assessing information diffusion models for influence maximization in signed social networks[J]. Expert Systems With Applications, 2019,119(4): 476-490.
[5]	DOMINGOS P , RICHARDSON M . Mining the network value of customers[C]// Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Mining. New York:ACM Press, 2001: 57-66.
[6]	KEMPE D , KLEINBERG J , TARDOS E . Maximizing the spread of influence in a social network[C]// Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM Press, 2003: 137-146.
[7]	GOLDENBERG J , LIBAI B , MULLER E . Using complex systems analysis to advance marketing theory development:modeling heterogeneity effects on new product growth through stochastic cellular automata[J]. Academy of Marketing Science Review, 2001,9(3): 1-18.
[8]	GRANOVETTER M . Threshold models of collective behavior[J]. American Journal of Sociology, 1987,83(6): 1420-1443.
[9]	BARBIERI N , BONCHI F , MANCO G . Topic-aware social influence propagation models[J]. Knowledge and Information Systems, 2013,37(3): 555-584.
[10]	刘勇, 谢胜男, 仲志伟 ,等. 社会网中基于主题兴趣的影响最大化算法[J]. 计算机研究发展, 2018,55(11): 2406-2418
	LIU Y , XIE S N , ZHONG Z W ,et al. Topic-interest based influence maximization algorithm in social networks[J]. Journal of Computer Research and Development, 2018,55(11): 2406-2418.
[11]	WANG F , WANG G J , XIE D Q . Maximizing the spread of positive influence under LT-MLA model[J]. Advance in Services Computing, 2016,10(11): 450-463.
[12]	CHEN W , COLLINS A , CUMMINGS R ,et al. Influence maximization in social networks when negative opinions may emerge and propagate[C]// Proceedings of 2010 SIAM International Conference on Data Mining. Columbus:SIAM Press, 2010: 379-390.
[13]	HOSSEINI-POZVEH M , ZAMANIFAR K , NAGHSH-NILCHI A R ,et al. Maximizing the spread of positive influence in signed social networks[J]. Intelligent Data Analysis, 2016,20(1): 199-218.
[14]	SHANG J X , WU H C , ZHOU S B ,et al. IMPC:influence maximization based on multi-neighbor potential in community networks[J]. Physica A:Statistical Mechanics and Its Applications, 2018,512(15): 1085-1103.
[15]	LI H , BHOWMICK S S , SUN A ,et al. Conformity-aware influence maximization in online social networks[J]. The VLDB Journal, 2014,5(8): 117-141.
[16]	HABIBA , BERGER-WOLF T Y , . Influence maximizing the extent of spread in a dynamic network[C]// Proceedings of International Conference on Knowledge Discovery and Data Mining. Berlin:Springer-Verlag, 2007: 542-550.
[17]	WANG H H , YANG Q , LEI F ,et al. Maximizing positive influence in signed social networks[C]// Proceedings of International Conference on Cloud Computing and Security. Berlin:Springer International Publishing, 2015: 356-357.
[18]	WANG F , JIANG W J , LI X L ,et al. Maximizing positive influence spread in online social networks via fluid dynamics[J]. Future Generation Computer Systems, 2018,86(9): 1491-1502.
[19]	谭振华, 时迎成, 石楠翔 ,等. 基于引力学的在线社会网络空间谣言传播分析模型[J]. 计算机研究与发展, 2017,54(11): 2586-2599.
	TAN Z H , SHI Y C , SHI N X ,et al. Rumor propagation analysis model inspired by gravity theory for online social networks[J]. Journal of Computer Research and Development, 2017,54(11): 2586-2599.
[20]	GUIZANI N , ELGHARIANI A , KOBES J ,et al. Effects of social network structure on epidemic disease spread dynamics with application to ad hoc networks[J]. IEEE Network, 2019,33(3): 139-145.
[21]	GRIFFIN C , RAJTMAJER S , SQUICCIARINI A ,et al. Consensus and information cascades in game-theoretic imitation dynamics with static and dynamic network topologies[J]. SIAM Journal on Applied Dynamical Systems, 2019,18(2): 597-628.
[22]	LESKOVE C 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:ACM Press, 2007: 420-429.
[23]	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. Hyderabad:Association for Computing Machinery, 2011: 47-48.
[24]	RUI X , MENG F , WANG Z ,et al. A reversed node ranking approach for influence maximization in social networks[J]. Applied Intelligence, 2019,49(7): 2684-2698.
[25]	LI C , WANG L , SUN S ,et al. Identification of influential spreaders based on classified neighbors in real-world complex networks[J]. Applied Mathematics and Computation, 2018(320): 512-523.
[26]	潘剑飞, 徐丽丽, 董一鸿 . 动态社区演化研究进展[J]. 电信科学, 2017,33(1): 24-33.
	PAN J F , XU L L , DONG Y H . Research progress of dynamic community evolution[J]. Telecommunications Science, 2017,33(1): 24-33.
[27]	KIM J , KIM S K , YU H . Scalable and parallelizable processing of influence maximization for large-scale social networks[C]// Proceedings of the 29th International Conference on Data Engineering. Piscataway:IEEE Press, 2013: 266-277.
[28]	王欢欢 . 社交网络影响力最大化的研究[D]. 南京:南京航空航天大学, 2016.
	WANG H H . Research on influence maximization in social networks[D]. Nanjing:Nanjing University of Aeronautics and Astronautics, 2016.

数据集	节点数/个	边数/条	信任度范围	信任阈值
Bitcoin OTC数据集	5 881	35 592	-10~10	0
Epinions数据集	131 828	841 372	1~5	3

数据集	组数/组	抽样节点数/个	抽样边/条
Epinions数据集	1	131 828	841 372
	10	542~834	5 000
Bitcoin OTC数据集	10	205~436	1 000

基于库仑力模型的动态社会网络积极影响力最大化算法

Dynamic social network active influence maximization algorithm based on Coulomb force model

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 28

相关文章 11

Metrics

推荐阅读 0

库仑力模型	DSC-TR模型
电荷	节点
电荷量	节点自身影响力
库仑力	社会库仑力
库仑力内外方向	影响传播扩散或抑制

[1]	赵婧博, 董石磊, 黄婷钰, 陈梦霞, 黄鹏. 5G专网的精准覆盖研究[J]. 电信科学, 2022, 38(Z1): 108-119.
[2]	陶昕, 万俊青, 李益锋, 徐羲晟, 乔楠婷, 许彬. 基于射线追踪传播模型实现5G室内分布系统仿真的研究[J]. 电信科学, 2022, 38(2): 111-118.
[3]	王晓云, 邓伟, 张龙, 苏鑫, 赵世卓. 基于特征建模的TDD系统大气波导干扰控制体系研究[J]. 电信科学, 2022, 38(11): 11-23.
[4]	吉福生,张洪沛,张炎. 社区结构感知的间断连接无线网络路由机制[J]. 电信科学, 2015, 31(4): 65-70.
[5]	雷方元,雷刚. CDMA下行信号对EGSM上行信号的同频干扰研究[J]. 电信科学, 2015, 31(1): 2015002-.
[6]	雷方元,雷刚. CDMA下行信号对EGSM上行信号的同频干扰研究[J]. 电信科学, 2015, 31(1): 139-145.
[7]	琚春华,鲍福光,许翀寰. 基于社会网络协同过滤的社会化电子商务推荐研究[J]. 电信科学, 2014, 30(9): 82-86.
[8]	吴大猛,钱江波,陈叶芳,董一鸿. 延迟容忍网络中基于邻居信息精确度的查询算法[J]. 电信科学, 2014, 30(4): 100-108.
[9]	李金双,李凤云. 移动社会网络中用户相似性计算的隐私保护研究[J]. 电信科学, 2013, 29(10): 119-122.
[10]	黄辉,杨秀平,杨秀敏,卿晓春. 面向密集城区网络的覆盖预测模型的应用研究[J]. 电信科学, 2012, 28(6): 151-160.
[11]	金欣,王晶,沈奇威. 自中心网络生成的高效分布式设计与实现[J]. 电信科学, 2010, 26(11): 85-88.