A layout algorithm for visualization of graph alignments

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümü, Türkiye

Tezin Onay Tarihi: 2017

Öğrenci: ANDAÇ AKARSU

Danışman: TOLGA CAN

Özet:

Graph layout algorithms are commonly used when visualizing. Usually these algorithms focus on a single graph. To be able to visualize multiple graphs at once, such as the results of graph alignment algorithms on biological networks, new layout algorithms need to be developed. A layout algorithm for visualizing graph alignments should display the aligned graphs separately, so that both the graphs and their alignment can be viewed individually. In addition, for better interpretation of the alignment results, similar to single graph layout algorithms, edge crossings should be minimized and highly connected subsets of nodes should be grouped together. In this thesis, we propose a graph layout heuristic for visualization of alignments of two graphs. The list of aligned nodes, ordered with respect to node similarity, is taken as input from the graph alignment algorithm. The nodes are re-ordered using an approach adapted from a solution to the minimum linear arrangement problem. The nodes are then placed using their degrees. The proposed layout algorithm is applied on biological networks and the resulting layouts are assessed for quality using the number of edge crosses, a standard measure for evaluating layout algorithms. Our results show that the proposed algorithm performs better for graph alignment visualization compared to standard layout algorithms.