Aligning graphs and finding substructures by message passing
by
Hamed Mahmoudi(Helsinki University of Technology)
→
Europe/Stockholm
FB52
FB52
Description
In recent years, the theory of the networks has gained an important role
in studying complex systems, ranging from molecular biology to social and
technical networks. One interesting issue in this context is graph
alignment problem where the goal is to find a matching of two graphs in
a way that as many edges as possible are matched. Various known fundamental
problems in combinatorial optimization such as the traveling salesman problem, the graph isomorphism and the maximum cliques, can be rewritten
in terms of graph alignment. In this talk a message-passing algorithm will
be introduced to study the graph-alignment and maximum-clique problem.
As a proof of concept the algorithm is applied in a biology to detect to
co evolution between interacting protein domain families in bacterial
signal transduction.