Model and Algorithms for Competitiveness Maximization on Complex Networks

In this paper we study a competition model on complex networks, where two competing agents are fixed to different states while other agents are evolving to update their states through interactions according to a distributed consensus rule. We consider the situation where one competitor has the opportunity to add new links to other evolving agents such that it could improve its influence on the number of its supporters. We focus on the problem of how to add these new links in order to maximize the influence of a competitor against its rival, referred to as competitiveness. We formulate this competition as a competitiveness maximization problem, which tries to maximize the number of supports of a given competitor against its rival. We analyze the properties of this problem on some special graphs and provide optimal solutions for them, respectively. We design a simulated annealing algorithm and three heuristic algorithms to approximately solve this NP-hard constrained optimization problem.