摘要
近年来,随着互联网信息传播以及新型冠状病毒COVID-19传播链阻断等重大应用问题的出现,社会网络影响最大化问题的研究受到了科学界广泛关注.影响最大化问题旨在根据特定应用问题的传播模型,识别出最优影响种子节点集,最大化其信息传播影响.现有影响最大化算法主要针对单连接影响传播模型,将影响最大化问题模拟为离散的影响力种子节点组合选取优化问题.然而,这些算法具有较高的计算时间复杂度,且无法解决具有大规模冲突关系的符号网络影响最大化问题.针对上述问题,首先,构建适用于符号网络的正负影响传播模型以及影响最大化优化模型.其次,通过引入由神经网络构成的deep Q network来选取种子节点集,将离散的种子节点组合选取问题转化为更易优化的网络权重连续优化问题.最后,提出基于演化深度强化学习的符号网络影响最大化算法SEDRL-IM.该算法将演化算法的个体视作策略,结合演化算法的无梯度全局搜索以及强化学习的局部搜索特性,实现对deep Q network权重优化问题解的有效搜索,从而找到最优影响种子节点集.在基准符号网络以及真实社交网络数据集上的大量实验结果表明,所提算法在影响传播范围与求解效率上都优于经典的基准算法.
In recent years,the research on influence maximization(IM)for social networks has attracted extensive attention from the scientific community due to the emergence of major application issues,such as information dissemination on the Internet and the blocking of COVID-19’s transmission chain.IM aims to identify a set of optimal influence seed nodes that would maximize the influence of information dissemination according to the propagation model for a specific application issue.The existing IM algorithms mainly focus on unidirectional-link influence propagation models and simulate IM issues as issues of optimizing the selection of discrete influence seed node combinations.However,they have a high computational time complexity and cannot be applied to solve IM issues for signed networks with large-scale conflicting relationships.To solve the above problems,this study starts by building a positive-negative influence propagation model and an IM optimization model readily applicable to signed networks.Then,the issue of selecting discrete seed node combinations is transformed into one of continuous network weight optimization for easier optimization by introducing a deep Q network composed of neural networks to select seed node sets.Finally,this study devises an IM algorithm based on evolutionary deep reinforcement learning for signed networks(SEDRL-IM).SEDRL-IM views the individuals in the evolutionary algorithm as strategies and combines the gradient-free global search of the evolutionary algorithm with the local search characteristics of reinforcement learning.In this way,it achieves the effective search for the optimal solution to the weight optimization issue of the Deep Q Network and further obtains the set of optimal influence seed nodes.Experiments are conducted on the benchmark signed network and real-world social network datasets.The extensive results show that the proposed SEDRL-IM algorithm is superior to the classical benchmark algorithms in both the influence propagation range and the solution efficiency.
作者
马里佳
洪华平
林秋镇
李坚强
公茂果
MA Li-Jia;HONG Hua-Ping;LIN Qiu-Zhen;LI Jian-Qiang;GONG Mao-Guo(School of Computer Science and Software Engineering,Shenzhen University,Shenzhen 518060,China;School of Electronic Engineering,Xidian University,Xi’an 710071,China)
出处
《软件学报》
EI
CSCD
北大核心
2023年第11期5084-5112,共29页
Journal of Software
基金
国家自然科学基金(U1713212,61672358,61572330,61772393,61836005)
广东省自然科学基金(2017A030313338)
国家重点研发计划(2020YFA0908700)。
关键词
符号网络
影响最大化
演化算法
深度强化学习
signed network
influence maximization(IM)
evolutionary algorithm(EA)
deep reinforcement learning(DRL)
