Metaheuristics for Network Alignment: An Integrative View

The Network Alignment problem is an NP-complete Combinatorial Optimization problem in graphs. The goal is to find an alignment between the input networks, i.e., a mapping between their respective nodes, such that the topological and functional structure is well preserved. During the last decades, many methods have been proposed for solving the problem. However, many of them are designed only for specific areas and applications. In this thesis, we propose AntNetAlign, a new Ant Colony Optimization Algorithm for solving the Network Alignment problem with an integrative view. The key novelties of this approach are the following. First, it can incorporate any pairwise node similarity information to guide the construction process. This similarity is not restricted to any specific kind, allowing for high versatility while applying our method in different contexts. Second, it combines this similarity metric with an improvement measure that depends on the current state of the construction, thus providing both a global and local view of the undergoing construction process. Third, it is able to optimize any of the three considered topological quality measures. And fourth, it is complemented with three different selection strategies. The experimental results obtained over a real-world set of Protein-Protein Interaction networks show that out algorithm is able to outperform other state-of-the-art algorithms from the literature in two out of three of the tested scores. More specifically, our method obtains significantly better results in the superior S3 score in a reasonable amount of time. Moreover, AntNetAlign obtains nearly-optimal solutions when aligning networks with themselves. Additional experimental results show that the good performance of our algorithm may be justified by its high resistance to noise