{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:1321099"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:1321099","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Graph partitioning under the spectral lens","abstract":"Η εύρεση υποκείμενων προτύπων σε δεδομένα είναι ένα θεμελιώδες καθήκον για επιστήμονες στα μαθηματικά και την πληροφορική, ενώ η σημασία της ομαδοποίησης και του διαχωρισμού των δεδομένων έχει αυξηθεί δραματικά την τελευταία δεκαετία. Σε αυτή την εργασία παρουσιάζουμε το ταξίδι ενός από τα πιο βασικά προβλήματα της περιοχής: το 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 πιστεύουμε ότι η προσέγγισή μας αποτελεί μια νέα, πιο εύκολη απόδειξη για ένα πολύ πρόσφατο αποτέλεσμα.","abstract_html":"Η εύρεση υποκείμενων προτύπων σε δεδομένα είναι ένα θεμελιώδες καθήκον για επιστήμονες στα μαθηματικά και την πληροφορική, ενώ η σημασία της ομαδοποίησης και του διαχωρισμού των δεδομένων έχει αυξηθεί δραματικά την τελευταία δεκαετία. Σε αυτή την εργασία παρουσιάζουμε το ταξίδι ενός από τα πιο βασικά προβλήματα της περιοχής: το 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 πιστεύουμε ότι η προσέγγισή μας αποτελεί μια νέα, πιο εύκολη απόδειξη για ένα πολύ πρόσφατο αποτέλεσμα.","abstract_has_math":false,"creators":["Κοιλιάρης Κωνσταντίνος"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015","date_published":"2015","updated_at":"2026-11-19T05:26:38Z","subjects":[],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1321099"],"render_values":[{"text":"uoadl:1321099","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1321099","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1321099","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A1321099","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Κοιλιάρης Κωνσταντίνος"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2015"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1321099","https://pergamos.lib.uoa.gr/uoa/dl/object/1321099"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Η εύρεση υποκείμενων προτύπων σε δεδομένα είναι ένα θεμελιώδες καθήκον για επιστήμονες στα μαθηματικά και την πληροφορική, ενώ η σημασία της ομαδοποίησης και του διαχωρισμού των δεδομένων έχει αυξηθεί δραματικά την τελευταία δεκαετία. Σε αυτή την εργασία παρουσιάζουμε το ταξίδι ενός από τα πιο βασικά προβλήματα της περιοχής: το 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 πιστεύουμε ότι η προσέγγισή μας αποτελεί μια νέα, πιο εύκολη απόδειξη για ένα πολύ πρόσφατο αποτέλεσμα.","Finding underlying structure in data has been a fundamental task for mathematicians, computer- and now data-scientists and the importance of clustering and partitioning data has increased dramatically in the past decade. We present the journey of one of the most essential problems in the area: Graph Partitioning. We begin with the importance and the wide range of applications it finds, the computational difficulties involved in solving it efficiently and the inapproximability results tied to it. We demonstrate the first average case analysis approaches using random models, the most prominent of which is the planted partition model or stochastic block model where the graph has k equally sized blocks and vertices connect independently with probability p within blocks and q across blocks. Recently, a large amount of research in computer science and statistics has been invested in providing lower-bounds on the scaling of |p  q| to ensure recovery of the planted blocks (partitions). We focus on the seminal results using spectral techniques and provide a high level overview of this rapidly evolving area, including the recent information-theoretic perspective threshold on the |p  q| range for recovery. Finally, give our own spectral approach for solving Graph Partitioning for arbi- trary k in the planted partition model and albeit not improving the state-of-the-art we believe our approach constitutes a new, easier proof for a very recent result."]},{"key":"dc:title","label":"Title","values":["Graph partitioning under the spectral lens"]}]}],"canonical_facts":{"dc:creator":["Κοιλιάρης Κωνσταντίνος"],"dc:date":["2015"],"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 πιστεύουμε ότι η προσέγγισή μας αποτελεί μια νέα, πιο εύκολη απόδειξη για ένα πολύ πρόσφατο αποτέλεσμα.","Finding underlying structure in data has been a fundamental task for mathematicians, computer- and now data-scientists and the importance of clustering and partitioning data has increased dramatically in the past decade. We present the journey of one of the most essential problems in the area: Graph Partitioning. We begin with the importance and the wide range of applications it finds, the computational difficulties involved in solving it efficiently and the inapproximability results tied to it. We demonstrate the first average case analysis approaches using random models, the most prominent of which is the planted partition model or stochastic block model where the graph has k equally sized blocks and vertices connect independently with probability p within blocks and q across blocks. Recently, a large amount of research in computer science and statistics has been invested in providing lower-bounds on the scaling of |p  q| to ensure recovery of the planted blocks (partitions). We focus on the seminal results using spectral techniques and provide a high level overview of this rapidly evolving area, including the recent information-theoretic perspective threshold on the |p  q| range for recovery. Finally, give our own spectral approach for solving Graph Partitioning for arbi- trary k in the planted partition model and albeit not improving the state-of-the-art we believe our approach constitutes a new, easier proof for a very recent result."],"dc:identifier":["uoadl:1321099","https://pergamos.lib.uoa.gr/uoa/dl/object/1321099"],"dc:language":["English"],"dc:title":["Graph partitioning under the spectral lens"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:26:38Z"}