Please use this identifier to cite or link to this item: http://hdl.handle.net/10889/12116
Title: Advanced graph analytics focusing on centrality analysis and graph similarity
Other Titles: Προηγμένες τεχνικές ανάλυσης γράφων με έμφαση στην ανάλυση κεντρικότητας και ομοιότητας
Authors: Χριστοφιδέλλης, Δημήτριος
Keywords: Graph analytics
Subgraph centrality
Graph similarity
Chebyshev expansion
Knowledge Graphs
Stochastic diagonal estimator
Keywords (translated): Ανάλυση γράφων
Ομοιότητα γράφων
Γράφοι γνώσης
Στοχαστικός διαγώνιος εκτιμητής
Abstract: In this era of Big Data, large graphs are ubiquitous and the design and implementation of tools for conducting Graph Analytics is a very active area of research and development. Two major tasks in Graph Analytics are evaluating the importance of graph vertices by means of suitable centrality metrics and similarity assessment of different graphs. In this thesis, tools are developed for these tasks that are based on matrix computations and randomized techniques. The focus is on undirected graphs, therefore the underlying matrices are symmetric. The functions of interest are the computation of subgraph centralities based on the matrix exponential and assessing graph similarity based on the histogram of the eigenvalues of suitable transformations of the corresponding adjacency matrices. For the latter problem, the method adopted relies on counting eigenvalues lying in specific bins of the histogram using the trace of a suitable matrix boxcar function. In both cases, therefore, the objective is to compute a value or subset of values depending on a special matrix function. The mathematical framework and the tools developed are described and evaluated on test graphs obtained from well known repositories as well as on two large problems arising in analysis of Knowledge Graphs for information retrieval in the area of geology as well as a graph describing airport connectivity matrix in commercial aviation. The tools described in this work were incorporated in the HP-KG platform at IBM Research Zurich. A brief presentation of this platform and its utilizations, mainly in the field of Knowledge Graphs, as well as how the thesis enhanced this platform are presented.
Abstract (translated): Στην εποχή «Μεγάλων Δεδομένων» την οποία διανύουμε, είναι παντού παρόντες μεγάλου μεγέθους γράφοι και ο σχεδιασμός, η υλοποίηση και η εφαρμογή εργαλείων για την ανάλυσή τους έχει εξελιχθεί σε ένα πολύ ενεργό τομέα έρευνας. Δύο σημαντικές διαδικασίες στην ανάλυση γράφων είναι η αξιολόγηση της σημασίας των κόμβων των γράφων μέσω κατάλληλων μετρικών κεντρικότητας και η εκτίμηση της ομοιότητας διαφορετικών γράφων. Στην παρούσα διπλωματική αναπτύσσονται εργαλεία για τις δύο αναφερόμενες διαδικασίες που βασίζονται σε υπολογισμούς μητρώων και σε τυχαιοποιημένες τεχνικές. Οι λειτουργίες που ενδιαφέρουν είναι ο υπολογισμός της κεντρικότητας υπογράφου (subgraph centrality) με βάση την εκθετική συνάρτηση μητρώου και η εκτίμηση της ομοιότητας γράφων που βασίζεται στο ιστόγραμμα των ιδιοτιμών των μητρώων γειτνίασης. Για το τελευταίο πρόβλημα, η μέθοδος που υιοθετήθηκε βασίζεται στην καταμέτρηση των ιδιοτιμών που βρίσκονται σε συγκεκριμένα εύρη του ιστoγράμματος, χρησιμοποιώντας το ίχνος μιας κατάλληλης boxcar συνάρτησης μητρώου. Επομένως, και στις δύο περιπτώσεις, ο στόχος είναι να υπολογιστεί μια τιμή ή ένα υποσύνολο τιμών που εξαρτάται από μια ειδική συνάρτηση μητρώου. Οι τεχνικές που παρουσιάζονται αφορούν πρωτίστως μη κατευθυνόμενους γράφους και κατά συνέπεια τα μητρώα που προκύπτουν είναι συμμετρικά. Το μαθηματικό πλαίσιο και τα εργαλεία που αναπτύχθηκαν περιγράφονται και αξιολογούνται σε πραγματικούς γράφους που λαμβάνονται από γνωστά αποθετήρια, σε ένα πρόβλημα που αφορά σε Γράφους Γνώσης για την ανάκτηση πληροφοριών στον τομέα της γεωλογίας και ένα πρόβλημα που αφορά στην αξιολόγηση αεροδρομίων βάσει της συνδεσιμότητάς τους μέσω εμπορικών πτήσεων. Τα εργαλεία που περιγράφονται έχουν ενσωματωθεί στη βιβλιοθήκη KG για Graph Analytics που αναπτύσσεται στα εργαστήρια της IBM Research Zurich.
Appears in Collections:Τμήμα Μαθηματικών (ΜΔΕ)

Files in This Item:
File Description SizeFormat 
christofidellis_thesis.pdf3.84 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.