Optimizing node infiltrations in complex networks by a local search based heuristic

Abstract

Over the past few years, the task of conceiving effective interventions on complex networks has arisen as different optimization problems. An interesting intervention scheme that has many important real-world applications is to introduce (infiltrate) in a network a certain number of new nodes and connect them to certain existing nodes with the aim of making them as central as possible. The idea is that they should occupy strategic positions in the network to gather a lot of information or to decisively influence others. In this work, we present an optimization problem that concerns the selection of nodes in a network with which to link each of a particular number of infiltrated nodes in order to maximize the lower betweenness centrality value obtained by them. This metric evaluates the participation of the nodes in the communications through the shortest paths of the network and it has been widely used as centrality measure in analyzing social networks. To address the problem, we propose a local search based heuristic whose performance is driven by two search strategies; a constructive greedy procedure that is employed to create an initial solution and a local improvement method that makes use of two neighborhood operators designed for exploring the search space of this problem. It should be noted that the development of metaheuristics for tackling combinatorial problems involving betweenness centrality is very challenging, because this measure is notoriously expensive to compute. That is why we have made two design decisions: firstly, to conceive a very simple metaheuristic approach and secondly, to incorporate in this proposal recent betweenness centrality update techniques that substantially reduce the number of shortest paths which should be re-computed when a network is changed. The performance of our optimizer, with respect to other metaheuristic models from the literature that can be adapted to face this problem, such as a randomized greedy multi-start algorithm and a steady-state genetic algorithm, is empirically shown.