Network Reconstruction from Betweenness Centrality by Artificial Bee Colony

Abstract Reconstructing complex network structures from measurable data has become a central issue in contemporary network science and engineering. In this paper, we tackle the reconstruction of the network topology from a set of target betweenness centrality values. This metric evaluates the participation of the vertices in the communication along the shortest paths of the network and it has been widely used as centrality measure in analyzing social networks. In this case, the network reconstruction task is formulated as an optimization problem whose search space consists of all possible subsets of edges linking a given set of vertices. It should be noted that the development of optimization algorithms 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 innovative design decisions (not explored previously in the literature): firstly, to address the problem by proposing an artificial bee colony algorithm, which is a potent swarm intelligence metaheuristic inspired in the foraging behavior of honeybees 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. Extensive experiments verify that our optimizer can achieve better solution quality than the state-of-the-art metaheuristic for this complex optimization problem and other competing algorithms. We have completed the study of the proposal by evaluating its behavior as tool to reconstruct network topology.