Manipulating Black-Box Networks for Centrality Promotion

Centrality measures are widely used to map each node to its importance in a network. For many practical applications, vital nodes bearing high centrality scores have superior positions over other nodes. To benefit from the positive impact of becoming a vital node, the problem of improving the centrality of the target node has attracted increasing attention. Many existing studies attack this problem by directly increasing the centrality score of the target node on the premise of knowing the network structure. However, these methods suffer from privacy issues due to their dependence on the network structure and may lose their effectiveness because other nodes can simultaneously increase the scores. Therefore, in this paper, we explore the following question: given a black-box network whose structure is unknown, is it possible to improve the centrality ranking (rather than the score) of a target node by implementing certain strategies? We provide an affirmative answer to this question. First, to avoid relying on the network structure for promotion, we propose strategies that freeze the original graph while appending nodes and edges just around the target node. Second, to guide strategies for effectively boosting centrality, we devise two principles that provide the target node with either the maximum gain or the minimum loss of centrality scores over other nodes. We prove that a strategy meeting the proposed principles is guaranteed to upgrade the target node's ranking. Extensive experiments were conducted to verify the effectiveness of the proposed strategies on black-box networks.