Mirza Klimenta
Doctoral Student in the PhD program since 01.11.2009.
advisors1. Prof. Dr. Ulrik Brandes2. Dr. Andreas Karrenbauer organisational data
|
 |
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.
publications
The following list of publications covers only those, which are or were published during participation at the Graduiertenkolleg / PhD program.
Currently no publications.