Analysis and visualization of directed graphs

Abstract

The display of Graphs, is widely used for the visualization of data or information. Although it is important to show all the information represented by the edges and the nodes of the graph, there are cases where this is either impossible due to the complexity and the size of the graphs or even misleadingsince the graph could be very dense, while other reasons may be related to privacy protection (e.g.,social network graphs). To overcome this challenge, different approaches imply to hide the unnecessary or redundant information or even replace the original graph with a subgraph or a summary. The main objective of this dissertation is to investigate and elaborate on the visualization and analysis of large graphs. More specifically, regarding visualization we design and implement variousversions of a new sophisticated framework of graph layout techniques that focus on the idea of improving the visualization aesthetics, in order to reduce the visualization complexity of the graph, on top of sophisticated graph drawing layouts. These techniques can be categorized in two main groups.The first category is with respect to bends while the second is based on edge removal. To this respect, we perform a set of experiments that show that these techniques produce progressively more abstract drawings of the input graph. No dummy vertices are introduced and the vertices of each path/channel are vertically aligned. Subsequently, the value of the introduced approach is that it also provides ageneric and parameterized visualization method based on the given scenario. Towards this direction, wealso elaborate on methods for grouping nodes with similar characteristics that naturally decomposes the graph based on the information derived by the edges within the graph, which can be used in order tohave better visualization of complex networks. In order to evaluate our drawing layout techniques, we assess the usability of various versions of our new layout compared with the one produced by other hierarchical drawing techniques. As a result,we provide insights regarding the factors that affect efficiency so introduce a set of metrics in order to evaluate the performance of these techniques. Our algorithms require almost linear time. Moreover, we design and conduct a comparative task-based evaluation with users in which we ask the participants to carry them out in order to extract the user's satisfaction level and exploit any possible problems and difficulties as regards the reachability information. Generally, the drawings produced by our algorithms have lower number of bends and are significantly smaller in area. The user evaluation also reveals thatthe performance of the participants is slightly better in the drawings of our proposed model and that our model is preferred in overall rating compared to the other model.

Η απεικόνιση των Γράφων, χρησιμοποιείται ευρέως για την οπτικοποίηση δεδομένων ή πληροφοριών.Αν και είναι σημαντικό να εμφανίζονται όλες οι πληροφορίες που αντιπροσωπεύονται από τις ακμές και τους κόμβους του γράφου, υπάρχουν περιπτώσεις όπου αυτό είναι είτε αδύνατο λόγω της πολυπλοκότητας και του μεγέθους του γράφου ή ακόμα και παραπλανητικό. Αυτό έγκειται στο γεγονός ότι οι εν λόγω γράφοι ενδέχεται να είναι αρκετά πυκνοί, ενώ άλλες περιπτώσεις σχετίζονται με προσωπικά δεδομένα και την ιδιωτικότητα (π.χ. κοινωνικά δίκτυα). Για να ξεπεραστεί αυτή η πρόκληση, διαφορετικές προσεγγίσεις σχετίζονται με την απόκρυψη της περιττής ή πλεονάζουσας πληροφορίας ή ακόμα και τη μερική αντικατάσταση του αρχικού γράφου με υπογράφο ή με μια περίληψη αυτού. Ο βασικός στόχος της παρούσας διατριβής είναι η λεπτομερής διερεύνηση περί οπτικοποίησης και ανάλυσης μεγάλων γράφων. Πιο συγκεκριμένα, αναφορικά με την οπτικοποίηση, σχεδιάζουμε και υλοποιούμε μια σειρά από διαφορετικές προσεγγίσεις ενός νέου μοντέλου γραφικής αναπαράστασης που εστιάζουν στην βελτίωση της γραφικής αναπαράστασης, προκειμένου να μειωθεί η οπτική πολυπλοκότητα του γραφήματος, πάνω από εξελιγμένες τεχνικές σχεδίασης για γράφους. Οι τεχνικές αυτές μπορούν να κατηγοριοποιηθούν σε δύο κύριες ομάδες. Η πρώτη κατηγορία σχετίζεται με τις γωνίες ενώ η δεύτερη με την αφαίρεση άκρων. Τα πειραματικά αποτελέσματα ανέδειξαν ότι αυτές οι τεχνικές παράγουν προοδευτικά πιο αφαιρετικά γραφήματα. Δεν εισάγονται εικονικοί κόμβοι και οι κόμβοι κάθε διαδρομής/καναλιού είναι κάθετα ευθυγραμμισμένοι. Η αξία της προσέγγισής μας είναι ότι παρέχει μια γενική αλλά παραμετροποιήσιμη μέθοδο οπτικοποίησης συναρτήσει του δοθέντος σεναρίου. Επιπροσθέτως, ασχολούμαστε με μεθόδους ομαδοποίησης κόμβων με παρόμοια χαρακτηριστικά, οι οποίες ομαδοποιούν τον γράφο βάσει των πληροφοριών που προέρχονται από τις ακμές, και οι οποίες μπορούν να χρησιμοποιηθούν για την καλύτερη οπτικοποίηση πολύπλοκων δικτύων. Προκειμένου, να αξιολογήσουμε τις τεχνικές σχεδιαστικής διάταξης, συγκρίνουμε τη χρηστικότητα των αποτελεσμάτων διαφόρων εκδόσεων του νέου μας μοντέλου με τα αντίστοιχα αποτελέσματα που παράγονται από παρόμοιες τεχνικές ιεραρχικής σχεδίασης. Ως αποτέλεσμα, τονίζουμε τις γενικές κατευθυντήριες γραμμές και παρέχουμε πληροφορίες σχετικά με τους παράγοντες της αποτελεσματικότητας. Οι τεχνικές μας απαιτούν σχεδόν γραμμικό χρόνο. Επιπλέον, σχεδιάζουμε και εφαρμόζουμε μία συγκριτική αξιολόγηση βασισμένη σε Δραστηριότητες με χρήστες, προκειμένου να εξαγάγουμε το επίπεδο ικανοποίησής τους καθώς και να αναδείξουμε τα όποια πιθανά προβλήματα και δυσκολίες. Τα αποτελέσματα αναδεικνύουν ότι τα γραφήματα βάσει του προτεινόμενου μοντέλου μας, έχουν μικρότερο αριθμό γωνιών και απαιτούν σημαντικά μικρότερη γεωμετρική περιοχή ενώ το μοντέλο μας προτιμάται στη συνολική βαθμολογία σε σύγκριση με το άλλο μοντέλο.