Title

A Layout Algorithm for Visualization of Graph Alignments

Abstract

Abstract

Graph layout algorithms are commonly used to visualize graphs and networks. 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 alignment results and 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.

Biography:

Supervisor(s)

Supervisor(s)

ANDAC AKARSU

Date and Location

Date and Location

2017-01-26;13:30:00-A105

Category

Category

MSc_Thesis