Competitiveness Maximization on Complex Networks
研究了在复杂网络中，一个竞争者通过添加有限数量的新链接来最大化自身影响力的问题，提出了两种竞争力最大化问题，并证明了其中一个是NP难的，另一个可通过贪心算法近似求解。
We consider a model of competition on complex networks, in which two competitors are fixed to opposite states while other agents, called normal agents, adjust their states according to a distributed consensus protocol. Suppose that one of the competitors could enhance its influence by creating new links. A natural question is, when the number of new links is limited due to the limited resource, how to add these links so as to maximize the influence of the given competitor over the other one (called competitiveness). We consider two competitiveness maximization problems: Problem 1 tries to maximize the number of supporters of the competitor, while Problem 2 tries to maximize the total supporting degree of normal agents toward the competitor. We prove that Problem 1 is NP-hard. We also show that the objective function of Problem 2 is monotonous and submodular, and hence there exists a polynomial-time greedy algorithm (GA) approximately solving Problem 2. Several centrality-based heuristic algorithms of less computational burden are also designed to provide approximate solutions to these two problems. We carry out extensive simulations to check the performances of these algorithms in six real networks. We find that GA always provides the best approximate solution to Problem 2, while for Problem 1, GA only has the best performance in directed networks. Furthermore, among those heuristic algorithms, an algorithm based on centrality in descending order is better than its counterpart in ascending order in solving Problem 2 in statistical sense. But for Problem 1, the performance of the centrality-based heuristic algorithms is more sensitive to the network structure and the locations of competitors.