Dominance-based knowledge discovery from large-scale attributed data

Abstract

This thesis establishes dominance relationships as a unifying and flexible mechanism for analyzing multi-attribute data in graphs and high-dimensional spaces, bypassing the need for rigid metric assumptions. It demonstrates this versatility across three core tasks, beginning with a skyline-based dissimilarity approach for high-dimensional image descriptors that captures intrinsic variation and utilizes hashing-based indexing for scalability. Second, it introduces DomiCom, a dimension-agnostic framework that merges exact or approximate domination scores with k-core decomposition to detect cohesive, attribute-significant, and optionally overlapping top-k dominant communities in attributed networks. Finally, it extends this reasoning to local community search, employing both hop-based and random-walk strategies guided by domination scores and maximum k-cores to build high-quality communities around user-specified query nodes. Supported by algorithmic formulations, theoretical analyses, and extensive experiments on real datasets, the research proves that dominance is a robust foundation for multi-criteria reasoning and new algorithm design in complex data environments.

Η παρούσα διατριβή καθιερώνει τις σχέσεις κυριαρχίας ως έναν ενοποιητικό και ευέλικτο μηχανισμό για την ανάλυση δεδομένων πολλαπλών χαρακτηριστικών σε γράφους και χώρους υψηλών διαστάσεων, παρακάμπτοντας την ανάγκη για αυστηρές μετρικές παραδοχές. Η ευελιξία αυτή καταδεικνύεται μέσα από τρεις βασικές εργασίες, ξεκινώντας με μια προσέγγιση ανομοιότητας βασισμένη σε τεχνικές skyline για περιγραφείς εικόνων υψηλών διαστάσεων, η οποία καταγράφει την εγγενή διακύμανση και αξιοποιεί δεικτοδότηση μέσω κατακερματισμού (hashing) για κλιμάκωση (scalability). Δεύτερον, εισάγει το DomiCom, ένα ανεξάρτητο διαστάσεων πλαίσιο που συνδυάζει ακριβείς ή προσεγγιστικές βαθμολογίες κυριαρχίας με την χρήση k-core, για τον εντοπισμό συνεκτικών, σημαντικών ως προς τα χαρακτηριστικά και δυνητικά επικαλυπτόμενων top-k κυρίαρχων κοινοτήτων σε δίκτυα με χαρακτηριστικά. Τέλος, επεκτείνει αυτή τη λογική στην αναζήτηση τοπικών κοινοτήτων, εφαρμόζοντας στρατηγικές βασισμένες σε άλματα (hop-based) καθώς και σε τυχαίους περιπάτους (random-walks), οι οποίες καθοδηγούνται από βαθμολογίες κυριαρχίας και μέγιστα k-cores για τη δημιουργία κοινοτήτων υψηλής ποιότητας γύρω από κόμβους-ερωτήματα που καθορίζει ο χρήστης. Υποστηριζόμενη από αλγοριθμικές διατυπώσεις, θεωρητικές αναλύσεις και εκτενή πειράματα σε πραγματικά σύνολα δεδομένων, η έρευνα αποδεικνύει ότι η κυριαρχία αποτελεί ένα ισχυρό θεμέλιο για συλλογιστική πολλαπλών κριτηρίων και σχεδιασμό νέων αλγορίθμων σε πολύπλοκα περιβάλλοντα δεδομένων.