Graph Alignment is a software project I have been developing for the Lässig [externer Link] and Berg [externer Link] groups at the Institute of Theoretical Physics [externer Link] at the University of Cologne. Graph Alignment is an extension module for the R programming environment [externer Link], written partly in C and partly in R. Its purpose is to find similarities in two networks by calculating an alignment between the nodes. In biology, this can be applied to identify similarities of interactions in gene and protein networks across multiple species.
Input data consists of two networks with arbitrary link strengths, represented by adjacency matrices, node similarity scores and discrete representations of the scoring functions to be used. The alignment is then found by maximizing a scoring function using the linear assignment algorithm [externer Link] created and implemented by R. Jonker and A. Volgenant (University of Amsterdam) iteratively. The result of the process is a permutation which maps nodes from the first network to nodes in the second network. Helper functions are provided to calculate optimal scoring parameters, an initial alignment and example input data.
The Graph Alignment package is currently in testing phase and will be available for download soon. Please note that use of the package is restricted to academic purposes only because of licensing of the LAP code.