Flow motifs in interaction networks
Φόρτωση...
Ημερομηνία
Συγγραφείς
Κοσυφάκη, Χρυσάνθη
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
Many real-world phenomena are best represented as interaction networks with
dynamic structures (e.g., transaction networks, social networks, traffic networks). Interaction
Networks capture flow of data which is transferred between their vertices
along a timeline. Analyzing such networks is crucial towards comprehending processes
in them. A typical analysis task is the finding of motifs, which are small
subgraph patterns that repeat themselves in the network.
In this thesis, we introduce network flow motifs, a novel type of motifs that model
significant flow transfer among a set of vertices within a constrained time window.
We design an algorithm for identifying flow motif instances in a large graph. Our
algorithm can be easily adapted to find the top k instances of maximal flow. In addition,
we design a dynamic programming module that finds the instance with the
maximum flow. We evaluate the performance of the algorithm on three real datasets
and identify flow motifs which are significant for these graphs.
Our results show that our algorithm is scalable and that the real networks indeed
include interesting motifs, which appear much more frequently than in randomly
generated networks having similar characteristics.
Πολλά φαινόμενα του πραγματικού κόσμου μπορούν να μοντελοποιηθούν με την βοήθεια των δικτύων αλληλεπίδρασης με δυναμικές δομές (π.χ. δίκτυα συναλλαγών, κοινωνικά δίκτυα, δίκτυα κυκλοφορίας). Τα δίκτυα αλληλεπίδρασης περιλαμβάνουν την ροή δεδομένων που μεταφέρεται μεταξύ των κόμβων του δικτύου κατά μήκος μιας χρονικής γραμμής. Η ανάλυση αυτών των δικτύων είναι ζωτικής σημασίας για την κατανόηση διάφορων διαδικασιών που συμβαίνουν σε αυτά. Ένας τύπος ανάλυ- σης σε αυτά τα δίκτυα είναι η εύρεση μοτίβων, τα οποία είναι μικρά υπογραφήματα που επαναλαμβάνονται μέσα στο δίκτυο. Στην εργασία αυτή εισαγάγουμε τα μοτίβα ροής δικτύου, ένα νέο τύπο μοτίβων που μοντελοποιούν την σημαντική μεταφορά ροής ενός δικτύου μεταξύ ενός συνόλου κόμβων μέσα σε ένα περιορισμένο χρονικό πλαίσιο. Σχεδιάζουμε έναν αλγόριθμο για τον προσδιορισμό των μοτίβων ροής σε ένα μεγάλο γράφημα. Ο αλγόριθμος μας μπορεί εύκολα να προσαρμοστεί και να βρει τα κορυφαία στιγμιότυπα με την μεγα- λύτερη ροή. Επιπλέον σχεδιάζουμε μια ρουτίνα δυναμικού προγραμματισμού που βρίσκει το στιγμιότυπο με την μεγαλύτερη ροή. Αξιολογούμε την απόδοση του αλ- γορίθμου σε τρια πραγματικά σύνολα δεδομένων και προσδιορίζουμε μοτίβα ροής που είναι σημαντικά για αυτά τα γραφήματα. Τα αποτελέσματα μας δείχνουν ότι ο αλγοριθμός μας είναι κλιμακώσιμος και ότι τα πραγματικά δίκτυα περιλαμβάνουν όντως ενδιαφέροντα μοτίβα, τα οποία εμφανίζονται πολύ συχνότερα σε αυτά σε σχέση με τυχαία παραγόμενα δίκτυα που έχουν παρόμοια χαρακτηριστικά.
Πολλά φαινόμενα του πραγματικού κόσμου μπορούν να μοντελοποιηθούν με την βοήθεια των δικτύων αλληλεπίδρασης με δυναμικές δομές (π.χ. δίκτυα συναλλαγών, κοινωνικά δίκτυα, δίκτυα κυκλοφορίας). Τα δίκτυα αλληλεπίδρασης περιλαμβάνουν την ροή δεδομένων που μεταφέρεται μεταξύ των κόμβων του δικτύου κατά μήκος μιας χρονικής γραμμής. Η ανάλυση αυτών των δικτύων είναι ζωτικής σημασίας για την κατανόηση διάφορων διαδικασιών που συμβαίνουν σε αυτά. Ένας τύπος ανάλυ- σης σε αυτά τα δίκτυα είναι η εύρεση μοτίβων, τα οποία είναι μικρά υπογραφήματα που επαναλαμβάνονται μέσα στο δίκτυο. Στην εργασία αυτή εισαγάγουμε τα μοτίβα ροής δικτύου, ένα νέο τύπο μοτίβων που μοντελοποιούν την σημαντική μεταφορά ροής ενός δικτύου μεταξύ ενός συνόλου κόμβων μέσα σε ένα περιορισμένο χρονικό πλαίσιο. Σχεδιάζουμε έναν αλγόριθμο για τον προσδιορισμό των μοτίβων ροής σε ένα μεγάλο γράφημα. Ο αλγόριθμος μας μπορεί εύκολα να προσαρμοστεί και να βρει τα κορυφαία στιγμιότυπα με την μεγα- λύτερη ροή. Επιπλέον σχεδιάζουμε μια ρουτίνα δυναμικού προγραμματισμού που βρίσκει το στιγμιότυπο με την μεγαλύτερη ροή. Αξιολογούμε την απόδοση του αλ- γορίθμου σε τρια πραγματικά σύνολα δεδομένων και προσδιορίζουμε μοτίβα ροής που είναι σημαντικά για αυτά τα γραφήματα. Τα αποτελέσματα μας δείχνουν ότι ο αλγοριθμός μας είναι κλιμακώσιμος και ότι τα πραγματικά δίκτυα περιλαμβάνουν όντως ενδιαφέροντα μοτίβα, τα οποία εμφανίζονται πολύ συχνότερα σε αυτά σε σχέση με τυχαία παραγόμενα δίκτυα που έχουν παρόμοια χαρακτηριστικά.
Περιγραφή
Λέξεις-κλειδιά
Δίκτυα αλληλεπίδρασης, Μοτίβα ροής, Αξιόλογηση, Τέστ σημαντικότης, Interaction networks, Flow motifs, Evaluation, Significance test
Θεματική κατηγορία
Evaluation
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Όνομα επιβλέποντος
Μαμουλής, Νικόλαος
Εξεταστική επιτροπή
Μαμουλής, Νικόλαος
Πιτουρά, Ευαγγελία
Τσαπάρας, Παναγιώτης
Πιτουρά, Ευαγγελία
Τσαπάρας, Παναγιώτης
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Πίνακας περιεχομένων
Χορηγός
Βιβλιογραφική αναφορά
Βιβλιογραφία: σ. 42-44
Ονόματα συντελεστών
Αριθμός σελίδων
48 σ.