LBCIM: Loyalty Based Competitive Influence Maximization with epsilon-greedy MCTS strategy
This work addresses influence maximization in competitive social networks, such as political campaigns, but is incremental as it builds on existing MCTS methods with specific enhancements.
The paper tackles competitive influence maximization by introducing a new gameboard with loyalty features and an improved Monte Carlo tree search using heuristics and epsilon-greedy selection, showing outperformance against benchmark strategies like general MCTS and minimax with alpha-beta pruning in experiments on synthetic and real datasets.
Competitive influence maximization has been studied for several years, and various frameworks have been proposed to model different aspects of information diffusion under the competitive environment. This work presents a new gameboard for two competing parties with some new features representing loyalty in social networks and reflecting the attitude of not completely being loyal to a party when the opponent offers better suggestions. This behavior can be observed in most political occasions where each party tries to attract people by making better suggestions than the opponent and even seeks to impress the fans of the opposition party to change their minds. In order to identify the best move in each step of the game framework, an improved Monte Carlo tree search is developed, which uses some predefined heuristics to apply them on the simulation step of the algorithm and takes advantage of them to search among child nodes of the current state and pick the best one using an epsilon-greedy way instead of choosing them at random. Experimental results on synthetic and real datasets indicate the outperforming of the proposed strategy against some well-known and benchmark strategies like general MCTS, minimax algorithm with alpha-beta pruning, random nodes, nodes with maximum threshold and nodes with minimum threshold.