Spectral reconstruction of networks using combinatorial optimization algorithms

Abstract

In this paper we study the reconstruction of a network topology from the eigenvalues of its Laplacian matrix. We introduce a new simple cost function and consider three combinatorial optimization methods - simulated annealing, tabu search, and multiagent optimization (ants)- while comparing their performance when reconstructing different categories of networks --random, regular, small-world, scale-free and clustered-- from their eigenvalues. We show that tabu search provides more accurate reconstructions than the other methods, while all the algorithms considered allow an exact reconstruction of small networks and lead to good approximations in the case of networks with larger orders.