A Layout algorithm for visualization of graph alignments

Download

index.pdf

Date

2017

Author

Akarsu, Andaç

Metadata

Show full item record

Item Usage Stats

172
views

81
downloads

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.

Subject Keywords

Graph theory., Graph algorithms., Computer graphics.

URI

http://etd.lib.metu.edu.tr/upload/12620838/index.pdf
https://hdl.handle.net/11511/26356

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

A Customized force-directed layout algorithm for biological graphs whose vertices have enzyme commission attributes Danacı, Hasan Fehmi; Atalay, Mehmet Volkan; Department of Computer Engineering (2015) Force directed layout algorithm is popularly used to draw biological graphs. However, it employs only graph structure. When we would like to embed domain-specific knowledge, such as biological or chemical attributes related to the vertices, force directed layout algorithm should be modified. It is then important to draw more readable layouts for biologists without the dispose of aesthetically pleasing way that comes from force-directed algorithm’s nature. This thesis aims to describe a modified and improved...
The Floyd-Warshall all-pairs shortest paths algorithm for disconnected and very sparse graphs Toroslu, İsmail Hakkı (2023-01-01) The Floyd-Warshall algorithm is the most popular algorithm for determining the shortest paths between all vertex pairs in a graph. It is a very simple and an elegant algorithm. However, for graphs without any negative weighted edges, using Dijkstra's shortest path algorithm for every vertex as a source vertex to produce all-pairs shortest paths works significantly better than the Floyd-Warshall algorithm, especially for large graphs. Furthermore, for graphs with negative weighted edges, with no negative cyc...
A Customized force-directed layout algorithm with genetic algorithm techniques for biological graphs whose vertices have enzyme commission attributes Aksoydan, Fırat; Atalay, Mehmet Volkan; Department of Computer Engineering (2019) A pathway can be visualized as a graph whose layout is drawn by a force-directed algorithm. In our previous study, we have described EClerize which is a customized and improved Kamada Kawai force-directed algorithm in order to visualize pathways that contain nodes with attributes as EC numbers. EClerize creates clusters of vertices with enzymes that belong to the same EC class. Here, we make use of genetic algorithm (GA) to obtain a global optimum solution for EClerize and we integrate undirected graph layo...
A MAP-Based Approach for Hyperspectral Imagery Super-Resolution IRMAK, Hasan; Akar, Gözde; Yuksel, Seniha Esen (Institute of Electrical and Electronics Engineers (IEEE), 2018-06-01) In this paper, we propose a novel single image Bayesian super-resolution (SR) algorithm where the hyperspectral image (HSI) is the only source of information. The main contribution of the proposed approach is to convert the ill-posed SR reconstruction problem in the spectral domain to a quadratic optimization problem in the abundance map domain. In order to do so, Markov random field based energy minimization approach is proposed and proved that the solution is quadratic. The proposed approach consists of f...
The static stochastic knapsack problem with normally distributed item sizes Merzifonluoglu, Yasemin; Geunes, Joseph; Romeijn, H. Edwin (Springer Science and Business Media LLC, 2012-09-01) This paper develops exact and heuristic algorithms for a stochastic knapsack problem where items with random sizes may be assigned to a knapsack. An item's value is given by the realization of the product of a random unit revenue and the random item size. When the realization of the sum of selected item sizes exceeds the knapsack capacity, a penalty cost is incurred for each unit of overflow, while our model allows for a salvage value for each unit of capacity that remains unused. We seek to maximize the ex...

Citation Formats

A. Akarsu, “A Layout algorithm for visualization of graph alignments,” M.S. - Master of Science, Middle East Technical University, 2017.