基于演化深度强化学习的符号网络影响最大化研究
作者:
作者单位:

作者简介:

马里佳(1990-),男,博士,助理教授,主要研究领域为演化计算,深度学习,复杂网络结构与行为分析;洪华平(1998-),男,硕士生,主要研究领域为深度学习,复杂网络结构分析;林秋镇(1984-),男,博士,副教授,主要研究领域为演化计算,多目标优化;李坚强(1980-),男,博士,教授,博士生导师,CCF专业会员,主要研究领域为人工智能,机器人,物联网,移动医疗.;公茂果(1979-),男,博士,教授,博士生导师,CCF高级会员,主要研究领域为计算智能理论与方法,网络信息感知与隐私保护,雷达与遥感智能系统.

通讯作者:

李坚强,lijq@szu.edu.cn

中图分类号:

TP18

基金项目:

国家自然科学基金(U1713212, 61672358, 61572330, 61772393, 61836005); 广东省自然科学基金(2017A030313338); 国家重点研发计划(2020YFA0908700)


Influence Maximization for Signed Networks Based on Evolutionary Deep Reinforcement Learning
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    近年来, 随着互联网信息传播以及新型冠状病毒COVID-19传播链阻断等重大应用问题的出现, 社会网络影响最大化问题的研究受到了科学界广泛关注. 影响最大化问题旨在根据特定应用问题的传播模型, 识别出最优影响种子节点集, 最大化其信息传播影响. 现有影响最大化算法主要针对单连接影响传播模型, 将影响最大化问题模拟为离散的影响力种子节点组合选取优化问题. 然而, 这些算法具有较高的计算时间复杂度, 且无法解决具有大规模冲突关系的符号网络影响最大化问题. 针对上述问题, 首先, 构建适用于符号网络的正负影响传播模型以及影响最大化优化模型. 其次, 通过引入由神经网络构成的deep Q network来选取种子节点集, 将离散的种子节点组合选取问题转化为更易优化的网络权重连续优化问题. 最后, 提出基于演化深度强化学习的符号网络影响最大化算法SEDRL-IM. 该算法将演化算法的个体视作策略, 结合演化算法的无梯度全局搜索以及强化学习的局部搜索特性, 实现对deep Q network权重优化问题解的有效搜索, 从而找到最优影响种子节点集. 在基准符号网络以及真实社交网络数据集上的大量实验结果表明, 所提算法在影响传播范围与求解效率上都优于经典的基准算法.

    Abstract:

    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.

    参考文献
    相似文献
    引证文献
引用本文

马里佳,洪华平,林秋镇,李坚强,公茂果.基于演化深度强化学习的符号网络影响最大化研究.软件学报,2023,34(11):5084-5112

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2021-12-03
  • 最后修改日期:2022-02-09
  • 录用日期:
  • 在线发布日期: 2023-05-18
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号