A Study Of Influence Maximization Based On Reinforcement Learning

Social network analysis is one of the most important branches in artificial intelli-gence.Influence maximization in social network has long been studied,and researchers have proposed many models and algorithms for this problem.Currently,researches on influence maximization mainly focu on static strategies to select nodes according to the target scope of influence and other constraints,rather than dynamic strategies to optimize the impact.As a result,since the states of the network are ever-changing,these static strategies could end up performing poorly.This paper discusses the optimization strategies based on reinforcement learning models.Since the agents in reinforcement learning learn themselves according to the historical interaction with the environment,which is time-dependent,the reinforcement learning algorithm could become the dynamic strategy that satisfies the given constraints,and gives the optimized impact result.In addition,we could set the reward in reinforce-ment learning to control the costs in activating seed nodes when optimizing the impact.As a result,we propose that reinforcement learning could be a better approach for this type of optimization problem.With reinforcement learning,this paper divides the problem of influence maximiza-tion into two subproblems: influence maximization with a single agent,and influence maximization with multi-agent.To create dynamic strategies for the single-agent opti-mization problem,first we could treat this problem as a dynamic planning problem with Markov property and construct the reinforcement learning framework.Then we may se-lect the best algorithm for simulation.Compared with the algorithms for solving static strategies,the experimental results of reinforcement learning have obvious advantages.Since influence maximization is an NP-hard problem,the dynamic solution of influence maximization with multi-agent would be even harder,and there are little research on it currently.For influence maximization with multi-agent,this paper uses DQN algorithm based on Self-play,Nash Q Learning algorithm,and Nash DQN algorithm to solve the optimization problem with multiple agents.The DQN algorithm according to Self-play is fit for situations when the agents perform actions sequentially,and could reduce the optimization problem of multiple agents to optimization problem of two agents.Nash Q Learning algorithm is fit for smaller networks and could make sure it converges to the Nash-equilibrium strategy.Nash DQN algorithm would get the approximate solution to Nash equilibrium with neural networks,and is fit for networks of larger size.The opti-mization of multiple competing agents is very complex.As a result,although the algo-rithm proposed in this paper does not perform very well on large-size networks,it provides a brand new approach for solving influence maximization problem with multi-agent.