Back to search

National and Kapodistrian University of Athens

Graph partitioning under the spectral lens

Abstract

dc:description

Η εύρεση υποκείμενων προτύπων σε δεδομένα είναι ένα θεμελιώδες καθήκον για επιστήμονες στα μαθηματικά και την πληροφορική, ενώ η σημασία της ομαδοποίησης και του διαχωρισμού των δεδομένων έχει αυξηθεί δραματικά την τελευταία δεκαετία. Σε αυτή την εργασία παρουσιάζουμε το ταξίδι ενός από τα πιο βασικά προβλήματα της περιοχής: το Graph Partitioning. Ξεκινάμε με τη σημασία και το ευρύ φάσμα των εφαρμογών που βρίσκει, τις υπολογιστικές δυσκολίες που εμπλέκονται στην επίλυσή του αποτελεσματικά και τα αποτέλεσμα μη προσεγγισιμότητας που συνδέονται με αυτό. Παρουσιάζουμε τις πρώτες average-case αναλύσεις χρησιμοποιώντας τυχαία μοντέλα, το σημαντικότερο εκ των οποίων είναι το planted partition model ή αλλιώς stochastic block model, όπου το γράφημα έχει k ισομεγέθη μέρη και οι κορυφές συνδέονται ανεξάρτητα με πιθανότητα p εντός των μερών και q ανάμεσα σε διαφορετικά μπλοκ. Πρόσφατα, ένα μεγάλο μέρος της έρευνας στην επιστήμη των υπολογιστών και της στατιστικής έχει επενδυθεί στην εύρεση κάτω φραγμάτων για την τιμή του | p - q | ώστε να διασφαλιστεί η εύρεση των φυτεμένων μερών. Επικεντρωνόμαστε στα κύρια αποτελέσματα που κάνουν χρήση φασματικών τεχνικών και παρέχουν μια επισκόπηση υψηλού επιπέδου αυτού του ταχέως εξελισσόμενου τομέα, συμπεριλαμβανομένου του πρόσφατου αποτελέσματος ορίου του | p - q | εύρος για την ανάκαμψη, βασισμένο σε τεχνικές θεωρίας πληροφοριών. Τέλος, δίνουμε τη δική μας φασματική προσέγγιση για την επίλυση του Graph Partitioning για αυθαίρετες τιμές του k στο planted partition model και αν και δεν βελτιώνουμε το state-of-the-art πιστεύουμε ότι η προσέγγισή μας αποτελεί μια νέα, πιο εύκολη απόδειξη για ένα πολύ πρόσφατο αποτέλεσμα.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Κοιλιάρης Κωνσταντίνος

Rights

Language dc:language
English

Identifiers

dc:identifier.*
Identifier
uoadl:1321099

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Κοιλιάρης Κωνσταντίνος. Graph partitioning under the spectral lens. 2015. https://pergamos.lib.uoa.gr/uoa/dl/object/1321099