Efficient analysis of local and global structures in large networks

Abstract

This dissertation focuses on efficient analysis of local and global structures in networks or graphs. Network analysis is an integral part of data analytics in general. Advanced knowledge of internal structures in networks, or networked data, has improved scientific understanding and led to scientific advances and new discoveries. Yet, there are fundamental limitations in existing computation methods for network structure analysis. (a) Existing methods are limited in scalability with network size. Networks in real-world applications are often large. The complexity and scalability issues are rarely addressed in network analysis literature. (b) More critically, existing methods for detecting community structures suffer in common from the problem with either the resolution limit or resolution tuning. We address and overcome these challenges, theoretically and computationally, in three important structure analysis tasks: (1) computation of graphlet distributions, (2) construction of triangle maps, and (3) detection of multilevel community structures. For Tasks 1 and 2, we have significantly reduced the complexities. We discover reusable or compressible structures adaptively and automatically. For Task 3, we have resolved the long-standing resolution problem, with an original theory for community detection, a.k.a., graph clustering. We have also removed serious speed barriers in optimum search algorithms with a novel methodology. In search for the intrinsic structure at a specified resolution level, we discover and utilize intrinsic structures at finer resolution levels. We enable concurrent search operations with a rich family of graph clustering models. We present our new algorithms and present their superior accuracy-efficiency performance on benchmark data sets, in comparison to state-of-the-art algorithms. We also present several applications of our algorithms to efficient structure analysis of real-world networks, data in network representation, and graphs produced by generative graph models.

Η παρούσα διατριβή εστιάζει στην αποτελεσματική ανάλυση των τοπικών και ολικών δομών σε δίκτυα ή γράφους. Η ανάλυση δικτύων είναι αναπόσπαστο μέρος της ανάλυσης δεδομένων. Η προηγμένη γνώση των εσωτερικών δομών σε δίκτυα, ή σε δικτυακά δεδομένα, έχει οδηγήσει σε σημαντικά επιτεύγματα και ανακαλύψεις. Ωστόσο, υπάρχουν θεμελιώδεις περιορισμοί στις υπάρχουσες υπολογιστικές μεθόδους για την ανάλυση των δομών ενός δικτύου. (αʹ) Οι υπάρχουσες μέθοδοι δεν μπορούν να χειριστούν μεγάλα δίκτυα. Σε εφαρμογές με πραγματικά δεδομένα, τα δίκτυα είναι συχνά τεράστια και αραιά. Η πολυπλοκότητα και τα ζητήματα απόδοσης σπάνια αναφέρονται στην βιβλιογραφία. (βʹ) Οι υπάρχουσες μέθοδοι για τον εντοπισμό κοινοτήτων υποφέρουν από το πρόβλημα είτε με το όριο ανάλυσης ή με την επιλογή της παραμέτρου ανάλυσης. Αντιμετωπίζουμε αυτές τις προκλήσεις, θεωρητικά και υπολογιστικά, σε τρία σημαντικά προβλήματα από την ανάλυση δικτύων: (1) τον υπολογισμό κατανομών γραφιδίων, (2) την εύρεση τριγώνων, και (3) την ανίχνευση δομών κοινοτήτων σε πολλαπλά επίπεδα. Στα προβλήματα 1 και 2, μειώνουμε σημαντικά την υπολογιστική πολυπλοκότητα. Ανακαλύπτουμε επαναχρησιμοποιήσιμες ή συμπιέσιμες δομές, προσαρμοστικά και αυτόματα. Αναφορικά με την ανίχνευση κοινοτήτων, επιλύουμε το μακροχρόνιο πρόβλημα με το όριο της ανάλυσης. Καταργούμε σοβαρά εμπόδια στην ταχύτητα για την αναζήτηση κοινοτήτων. Ανακαλύπτουμε και χρησιμοποιούμε εγγενείς δομές κοινοτήτων σε χαμηλότερα επίπεδα και καθιστούμε δυνατό τον παραλληλισμό κατά την αναζήτηση κοινοτήτων. Παρουσιάζουμε τους νέους μας αλγόριθμους και δείχνουμε πειραματικά την ανώτερη απόδοση τους, τόσο σε ακρίβεια, όσο και σε ταχύτητα, συγκριτικά με τους αλγόριθμους τελευταίας τεχνολογίας. Παρουσιάζουμε επίσης αρκετές εφαρμογές των αλγορίθμων μας για την αποτελεσματική ανάλυση δομών δικτύων σε πραγματικά δεδομένα.