Similarity in temporal graphs
Φόρτωση...
Ημερομηνία
Συγγραφείς
Κουρσούμης, Αντώνιος
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
In all modern networks, calculating metrics and ranking nodes according to their
inherent characteristics is a vital part of their analysis. It helps by providing information
of the structure of the network, the association and importance of nodes, as
well as presenting characteristics and information of the network itself. The main
problem lies in redefining already existent models and algorithms that are built for
static networks to also apply their calculations, effectively, on networks that evolve
over time. This must not be done by completely excluding node structure or other
information they already include but by extending them to also calculate temporal
metrics. Such a change is essential due to the amount of data being extracted everyday
whose components include rich temporal information. This work focuses on
altering distance, diameter and centrality metrics as well as the SimRank algorithm to
fit temporal data extracted from two different datasets restructured in three different
graph implementations; an undirected, a directed and a bipartite one. The resulting
definitions, models and implementations are analyzed and ranking algorithms were
used to evaluate their significance.
Με την εξέλιξη των αυτόματων εργαλείων συλλογής δεδομένων, η δυνατότητα μας να δημιουργούμε και να αποθηκεύουμε πληροφορία έχει αυξηθεί δραματικά τις τελευταίες δεκαετίες. Μεγάλο μέρος αυτής της πληροφορίας χρησιμοποιεί την δομή γράφων για την οργάνωση των δεδομένων. Οι γράφοι αποτελούν ένα κεντρικό κομμάτι της σύγχρονης εποχής. Υπάρχουν παντού. Πολλοί από αυτούς αλλάζουν συνεχώς με το πέρασμα του χρόνου. Βασικότερα παραδείγματα αυτής της εξέλιξης είναι τα πληροφοριακά δίκτυα του διαδικτύου και τα κοινωνικά δίκτυα που περιέ- χουν εκατομμύρια ή και δισεκατομμύρια ακμές και κόμβους. Η ανάλυση τέτοιων γράφων, που αντιπροσωπεύουν τέτοιο πλήθος εξελισσόμενης και διασυνδεδεμένης πληροφορίας, βρίσκει πολλαπλές εφαρμογές. Η ανάλυση δομών στα σύγχρονα κοι- νωνικά δίκτυα, η μελέτη καταναλωτικών προτύπων σε ηλεκτρονικά καταστήματα και η ανάλυση των αλληλεπιδράσεων πρωτεϊνών σε βιοϊατρικά δίκτυα είναι λίγα μόνο παραδείγματα. Στον τομέα των γράφων, υπάρχει μεγάλο πλήθος αλγορίθμων που κύριο σκοπό έχουν την εξαγωγή μετρικών και την κατάταξη στοιχείων του γράφου ανάλογα με αυτές. Παρόλα αυτά, οι γράφοι αυτοί δεν περιέχουν καμία πληροφορίας σχετικά με την εξέλιξη των στοιχείων τους στην πάροδο του χρόνου. Σε αυτή την εργασία, αναλύονται πολλαπλοί τρόποι μετατροπής τέτοιων αλγορίθμων και δομών, με κύριο στόχο την εφαρμογή τους σε γράφους οι οποίοι εξελίσσονται στον χρόνο. Τέτοιοι γράφοι περιέχουν πληροφορία που δεν μπορεί να εξαχθεί με την χρήση των στατι- κών αλγορίθμων. Αρχικά αναλύεται η δυνατότητα μετατροπής ενός από τους κυριότερους αλγορίθμους μέτρησης ομοιότητας κόμβων σε γράφους, του SimRank, προκειμένου να εξάγει την ίδια πληροφορία, αποτελεσματικά, από χρονικά εξελισσόμενους γράφους. Στη συνέχεια μελετώνται, με τον ίδιο στόχο, αλγόριθμοι για την μέτρηση απόστασης, κεντρικότητας και διαμέτρου. Τέλος, παρουσιάζονται τα αποτελέσματα αυτών των μετατροπών και αναλύεται η αποτελεσματικότητά τους μέσω της εφαρμογής τους σε πραγματικά, εξελισσόμενα δεδομένα. Κύριος στόχος αυτής της εργασίας είναι να παρουσιάσει την σημαντικότητα της με- τατροπής υπαρχόντων αλγορίθμων ώστε να δουλεύουν σε εξελισσόμενα δεδομένα καθώς και της αποτελεσματικότητα μίας τέτοιας μετατροπής.
Με την εξέλιξη των αυτόματων εργαλείων συλλογής δεδομένων, η δυνατότητα μας να δημιουργούμε και να αποθηκεύουμε πληροφορία έχει αυξηθεί δραματικά τις τελευταίες δεκαετίες. Μεγάλο μέρος αυτής της πληροφορίας χρησιμοποιεί την δομή γράφων για την οργάνωση των δεδομένων. Οι γράφοι αποτελούν ένα κεντρικό κομμάτι της σύγχρονης εποχής. Υπάρχουν παντού. Πολλοί από αυτούς αλλάζουν συνεχώς με το πέρασμα του χρόνου. Βασικότερα παραδείγματα αυτής της εξέλιξης είναι τα πληροφοριακά δίκτυα του διαδικτύου και τα κοινωνικά δίκτυα που περιέ- χουν εκατομμύρια ή και δισεκατομμύρια ακμές και κόμβους. Η ανάλυση τέτοιων γράφων, που αντιπροσωπεύουν τέτοιο πλήθος εξελισσόμενης και διασυνδεδεμένης πληροφορίας, βρίσκει πολλαπλές εφαρμογές. Η ανάλυση δομών στα σύγχρονα κοι- νωνικά δίκτυα, η μελέτη καταναλωτικών προτύπων σε ηλεκτρονικά καταστήματα και η ανάλυση των αλληλεπιδράσεων πρωτεϊνών σε βιοϊατρικά δίκτυα είναι λίγα μόνο παραδείγματα. Στον τομέα των γράφων, υπάρχει μεγάλο πλήθος αλγορίθμων που κύριο σκοπό έχουν την εξαγωγή μετρικών και την κατάταξη στοιχείων του γράφου ανάλογα με αυτές. Παρόλα αυτά, οι γράφοι αυτοί δεν περιέχουν καμία πληροφορίας σχετικά με την εξέλιξη των στοιχείων τους στην πάροδο του χρόνου. Σε αυτή την εργασία, αναλύονται πολλαπλοί τρόποι μετατροπής τέτοιων αλγορίθμων και δομών, με κύριο στόχο την εφαρμογή τους σε γράφους οι οποίοι εξελίσσονται στον χρόνο. Τέτοιοι γράφοι περιέχουν πληροφορία που δεν μπορεί να εξαχθεί με την χρήση των στατι- κών αλγορίθμων. Αρχικά αναλύεται η δυνατότητα μετατροπής ενός από τους κυριότερους αλγορίθμους μέτρησης ομοιότητας κόμβων σε γράφους, του SimRank, προκειμένου να εξάγει την ίδια πληροφορία, αποτελεσματικά, από χρονικά εξελισσόμενους γράφους. Στη συνέχεια μελετώνται, με τον ίδιο στόχο, αλγόριθμοι για την μέτρηση απόστασης, κεντρικότητας και διαμέτρου. Τέλος, παρουσιάζονται τα αποτελέσματα αυτών των μετατροπών και αναλύεται η αποτελεσματικότητά τους μέσω της εφαρμογής τους σε πραγματικά, εξελισσόμενα δεδομένα. Κύριος στόχος αυτής της εργασίας είναι να παρουσιάσει την σημαντικότητα της με- τατροπής υπαρχόντων αλγορίθμων ώστε να δουλεύουν σε εξελισσόμενα δεδομένα καθώς και της αποτελεσματικότητα μίας τέτοιας μετατροπής.
Περιγραφή
Λέξεις-κλειδιά
Ομοιότητα, Γραφήματα, Χρονικά γραφήματα, Μετρικές, Similarity, Graphs, Temporal graphs, Metrics
Θεματική κατηγορία
Graphic methods
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Όνομα επιβλέποντος
Πιτουρά, Ευαγγελία
Εξεταστική επιτροπή
Πιτουρά, Ευαγγελία
Τσαπάρας, Παναγιώτης
Μαμουλής, Νικόλαος
Τσαπάρας, Παναγιώτης
Μαμουλής, Νικόλαος
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Πίνακας περιεχομένων
Χορηγός
Βιβλιογραφική αναφορά
Βιβλιογράφία : σ. 56-57
Ονόματα συντελεστών
Αριθμός σελίδων
57 σ.