Houssame Hajji

Houssame Hajji has a background in Mathematics Physics and Computer Science. He is currently pursuing a MSc in Management and IT at the University of St Andrews as well as a MSc in Mathematics and Computer Science at the Toulouse Institute of Technology. For his dissertation, Houssame is supervised by Professor Aaron Quigley. You can contact Houssame at hmh5@st-andrews.ac.uk.
Dissertation Title: Clustering and Force Directed Graph Layouts
Force directed (or Spring) algorithms view a graph as a virtual physical system where the nodes of the graph are bodies of the system. These bodies have forces acting on or between them. Often the forces are physics-‐based, and therefore have a natural analogy, such as magnetic repulsion or gravitational attraction. Almost any information visualisation toolkit, graph layout system or tool that uses graphs, includes a method for force directed layout. As such, it is a standard graph layout technique. Classical algorithms are quadratic (and hence don’t scale well). Advances in the past decade by Quigley and Koren have seen this reduced to n log n (or less). These improvements mean these methods can layout the nodes of very large graphs interactively, rather than waiting hours or days for the layout to compute. However, when considering graphs of thousands, tens of thousands or millions of nodes, the positioning of the nodes of the graph is but a small part of the problem. How to route the edges? How to cluster the graph (thereby reducing the number of visual elements to display)? How to blend multi-views or hyper-graphs remain open research and development problems. How to manage a steady flow of changes to the nodes, edges, forces or clustering which can dramatically effect the ideal layout of the nodes from one time step to the next?