Η έννοια των δικτύων εμφανίζεται πολύ συχνά με διάφορες μορφές. Δίκτυο
μπορούμε να θεωρήσουμε ένα σύνολο υπολογιστών που συνδέονται μεταξύ τους
υπακούοντας σε κάποιο πρωτόκολλο επικοινωνίας αλλά και μια ομάδα ανθρώ-
πων που συνδέονται μέσω κάποιας κοινωνικής σχέσης, ενός εργασιακού χώρου
αλλά και ως χρήστες ενός forum ή μίας πλατφόρμας κοινωνικής δικτύωσης. Σε
οποιαδήποτε περίπτωση, ένα δίκτυο μπορεί να αναπαρασταθεί με τη μορφή ενός
γράφηματος, όπου οι κόμβοι αναπαριστούν τα άτομα/υπολογιστές και οι ακμές τη
μεταξύ τους σχέση ανάλογα με το πρόβλημα.
Στα πλαίσια ενός τέτοιου δικτύου μας ενδιαφέρει η συμπεριφορά των κόμβων
στην περίπτωση που συμβεί ένα γεγονός που αλλάζει την κατάστασή τους. Στην
περίπτωση που αναφερόμαστε σε μία κοινωνική ομάδα ή μία πόλη, αυτό το φαι-
νόμενο μπορεί να είναι το ξέσπασμα μίας επιδημίας που εξαπλώνεται στο δίκτυο
αλλά και μίας είδησης/φήμης, όπου ενημερώνεται το δίκτυο. Στην πρώτη περί-
πτωση, μας ενδιαφέρει να περιορίσουμε την επιδημία, αλλάζοντας τοπολογικά το
δίκτυο ενώ στη δεύτερη περίπτωση, είναι επιθυμητό να διευκολύνουμε την εξά-
πλωση της είδησης, έτσι ώστε να ενημερωθούν όσο το δυνατόν, περισσότεροι
κόμβοι(χρήστες).
Η συμπεριφορά του δικτύου σε ένα τέτοιο φαινόμενο, μπορεί να προσομοιωθεί
από ένα δυναμικό σύστημα. Με τον όρο δυναμικό σύστημα αναφερόμαστε σε ένα
σύστημα που έχει ένα σύνολο καταστάσεων, όπου κάθε κατάσταση, προκύπτει
σε συνάρτηση με την προηγούμενη. Παραδείγματα εφαρμογής ενός δυναμικού
συστήματος σε δίκτυο, εμφανίζονται σε διάφορους τομείς όπως στην οικολογία,
τη διάχυση πληροφορίας, το viral marketing, την επιδημιολογία.
Τα δυναμικά συστήματα που προσομοιώνουν τη συμπεριφορά του δικτύου
σε τέτοια φαινόμενα, χρησιμοποιούν επιδημιολογικά μοντέλα για να περιγρά-
ψουν τις δυνατές καταστάσεις στις οποίες μπορεί να περιέλθει ένας κόμβος. Στη
συγκεκριμένη εργασία, χρησιμοποιήσαμε το μοντέλο SIS (Susceptible-Infected-Susceptible)
[8].Το μοντέλο SIS δηλώνει ότι ένας κόμβος μπορεί να είναι είτε
επιρρεπής στο να ασθενήσει (susceptible) είτε ασθενής (infected). Αυτό σημαί-
νει πως ένας κόμβος δεν θεραπεύεται ποτέ πλήρως αλλά υπάρχει πιθανότητα να
ασθενήσει πάλι.
Με βάση τη βιβλιογραφία, σε ένα τέτοιο δυναμικό σύστημα, αναζητούμε κά-
ποια σημεία (fixed points) στα οποία το σύστημα θα ισορροπεί. Υπάρχουν σημεία τα οποία είναι σημεία ισορροπίας αλλά δεν είναι σταθερά. Σε αυτά τα σημεία,
το σύστημα μπορεί στιγμιαία να ισορροπήσει αλλά ξεφεύγει πολύ εύκολα από
αυτό. Αναζητούμε συνεπώς, σταθερά σημεία ισορροπίας, τα λεγόμενα stable fixed
points. Έχει αποδειχτεί [6] ότι μπορούμε σε αυτά στα σημεία να καθορίσουμε τις
απαραίτητες συνθήκες για να είναι σταθερά, περιορίζοντας τη μέγιστη ιδιοτιμή
του μητρώου γειτνίασης που περιγράφει το δίκτυο. Ορίζονται δηλαδή κατώφλια
(thresholds) κατά περίπτωση, που περιορίζουν την μέγιστη ιδιοτιμή του δικτύου με
τέτοιο τρόπο ώστε το σύστημα, να βρίσκεται σε κατάσταση ισορροπίας. Στην πε-
ρίπτωση που αναφερόμαστε στο φαινόμενο της επιδημίας, στόχος είναι στο αντί-
στοιχο σημείο ισορροπίας η μέγιστη ιδιοτιμή να είναι κάτω του κατωφλίου, έτσι
ώστε να εξασφαλίσουμε τον περιορισμό εξάπλωσης της επιδημίας στο δίκτυο.
Στην περίπτωση που αναφερόμαστε σε μία είδηση ή ένα ανταγωνιστικό προϊόν,
η μέγιστη ιδιοτιμή θέλουμε να είναι άνω του αντίστοιχου κατωφλίου έτσι ώστε
να έχουμε εξάπλωση στο δίκτυο. Επομένως ανάλογα με την περίπτωση, αντιμε-
τωπίζουμε διαφορετικά τα κατώφλια που υπολογίζονται για το αντίστοιχο σημείο
ισορροπίας.
Στα πλαίσια της μεταπτυχιακής εργασίας, χρησιμοποιήσαμε το μοντέλο SIS
για να περιγράψουμε το φαινόμενο όπου ένας ιός εξαπλώνεται σε ένα δίκτυο όπου
οι κόμβοι του δικτύου, έχουν διαφορετική ευαισθησία απέναντί του. Πραγματο-
ποιήσαμε μαθηματική περιγραφή του μοντέλου, ορίζοντας τα απαραίτητα κατώ-
φλια έτσι ώστε το σύστημα να ισορροπεί ανάλογα με το σημείο ισορροπίας αλλά
και το είδος του γραφήματος. Επίσης, πραγματοποιήσαμε προσομοίωση του μο-
ντέλου σε συνθετικά γραφήματα (κλίκα, αυθαίρετο γράφημα κ.α), επαληθεύοντας
τη συμπεριφορά που υποδεικνύει το μαθηματικό μοντέλο. / Which is the appropriate answer about the definition of a network? One could
answer that a group of people who share a relationship (colleagues, students etc)
could be referred to, as a network. Another possible definition, is a computer
network. Consequently, it is obvious that the idea of a network can be found in
various ways in our daily life.
In the same terms, suppose we have one competing idea/product or a virus
that propagates over a multiple profile social (or other) network. Can we predict
what proportion of the network will actually get ”infected” (e.g., spread the idea
or buy the competing product), when the nodes of the network appear to have
different sensitivity based on their profile? For example, if there are two profiles
A, B in a network and the nodes of profile A and profile B are susceptible to a
highly spreading virus with probabilities βA and βB respectively, what percentage
of both profiles will actually get infected from the virus in the end?
The behavior of such a network, can be simulated using dynamical systems
theory. We consider a dynamical system as a system with a set of possible states
where each future state, is computed based on the previous state. Dynamical System
Applications, can be found in many fields such as viral marketing, ecology, information
diffusion and virus propagation.
In order to simulate the rumor or virus which is spreading across the network,
one has to use virus propagation models. The selection of the appropriate model,
depends on the special attributes and characteristics of the spreading rumor/virus
and it should cover all the possible states in which a node in the network can be
(sick, healthy,susceptible, informed, not informed etc).
According to Dynamical Systems Theory, we are looking for possible fixed
points where the system is in equilibrium. In particular, we would require each
fixed point to be a stable attractor and not lead the system far away from the
equilibrium point due to opposing forces (stable fixed points). It has been proven
that limiting the leading eigenvalue of the adjacency matrix of the graph, is the
only condition required, in order for the system to be in equilibrium state, in the
corresponding fixed point.
In this paper, we assume an SIS propagation model [8] which is applied on a
heterogeneous network. That is, we assume that there is no fair game using the
terminology of [14, 3]. In the SIS model, each node can be either in a susceptible
(S) state or in the infected state (I) and as result there is no permanent immunity
and every node can get infected multiple times.Since this is the first theoretical
treatment of heterogeneous environments for virus propagation, we choose to work
in the simple model of SIS and not in other models.
Suppose that we are given a social network and a rumor that spreads over it,
where the nodes of the network represent people with high/low sensitivity to the
rumor and the links represent the association of the nodes, how will the rumor
propagate over the network? That is, can we determine whether all members of
the network will reproduce the rumor to their neighbors and ”infect” them or the
rumor will spread in a small group in the network and die out quickly? Similarly,
which is the tipping point where such a rumor or infectious virus will take off? It
would be very helpful if we could find the specific point when the ”virus” spreads
all over the network and an epidemic occurs. Finally, what is the case when the
nodes have different endurance/sensitivity to the ”virus” and have temporary or
permanent immunity?
Our basic assumption and innovation when compared to all previous approaches
is that there is no fair-play and nodes have different profile against the virus. That
is, the network is heterogeneous with respect to the virus, which means that nodes
have different sensitivity to it. This is one of our main contributions in comparison
with previous results where all nodes appear to have the same behavior towards the
virus and the same model parameters. The propagation model which is followed,
resembles the SIS (no immunity like flu) model where nodes are either susceptible
or infected but with modifications. All nodes can get infected from one another,
despite the difference of their profiles. We prove and present the tipping point
where the virus is about to spread all over the network or the rumor ”infect” every
member of the network and result in a ”viral” phenomenon.
Our main contribution, is that we provide answers for the questions above,
for special topologies such as the clique as well as arbitrary graphs of high or
low connectivity. In particular, to the best of our knowledge, we are the first to
provide theoretical and experimental findings on the propagation of a virus over a
heterogeneous network. We prove that in the case of two profiles, if one profile has
high sensitivity to the virus and the other one has low sensitivity, actually nodes
from both profiles will get infected proportionally in the case where the network is
a clique. For arbitrary networks, we prove necessary conditions for the virus to die
out allowing for multiple profiles (not just two), while at the same time we give
directions to prove other interesting cases. The problem has many applications in
the field of viral marketing, medicine, ecology and other.
| Identifer | oai:union.ndltd.org:upatras.gr/oai:nemertes:10889/8447 |
| Date | 16 April 2015 |
| Creators | Ράπτη, Αγγελική |
| Contributors | Τσακαλίδης, Αθανάσιος, Rapti, Angeliki, Τσακαλίδης, Αθανάσιος, Τζήμας, Ιωάννης, Σιούτας, Σπυρίδων |
| Source Sets | University of Patras |
| Language | gr |
| Detected Language | Greek |
| Type | Thesis |
| Rights | 0 |
Page generated in 0.0099 seconds