Μελέτη εξάπλωσης ιών σε δίκτυα

• Κύριος συγγραφέας: Ράπτη, Αγγελική
• Άλλοι συγγραφείς: Τσακαλίδης, Αθανάσιος
• Μορφή: Thesis
• Γλώσσα: Greek
• Έκδοση: 2015
• Θέματα: Ιοί ηλεκτρονικών υπολογιστών; Εξάπλωση ιών; Δυναμικό σύστημα; Σταθερό σημείο; Επιδημιολογικό κατώφλι; Computer viruses; Propagation; Dynamical system; Fixed point; Epidemic threshold; 005.84

Η έννοια των δικτύων εμφανίζεται πολύ συχνά με διάφορες μορφές. Δίκτυο μπορούμε να θεωρήσουμε ένα σύνολο υπολογιστών που συνδέονται μεταξύ τους υπακούοντας σε κάποιο πρωτόκολλο επικοινωνίας αλλά και μια ομάδα ανθρώ- πων που συνδέονται μέσω κάποιας κοινωνικής σχέσης, ενός εργασιακού χώρου αλλά και ως χρήστες ενός forum ή μίας πλατφόρμας κοινωνικής δικτύωσης. Σε οποιαδήποτε περίπτωση, ένα δίκτυο μπορεί να αναπαρασταθεί με τη μορφή ενός γράφηματος, όπου οι κόμβοι αναπαριστούν τα άτομα/υπολογιστές και οι ακμές τη μεταξύ τους σχέση ανάλογα με το πρόβλημα. Στα πλαίσια ενός τέτοιου δικτύου μας ενδιαφέρει η συμπεριφορά των κόμβων στην περίπτωση που συμβεί ένα γεγονός που αλλάζει την κατάστασή τους. Στην περίπτωση που αναφερόμαστε σε μία κοινωνική ομάδα ή μία πόλη, αυτό το φαι- νόμενο μπορεί να είναι το ξέσπασμα μίας επιδημίας που εξαπλώνεται στο δίκτυο αλλά και μίας είδησης/φήμης, όπου ενημερώνεται το δίκτυο. Στην πρώτη περί- πτωση, μας ενδιαφέρει να περιορίσουμε την επιδημία, αλλάζοντας τοπολογικά το δίκτυο ενώ στη δεύτερη περίπτωση, είναι επιθυμητό να διευκολύνουμε την εξά- πλωση της είδησης, έτσι ώστε να ενημερωθούν όσο το δυνατόν, περισσότεροι κόμβοι(χρήστες). Η συμπεριφορά του δικτύου σε ένα τέτοιο φαινόμενο, μπορεί να προσομοιωθεί από ένα δυναμικό σύστημα. Με τον όρο δυναμικό σύστημα αναφερόμαστε σε ένα σύστημα που έχει ένα σύνολο καταστάσεων, όπου κάθε κατάσταση, προκύπτει σε συνάρτηση με την προηγούμενη. Παραδείγματα εφαρμογής ενός δυναμικού συστήματος σε δίκτυο, εμφανίζονται σε διάφορους τομείς όπως στην οικολογία, τη διάχυση πληροφορίας, το viral marketing, την επιδημιολογία. Τα δυναμικά συστήματα που προσομοιώνουν τη συμπεριφορά του δικτύου σε τέτοια φαινόμενα, χρησιμοποιούν επιδημιολογικά μοντέλα για να περιγρά- ψουν τις δυνατές καταστάσεις στις οποίες μπορεί να περιέλθει ένας κόμβος. Στη συγκεκριμένη εργασία, χρησιμοποιήσαμε το μοντέλο SIS (Susceptible-Infected-Susceptible) [8].Το μοντέλο SIS δηλώνει ότι ένας κόμβος μπορεί να είναι είτε επιρρεπής στο να ασθενήσει (susceptible) είτε ασθενής (infected). Αυτό σημαί- νει πως ένας κόμβος δεν θεραπεύεται ποτέ πλήρως αλλά υπάρχει πιθανότητα να ασθενήσει πάλι. Με βάση τη βιβλιογραφία, σε ένα τέτοιο δυναμικό σύστημα, αναζητούμε κά- ποια σημεία (fixed points) στα οποία το σύστημα θα ισορροπεί. Υπάρχουν σημεία τα οποία είναι σημεία ισορροπίας αλλά δεν είναι σταθερά. Σε αυτά τα σημεία, το σύστημα μπορεί στιγμιαία να ισορροπήσει αλλά ξεφεύγει πολύ εύκολα από αυτό. Αναζητούμε συνεπώς, σταθερά σημεία ισορροπίας, τα λεγόμενα stable fixed points. Έχει αποδειχτεί [6] ότι μπορούμε σε αυτά στα σημεία να καθορίσουμε τις απαραίτητες συνθήκες για να είναι σταθερά, περιορίζοντας τη μέγιστη ιδιοτιμή του μητρώου γειτνίασης που περιγράφει το δίκτυο. Ορίζονται δηλαδή κατώφλια (thresholds) κατά περίπτωση, που περιορίζουν την μέγιστη ιδιοτιμή του δικτύου με τέτοιο τρόπο ώστε το σύστημα, να βρίσκεται σε κατάσταση ισορροπίας. Στην πε- ρίπτωση που αναφερόμαστε στο φαινόμενο της επιδημίας, στόχος είναι στο αντί- στοιχο σημείο ισορροπίας η μέγιστη ιδιοτιμή να είναι κάτω του κατωφλίου, έτσι ώστε να εξασφαλίσουμε τον περιορισμό εξάπλωσης της επιδημίας στο δίκτυο. Στην περίπτωση που αναφερόμαστε σε μία είδηση ή ένα ανταγωνιστικό προϊόν, η μέγιστη ιδιοτιμή θέλουμε να είναι άνω του αντίστοιχου κατωφλίου έτσι ώστε να έχουμε εξάπλωση στο δίκτυο. Επομένως ανάλογα με την περίπτωση, αντιμε- τωπίζουμε διαφορετικά τα κατώφλια που υπολογίζονται για το αντίστοιχο σημείο ισορροπίας. Στα πλαίσια της μεταπτυχιακής εργασίας, χρησιμοποιήσαμε το μοντέλο SIS για να περιγράψουμε το φαινόμενο όπου ένας ιός εξαπλώνεται σε ένα δίκτυο όπου οι κόμβοι του δικτύου, έχουν διαφορετική ευαισθησία απέναντί του. Πραγματο- ποιήσαμε μαθηματική περιγραφή του μοντέλου, ορίζοντας τα απαραίτητα κατώ- φλια έτσι ώστε το σύστημα να ισορροπεί ανάλογα με το σημείο ισορροπίας αλλά και το είδος του γραφήματος. Επίσης, πραγματοποιήσαμε προσομοίωση του μο- ντέλου σε συνθετικά γραφήματα (κλίκα, αυθαίρετο γράφημα κ.α), επαληθεύοντας τη συμπεριφορά που υποδεικνύει το μαθηματικό μοντέλο.