Aristotle University Of Thessaloniki (AUTH)
Efficient analysis of local and global structures in large networks
Abstract
dc:descriptionThis 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.
Degree
thesis:*- Grantor dc:publisher
- Aristotle University Of Thessaloniki (AUTH)
- Year dc:date
- 2022
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Floros, Dimitrios
- Φλώρος, Δημήτριος
Subjects
dc:subject × 14- Ανάλυση δικτύων και γράφων
- Κατανομές γραφιδίων
- Συσταδοποίηση σε γράφους
- Εύρεση κοινοτήτων
- Graphlet distributions
- Community detection
- Network & graph analysis
- Graph clustering
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- Επιστήμες Μηχανικού και Τεχνολογία
- Υπολογιστές, Υλικό (hardware) και Αρχιτεκτονική
- Electrical Engineering, Electronic Engineering, Information Engineering
- Engineering and Technology
- Computer science, Hardware and Architecture
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/52905