University of Konstanz
Graduiertenkolleg / PhD Program
Computer and Information Science

Mirza Klimenta

Doctoral Student in the PhD program from 01.11.2009 to 31.03.13.

advisors

1. Prof. Dr. Ulrik Brandes
2. Dr. Andreas Karrenbauer

organisational data

E-mail: klimenta "at" inf.uni-konstanz.de
picture

project description

As a fundamental model for inter-object relation exploration, networks are often visualized to convey the underlying structural properties. The visualization schemes are usually a subject to certain (aesthetic) requirements, appropriately handled in the field of graph drawing concerned with network's (graph) object geometric position reconstruction. Effective drawings are most often a result of specific energy model optimization, the objective common to other fields, such as the Multidimensional Scaling (MDS) - a family of techniques for analyzing data about proximity and similarity. Applied Classical MDS and its approximations, namely Pivot MDS and Landmark MDS, all based on spectral decomposition, appear to represent the global graph structure well, but for the local structure emphasis it should be proceeded with iterative stress minimization. Among many approaches, in the context of graph drawing the preferred optimization strategy is based on majorization: an approach guaranteed to converge to (locally) minimal energy solution.

Our focus is, in part, on the basic model extension and adaptation, consequently satisfying different visualization constraints. Adapting one of the most widely used MDS energy models (stress) has already shown acceptable results (ie. radial graph drawing), but further research tailored for a specific constraint is needed. In particular, we investigate the constraint of minimizing the area consumed by the drawing (still preserving the graph's global structure), possibility of adapting the model to centrality drawings, and focusing (visual emphasis of) certain parts of the graph. Although different MDS models might be subjected with constraints, the comparison of implications is missing.
In addition, our results show that some of the problems imposed by the application of stress MDS model to graph drawing might be avoided by weight and distance engineering, both being important optimization parameters.

Another focal point of the research is based on the time and space complexity problems of the underlying algorithms, as the growing complexity of the networks makes current methods inefficient.
The improvements should allow processing input graphs with millions of nodes and edges on relatively standard equipment.

Currently, our work addresses optimal initialization of the energy model minimization process leading to faster subsequent convergence. In particular, we show that the global scale of the initial solution is of great importance, and provide solutions optimal for most cases. In addition, we explore the model based on restricted information that might lead to acceptable solutions, yet providing substantial time and space complexity gains. Incorporating the restricted model with local node update might lead to further computational speed improvements, but might compromise the resulting quality. The problems of in-between energy model transition are also addressed.

publications

The following list of publications covers only those, which are or were published during participation at the Graduiertenkolleg / PhD program.

Conference Papers

2012

Phd Theses

2012