{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:2935329"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:2935329","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Time Evolving Graph Compression","abstract":"Σύγχρονα συστήματα επεξεργασίας δεδομένων που δίνουν δυνατότητες αλληλεπίδρασης και μοντελοποιούν συσχετισμούς μεταξύ χρηστών παίζουν αποφασιστικό ρόλο στη σημερινή εποχή. Τροφοδοτούν καθημερινές ανθρώπινες δραστηριότητες, βοηθούν στον καθορισμό της παγκόσμιας επικοινωνίας και συμβάλλουν στη δημιουργία και διαχείριση δικτύων κοινοτήτων. Τέτοια δίκτυα αναπαρίστανται κατά κύριο λόγο με τη χρήση γράφων, τα μεγέθη των οποίων έχουν παρουσιάσει εκθετικές αυξήσεις κατά τη διάρκεια της περασμένης δεκαετίας. Τα μεγέθη αυτά εμποδίζουν την έγκαιρη ανάλυση τέτοιων δικτύων λόγω περιορισμών σε μνήμη αλλά και ιδιαίτερων απαιτήσεων I/O. Με τη χρήση τεχνικών συμπίεσης γράφων έχει επιτευχθεί μείωση της απαιτούμενης μνήμης για την αναπαράσταση τέτοιων δικτύων χρησιμοποιώντας μερικά bits­ανά­ακμή. Αντίστοιχες προσεγγίσεις προσφέρουν σύντομες και περιεκτικές απεικονίσεις για κοινωνικά, βιολογικά και πληροφοριακά δίκτυα, ενώ ταυτόχρονα επιτρέπουν αποδοτική πρόσβαση σε συγκεκριμένα στοιχεία του γράφου προς αναζήτηση. Παρά την επιτυχία τους, τέτοιες μέθοδοι επικεντρώνουν την προσοχή τους κυρίως σε στατικούς γράφους και προσφέρουν πρόσβαση μονάχα σε ένα στιγμιότυπο ή σε συγκεντρωτικά χαρακτηριστικά ενός δικτύου. Στην πραγματικότητα όμως, τα δίκτυα εξελίσσονται διαρκώς με την πάροδο του χρόνου και σε πολλές περιπτώσεις είναι αναγκαία η αποτύπωση αυτής της εξέλιξης. Σε αυτή τη διπλωματική εργασία προτείνουμε ένα framework για τη συμπίεση τέτοιων χρονικά εξελισσόμενων γράφων, το οποίο βασίζεται σε μια δυϊκή αναπαράσταση στην οποία εμπεριέχονται η δομή του δικτύου, καθώς και η συναφής χρονική πληροφορία. Αν και εκμεταλλευόμαστε αρκετές δομικές ιδιότητες δικτύων που συναντώνται στην πραγματικότητα, εισάγουμε και εκμεταλλευόμαστε επίσης εμπειρικά παρατηρημένες ιδιότητες σχετικά με τη χρονική τους διάσταση. Η ανάλυση και η πειραματική αξιολόγηση που διεξάγουμε δείχνουν ότι το προτεινόμενο framework αποδίδει πολύ καλύτερα από άλλες γνωστές τεχνικές ίδιου σκοπού, ενώ ταυτόχρονα επιτυγχάνει σημαντικές βελτιώσεις στις αναλογίες συμπίεσης οι οποίες σε μερικές περιπτώσεις πέφτουν κάτω από το μισό άλλων προσεγγίσεων τελευταίας τεχνολογίας. Ταυτόχρονα, η αποδοτική ως προς τη μνήμη αναπαράσταση που προτείνεται, καταφέρνει πάνω από 60% πιο γρήγορη συμπίεση γράφων καθώς και πολλαπλών τάξεων μεγέθους γρηγορότερες επερωτήσεις πάνω στα στοιχεία των αντίστοιχων γράφων, ειδικά για δίκτυα μεγάλης κλίμακας. Εν τέλει, το framework που προτείνεται είναι η πρώτη εις γνώσιν μας προσπάθεια συμπίεσης χρονικά εξελισσόμενων γράφων που χρησιμοποιεί πραγματικό χρόνο αντί για αριθμημένα χρονικά βήματα. Αυτό βοηθάει στον ορισμό της χρονικής λεπτομέρειας και έχει ως αποτέλεσμα τον καλύτερο έλεγχο του μεγέθους της αναπαράστασης επιτυγχάνοντας ακόμα περισσότερο κέρδος σε μνήμη.","abstract_html":"Σύγχρονα συστήματα επεξεργασίας δεδομένων που δίνουν δυνατότητες αλληλεπίδρασης και μοντελοποιούν συσχετισμούς μεταξύ χρηστών παίζουν αποφασιστικό ρόλο στη σημερινή εποχή. Τροφοδοτούν καθημερινές ανθρώπινες δραστηριότητες, βοηθούν στον καθορισμό της παγκόσμιας επικοινωνίας και συμβάλλουν στη δημιουργία και διαχείριση δικτύων κοινοτήτων. Τέτοια δίκτυα αναπαρίστανται κατά κύριο λόγο με τη χρήση γράφων, τα μεγέθη των οποίων έχουν παρουσιάσει εκθετικές αυξήσεις κατά τη διάρκεια της περασμένης δεκαετίας. Τα μεγέθη αυτά εμποδίζουν την έγκαιρη ανάλυση τέτοιων δικτύων λόγω περιορισμών σε μνήμη αλλά και ιδιαίτερων απαιτήσεων I/O. Με τη χρήση τεχνικών συμπίεσης γράφων έχει επιτευχθεί μείωση της απαιτούμενης μνήμης για την αναπαράσταση τέτοιων δικτύων χρησιμοποιώντας μερικά bits­ανά­ακμή. Αντίστοιχες προσεγγίσεις προσφέρουν σύντομες και περιεκτικές απεικονίσεις για κοινωνικά, βιολογικά και πληροφοριακά δίκτυα, ενώ ταυτόχρονα επιτρέπουν αποδοτική πρόσβαση σε συγκεκριμένα στοιχεία του γράφου προς αναζήτηση. Παρά την επιτυχία τους, τέτοιες μέθοδοι επικεντρώνουν την προσοχή τους κυρίως σε στατικούς γράφους και προσφέρουν πρόσβαση μονάχα σε ένα στιγμιότυπο ή σε συγκεντρωτικά χαρακτηριστικά ενός δικτύου. Στην πραγματικότητα όμως, τα δίκτυα εξελίσσονται διαρκώς με την πάροδο του χρόνου και σε πολλές περιπτώσεις είναι αναγκαία η αποτύπωση αυτής της εξέλιξης. Σε αυτή τη διπλωματική εργασία προτείνουμε ένα framework για τη συμπίεση τέτοιων χρονικά εξελισσόμενων γράφων, το οποίο βασίζεται σε μια δυϊκή αναπαράσταση στην οποία εμπεριέχονται η δομή του δικτύου, καθώς και η συναφής χρονική πληροφορία. Αν και εκμεταλλευόμαστε αρκετές δομικές ιδιότητες δικτύων που συναντώνται στην πραγματικότητα, εισάγουμε και εκμεταλλευόμαστε επίσης εμπειρικά παρατηρημένες ιδιότητες σχετικά με τη χρονική τους διάσταση. Η ανάλυση και η πειραματική αξιολόγηση που διεξάγουμε δείχνουν ότι το προτεινόμενο framework αποδίδει πολύ καλύτερα από άλλες γνωστές τεχνικές ίδιου σκοπού, ενώ ταυτόχρονα επιτυγχάνει σημαντικές βελτιώσεις στις αναλογίες συμπίεσης οι οποίες σε μερικές περιπτώσεις πέφτουν κάτω από το μισό άλλων προσεγγίσεων τελευταίας τεχνολογίας. Ταυτόχρονα, η αποδοτική ως προς τη μνήμη αναπαράσταση που προτείνεται, καταφέρνει πάνω από 60% πιο γρήγορη συμπίεση γράφων καθώς και πολλαπλών τάξεων μεγέθους γρηγορότερες επερωτήσεις πάνω στα στοιχεία των αντίστοιχων γράφων, ειδικά για δίκτυα μεγάλης κλίμακας. Εν τέλει, το framework που προτείνεται είναι η πρώτη εις γνώσιν μας προσπάθεια συμπίεσης χρονικά εξελισσόμενων γράφων που χρησιμοποιεί πραγματικό χρόνο αντί για αριθμημένα χρονικά βήματα. Αυτό βοηθάει στον ορισμό της χρονικής λεπτομέρειας και έχει ως αποτέλεσμα τον καλύτερο έλεγχο του μεγέθους της αναπαράστασης επιτυγχάνοντας ακόμα περισσότερο κέρδος σε μνήμη.","abstract_has_math":false,"creators":["Στέφου Θεόδωρος","Stefou Theodoros"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2021,"date_issued":"2021","date_published":"2021","updated_at":"2026-11-19T05:42:05Z","subjects":["Θετικές Επιστήμες","Science"],"languages":["Ελληνικά","English","Greek"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:2935329"],"render_values":[{"text":"uoadl:2935329","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/2935329","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/2935329","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%3A2935329","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Στέφου Θεόδωρος","Stefou Theodoros"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2021"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Θετικές Επιστήμες","Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["Ελληνικά","English","Greek"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:2935329","https://pergamos.lib.uoa.gr/uoa/dl/object/2935329"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Σύγχρονα συστήματα επεξεργασίας δεδομένων που δίνουν δυνατότητες αλληλεπίδρασης και μοντελοποιούν συσχετισμούς μεταξύ χρηστών παίζουν αποφασιστικό ρόλο στη σημερινή εποχή. Τροφοδοτούν καθημερινές ανθρώπινες δραστηριότητες, βοηθούν στον καθορισμό της παγκόσμιας επικοινωνίας και συμβάλλουν στη δημιουργία και διαχείριση δικτύων κοινοτήτων. Τέτοια δίκτυα αναπαρίστανται κατά κύριο λόγο με τη χρήση γράφων, τα μεγέθη των οποίων έχουν παρουσιάσει εκθετικές αυξήσεις κατά τη διάρκεια της περασμένης δεκαετίας. Τα μεγέθη αυτά εμποδίζουν την έγκαιρη ανάλυση τέτοιων δικτύων λόγω περιορισμών σε μνήμη αλλά και ιδιαίτερων απαιτήσεων I/O. Με τη χρήση τεχνικών συμπίεσης γράφων έχει επιτευχθεί μείωση της απαιτούμενης μνήμης για την αναπαράσταση τέτοιων δικτύων χρησιμοποιώντας μερικά bits­ανά­ακμή. Αντίστοιχες προσεγγίσεις προσφέρουν σύντομες και περιεκτικές απεικονίσεις για κοινωνικά, βιολογικά και πληροφοριακά δίκτυα, ενώ ταυτόχρονα επιτρέπουν αποδοτική πρόσβαση σε συγκεκριμένα στοιχεία του γράφου προς αναζήτηση. Παρά την επιτυχία τους, τέτοιες μέθοδοι επικεντρώνουν την προσοχή τους κυρίως σε στατικούς γράφους και προσφέρουν πρόσβαση μονάχα σε ένα στιγμιότυπο ή σε συγκεντρωτικά χαρακτηριστικά ενός δικτύου. Στην πραγματικότητα όμως, τα δίκτυα εξελίσσονται διαρκώς με την πάροδο του χρόνου και σε πολλές περιπτώσεις είναι αναγκαία η αποτύπωση αυτής της εξέλιξης. Σε αυτή τη διπλωματική εργασία προτείνουμε ένα framework για τη συμπίεση τέτοιων χρονικά εξελισσόμενων γράφων, το οποίο βασίζεται σε μια δυϊκή αναπαράσταση στην οποία εμπεριέχονται η δομή του δικτύου, καθώς και η συναφής χρονική πληροφορία. Αν και εκμεταλλευόμαστε αρκετές δομικές ιδιότητες δικτύων που συναντώνται στην πραγματικότητα, εισάγουμε και εκμεταλλευόμαστε επίσης εμπειρικά παρατηρημένες ιδιότητες σχετικά με τη χρονική τους διάσταση. Η ανάλυση και η πειραματική αξιολόγηση που διεξάγουμε δείχνουν ότι το προτεινόμενο framework αποδίδει πολύ καλύτερα από άλλες γνωστές τεχνικές ίδιου σκοπού, ενώ ταυτόχρονα επιτυγχάνει σημαντικές βελτιώσεις στις αναλογίες συμπίεσης οι οποίες σε μερικές περιπτώσεις πέφτουν κάτω από το μισό άλλων προσεγγίσεων τελευταίας τεχνολογίας. Ταυτόχρονα, η αποδοτική ως προς τη μνήμη αναπαράσταση που προτείνεται, καταφέρνει πάνω από 60% πιο γρήγορη συμπίεση γράφων καθώς και πολλαπλών τάξεων μεγέθους γρηγορότερες επερωτήσεις πάνω στα στοιχεία των αντίστοιχων γράφων, ειδικά για δίκτυα μεγάλης κλίμακας. Εν τέλει, το framework που προτείνεται είναι η πρώτη εις γνώσιν μας προσπάθεια συμπίεσης χρονικά εξελισσόμενων γράφων που χρησιμοποιεί πραγματικό χρόνο αντί για αριθμημένα χρονικά βήματα. Αυτό βοηθάει στον ορισμό της χρονικής λεπτομέρειας και έχει ως αποτέλεσμα τον καλύτερο έλεγχο του μεγέθους της αναπαράστασης επιτυγχάνοντας ακόμα περισσότερο κέρδος σε μνήμη.","Contemporary data­systems that enable the interaction of individuals and model formed associations among users do now play a crucial role. They empower the daily human activity, help shape the global discourse, and assist in creating and managing networks of communities. Routinely such networks are represented with graphs whose growth has been unprecedented during the last decade. This growth hinders the timely analysis of networks due to existing limitations in memory and significant I/O overheads. Graph compression techniques have managed to reduce memory requirements for representing such networks by using a few bits­per­edge. Respective approaches offer succinct mappings for social, biological, and information networks while allowing for the efficient access of sought graph elements. Despite their success, such methods predominantly focus on static graphs, and offer access to merely a snapshot or an aggregated view of a network. In reality however, networks do change over time and, in many instances, we are interested in capturing this evolution. In this master thesis, we propose a framework for compressing such emerging temporal graphs which is based on a dual­representation entailing both the network structure and pertinent temporal information. Although we exploit several known properties when it comes to the structure of real­world networks, we also introduce and capitalize on empirically observed exhibited properties regarding their time aspect(s). Our analysis and experimental evaluation show that the proposed framework greatly outperforms competing approaches while attaining significantly improved compression ratios, that are sometimes less than half of the requirements of state­of­the­art approaches. At the same time, our memory­efficient representation yields more than 60% faster compression of graphs and orders of magnitude quicker retrieval of their respective elements, especially for large­scale networks. Finally, our framework is the first temporal graph compression effort we are aware of, that considers actual time instead of time steps. This helps designate a desired timegranularity and hence, allows us to better control the size of our representation achieving further memory savings."]},{"key":"dc:title","label":"Title","values":["Time Evolving Graph Compression"]}]}],"canonical_facts":{"dc:creator":["Στέφου Θεόδωρος","Stefou Theodoros"],"dc:date":["2021"],"dc:description":["Σύγχρονα συστήματα επεξεργασίας δεδομένων που δίνουν δυνατότητες αλληλεπίδρασης και μοντελοποιούν συσχετισμούς μεταξύ χρηστών παίζουν αποφασιστικό ρόλο στη σημερινή εποχή. Τροφοδοτούν καθημερινές ανθρώπινες δραστηριότητες, βοηθούν στον καθορισμό της παγκόσμιας επικοινωνίας και συμβάλλουν στη δημιουργία και διαχείριση δικτύων κοινοτήτων. Τέτοια δίκτυα αναπαρίστανται κατά κύριο λόγο με τη χρήση γράφων, τα μεγέθη των οποίων έχουν παρουσιάσει εκθετικές αυξήσεις κατά τη διάρκεια της περασμένης δεκαετίας. Τα μεγέθη αυτά εμποδίζουν την έγκαιρη ανάλυση τέτοιων δικτύων λόγω περιορισμών σε μνήμη αλλά και ιδιαίτερων απαιτήσεων I/O. Με τη χρήση τεχνικών συμπίεσης γράφων έχει επιτευχθεί μείωση της απαιτούμενης μνήμης για την αναπαράσταση τέτοιων δικτύων χρησιμοποιώντας μερικά bits­ανά­ακμή. Αντίστοιχες προσεγγίσεις προσφέρουν σύντομες και περιεκτικές απεικονίσεις για κοινωνικά, βιολογικά και πληροφοριακά δίκτυα, ενώ ταυτόχρονα επιτρέπουν αποδοτική πρόσβαση σε συγκεκριμένα στοιχεία του γράφου προς αναζήτηση. Παρά την επιτυχία τους, τέτοιες μέθοδοι επικεντρώνουν την προσοχή τους κυρίως σε στατικούς γράφους και προσφέρουν πρόσβαση μονάχα σε ένα στιγμιότυπο ή σε συγκεντρωτικά χαρακτηριστικά ενός δικτύου. Στην πραγματικότητα όμως, τα δίκτυα εξελίσσονται διαρκώς με την πάροδο του χρόνου και σε πολλές περιπτώσεις είναι αναγκαία η αποτύπωση αυτής της εξέλιξης. Σε αυτή τη διπλωματική εργασία προτείνουμε ένα framework για τη συμπίεση τέτοιων χρονικά εξελισσόμενων γράφων, το οποίο βασίζεται σε μια δυϊκή αναπαράσταση στην οποία εμπεριέχονται η δομή του δικτύου, καθώς και η συναφής χρονική πληροφορία. Αν και εκμεταλλευόμαστε αρκετές δομικές ιδιότητες δικτύων που συναντώνται στην πραγματικότητα, εισάγουμε και εκμεταλλευόμαστε επίσης εμπειρικά παρατηρημένες ιδιότητες σχετικά με τη χρονική τους διάσταση. Η ανάλυση και η πειραματική αξιολόγηση που διεξάγουμε δείχνουν ότι το προτεινόμενο framework αποδίδει πολύ καλύτερα από άλλες γνωστές τεχνικές ίδιου σκοπού, ενώ ταυτόχρονα επιτυγχάνει σημαντικές βελτιώσεις στις αναλογίες συμπίεσης οι οποίες σε μερικές περιπτώσεις πέφτουν κάτω από το μισό άλλων προσεγγίσεων τελευταίας τεχνολογίας. Ταυτόχρονα, η αποδοτική ως προς τη μνήμη αναπαράσταση που προτείνεται, καταφέρνει πάνω από 60% πιο γρήγορη συμπίεση γράφων καθώς και πολλαπλών τάξεων μεγέθους γρηγορότερες επερωτήσεις πάνω στα στοιχεία των αντίστοιχων γράφων, ειδικά για δίκτυα μεγάλης κλίμακας. Εν τέλει, το framework που προτείνεται είναι η πρώτη εις γνώσιν μας προσπάθεια συμπίεσης χρονικά εξελισσόμενων γράφων που χρησιμοποιεί πραγματικό χρόνο αντί για αριθμημένα χρονικά βήματα. Αυτό βοηθάει στον ορισμό της χρονικής λεπτομέρειας και έχει ως αποτέλεσμα τον καλύτερο έλεγχο του μεγέθους της αναπαράστασης επιτυγχάνοντας ακόμα περισσότερο κέρδος σε μνήμη.","Contemporary data­systems that enable the interaction of individuals and model formed associations among users do now play a crucial role. They empower the daily human activity, help shape the global discourse, and assist in creating and managing networks of communities. Routinely such networks are represented with graphs whose growth has been unprecedented during the last decade. This growth hinders the timely analysis of networks due to existing limitations in memory and significant I/O overheads. Graph compression techniques have managed to reduce memory requirements for representing such networks by using a few bits­per­edge. Respective approaches offer succinct mappings for social, biological, and information networks while allowing for the efficient access of sought graph elements. Despite their success, such methods predominantly focus on static graphs, and offer access to merely a snapshot or an aggregated view of a network. In reality however, networks do change over time and, in many instances, we are interested in capturing this evolution. In this master thesis, we propose a framework for compressing such emerging temporal graphs which is based on a dual­representation entailing both the network structure and pertinent temporal information. Although we exploit several known properties when it comes to the structure of real­world networks, we also introduce and capitalize on empirically observed exhibited properties regarding their time aspect(s). Our analysis and experimental evaluation show that the proposed framework greatly outperforms competing approaches while attaining significantly improved compression ratios, that are sometimes less than half of the requirements of state­of­the­art approaches. At the same time, our memory­efficient representation yields more than 60% faster compression of graphs and orders of magnitude quicker retrieval of their respective elements, especially for large­scale networks. Finally, our framework is the first temporal graph compression effort we are aware of, that considers actual time instead of time steps. This helps designate a desired timegranularity and hence, allows us to better control the size of our representation achieving further memory savings."],"dc:identifier":["uoadl:2935329","https://pergamos.lib.uoa.gr/uoa/dl/object/2935329"],"dc:language":["Ελληνικά","English","Greek"],"dc:subject":["Θετικές Επιστήμες","Science"],"dc:title":["Time Evolving Graph Compression"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:42:05Z"}