Η έννοια των δικτύων εμφανίζεται πολύ συχνά με διάφορες μορφές. Δίκτυο μπορούμε να θεωρήσουμε ένα σύνολο υπολογιστών που συνδέονται μεταξύ τους υπακούοντας σε κάποιο πρωτόκολλο επικοινωνίας αλλά και μια ομάδα ανθρώ- πων που συνδέονται μέσω κάποιας κοινωνικής σχέσης, ενός εργασιακού χώρου αλλά και ως χρήστες ενός 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.

La modélisation des maladies infectieuses représente un outil important pour évaluer la vulnérabilité d'une population à l'introduction d'un nouveau agent pathogène. La possibilité d’enregistrer les contacts responsables de la propagation des maladies représente à la fois une ressource et un défi pour les modèles épidémiques. En particulier, l'interaction entre la dynamique des maladies et l'évolution dans le temps des structures de contact influence la façon dont les agents pathogènes se propagent, en changeant les conditions qui mènent à une flambée épidémique (seuil épidémique). Jusqu'à maintenant, les chercheurs n'ont caractérisé le seuil épidémique sur des structures de contact qui évoluent dans le temps que dans des contextes spécifiques. En utilisant un formalisme multi-couches, nous calculons analytiquement le seuil épidémique sur un réseau temporel générique. Nous utilisons cette méthode pour évaluer l'impact de la résolution temporelle et la durée du réseau sur l'estimation du seuil. De plus, grâce à cette méthode, nous évaluons la vulnérabilité globale de différents systèmes à l'introduction d'agents pathogènes, et en particulier nous analysons les réseaux de mouvements des bovins. Les données de contact souvent ne sont pas disponible en temps réel, et cela limite notre capacité de prévision. Pour répondre à ça, nous développons une méthodologie numérique pour prédire le risque épidémique ciblé, qui repose uniquement sur les données de contact passées. Notre travail fournit de nouvelles méthodologies pour évaluer et prédire le risque associé à un agent pathogène émergent, à la fois à l'échelle de la population et en ciblant des hôtes spécifiques. / Infectious disease modeling represents a powerful tool for assessing the vulnerability of a population to the introduction of a new infectious pathogen. The increased availability of highly resolved data tracking host interactions is making epidemic models potentially increasingly accurate. Integrating into them all the features emerging from these data, however, still represents a challenge. In particular, the interaction between disease dynamics and the time evolution of contact structures has been shown to impact the way pathogens spread, changing the conditions that lead to the wide-spreading regime, as encoded in epidemic threshold. Up to now researchers have characterized the epidemic threshold on time evolving contact structures only in specific settings. Using a multilayer formalism, we analytically compute the epidemic threshold on a generic temporal network, accounting for several different disease features. We use this methodology to assess the impact of time resolution and network duration on the estimation of the threshold. Then, thanks to it, we assess the global vulnerability of different systems to pathogen introduction, and in particular we analyze the networks of cattle trade movements Data collection strategies often inform us only about past network configurations, and that limits our prediction capabilities. We face this by developing a data-driven methodology for predicting targeted epidemic that relies only past contact data. Our work provides new methodologies for assessing and predicting the risk associated to an emerging pathogen, both at the population scale and targeting specific hosts.

Dans le développement récent des sciences de réseau, réseaux contraints spatiales sont devenues un objet d'une enquête approfondie. Spatiales des réseaux de contraintes sont intégrées dans l'espace de configuration. Leurs structures et les dynamiques sont influencées par la distance spatiale. Ceci est prouvé par les données empiriques de plus en plus sur des systèmes réels montrant des lois exponentielles ou de distribution d'énergie distance spatiale de liens. Dans cette thèse, nous nous concentrons sur la structure de réseau spatial avec une distribution en loi de puissance spatiale. Plusieurs mécanismes de formation de la structure et de la dynamique de diffusion sur ces réseaux sont pris en considération. D'abord, nous proposons un réseau évolutif construit en l'espace de configuration d'un mécanisme de concurrence entre le degré et les préférences de distance spatiale. Ce mécanisme est décrit par un a^'fc- + (1 — a)^'lL_,1, où ki est le degré du noeud i et rni est la distance spatiale entre les noeuds n et i. En réglant le paramètre a, le réseau peut être fait pour changer en continu à partir du réseau spatiale entraînée (a = 0) pour le réseau sans échelle (a = 1). La structure topologique de notre modèle est comparé aux données empiriques de réseau de courrier électronique avec un bon accord. Sur cette base, nous nous concentrons sur la dynamique de diffusion sur le réseau axé sur spatiale (a — 0). Le premier modèle, nous avons utilisé est fréquemment employée dans l'étude de la propagation de l'épidémie: ['spatiale susceptible-infecté-susceptible (SIS) modèle. Ici, le taux de propagation entre deux noeuds connectés est inversement proportionnelle à leur distance spatiale. Le résultat montre que la diffusion efficace de temps augmente avec l'augmentation de a. L'existence d'seuil épidémique générique est observée, dont la valeur dépend du paramètre a Le seuil épidémique maximum et le ratio minimum fixe de noeuds infectés localiser simultanément dans le intervalle 1.5 < a < 2.Puisque le réseau spatiale axée a bien défini la distance spatiale, ce modèle offre une occasion d'étudier la dynamique de diffusion en utilisant les techniques habituelles de la mécanique statistique. Tout d'abord, compte tenu du fait que la diffusion est anormale en général en raison de l'importante long plage de propagation, nous introduisons un coefficient de diffusion composite qui est la somme de la diffusion d'habitude constante D des lois de la Fick appliqué sur différentes distances de transfert possibles sur le réseau. Comme prévu, ce coefficient composite diminue avec l'augmentation de a. et est une bonne mesure de l'efficacité de la diffusion. Notre seconde approche pour cette diffusion anormale est de calculer le déplacement quadratique moyen (l²) à identifier une constante de diffusion D' et le degré de la anomalousness y avec l'aide de la loi de puissance (l²) = 4D'ty. D' comportements de la même manière que D, i.e.. elle diminue avec l'augmentation de a. y est inférieur à l'unité (subdiffusion) et tend à un (diffusion normale) que a augmente. / In the recent development of network sciences, spatial constrained networks have become an object of extensive investigation. Spatial constrained networks are embedded in configuration space. Their structures and dynamics are influenced by spatial distance. This is proved by more and more empirical data on real Systems showing exponential or power laws spatial distance distribution of links. In this dissertation, we focus on the structure of spatial network with power law spatial distribution. Several mechanisms of structure formation and diffusion dynamics on these networks are considered. First we propose an evolutionary network constructed in the configuration space with a competing mechanism between the degree and the spatial distance preferences. This mechanism is described by a ki + (1 — a), where ki is the degree of node i and rni is the spatial distance between nodes n and i. By adjusting parameter a, the network can be made to change continuously from the spatial driven network (a = 0) to the scale-free network (a = 1). The topological structure of our model is compared to the empirical data from email network with good agreement. On this basis, we focus on the diffusion dynamics on spatial driven network (a = 0). The first model we used is frequently employed in the study of epidemie spreading : the spatial susceptible-infected-susceptible (SIS) model. Here the spreading rate between two connected nodes is inversely proportional to their spatial distance. The result shows that the effective spreading time increases with increasing a. The existence of generic epidemic threshold is observed, whose value dépends on parameter a. The maximum épidemic threshold and the minimum stationary ratio of infected nodes simultaneously locate in the interval 1.5 < a < 2. Since the spatial driven network has well defined spatial distance, this model offers an occasion to study the diffusion dynamics by using the usual techniques of statistical mechanics. First, considering the fact that the diffusion is anomalous in general due to the important long-range spreading, we introduce a composite diffusion coefficient which is the sum of the usual diffusion constant D of the Fick's laws applied over different possible transfer distances on the network. As expected, this composite coefficient decreases with increasing a and is a good measure of the efficiency of the diffusion. Our second approach to this anomalous diffusion is to calculate the mean square displacement (l²) to identify a diffusion constant D' and the degree of thé anomalousness y with the help of the power law {l²} = 4D'ty. D' behaviors in the same way as D, i.e., it decreases with increasing a. y is smaller than unity (subdiffusion) and tends to one (normal diffusion) as a increases.

Menschliche Systeme werden seit einiger Zeit modelliert und analysiert auf der Basis der Theorie komplexer Netzwerke. Dies erlaubt es quantitativ zu untersuchen, welche strukturellen und zeitlichen Merkmale eines Systems Ausbreitungsprozesse beeinflussen, z.B. von Informationen oder von Infektionskrankheiten. Im ersten Teil der Arbeit wird untersucht, wie eine modular-hierarchische Struktur von statischen Netzwerken eine schnelle Verbreitung von Signalen ermöglicht. Es werden neue Heuristiken entwickelt um die Random-Walk-Observablen “First Passage Time” und “Cover Time” auf lokal geclusterten Netzwerken zu ermitteln. Vergleiche mit der Approximation eines gemittelten Mediums zeigen, dass das Auftreten der beobachteten Minima der Observablen ein reiner Netzwerkeffekt ist. Es wird weiterhin dargelegt, dass nicht alle modular-hierarchischen Netzwerkmodelle dieses Phänomen aufweisen. Im zweiten Teil werden zeitlich veränderliche face-to-face Kontaktnetzwerke auf ihre Anfälligkeit für Infektionskrankheiten untersucht. Mehrere Studien belegen, dass Menschen vornehmlich Zeit in Isolation oder kleinen, stark verbundenen Gruppen verbringen, und dass ihre Kontaktaktivität einem zirkadianen Rhythmus folgt. Inwieweit diese beiden Merkmale die Ausbreitung von Krankheiten beeinflussen, ist noch unklar. Basierend auf einem neuen Modell wird erstmals gezeigt, dass zirkadian variierende Netzwerke Trajektorien folgen in einem Zustandsraum mit einer strukturellen und einer zeitlichen Dimension. Weiterhin wird dargelegt, dass mit zunehmender Annäherung der zeitlichen Dimension von System und Krankheit die systemische Infektionsanfälligkeit sinkt. Dies steht in direktem Widerspruch zu Ergebnissen anderer Studien, die eine zunehmende Anfälligkeit vorhersagen, eine Diskrepanz, die auf die Ungültigkeit einer weit verbreiteten Approximation zurückzuführen ist. Die hier vorgestellten Ergebnisse implizieren, dass auf dem Gebiet die Entwicklung neuer theoretischer Methoden notwendig ist. / Human systems have been modeled and analyzed on the basis of complex networks theory in recent time. This abstraction allows for thorough quantitative analyses to investigate which structural and temporal features of a system influence the evolution of spreading processes, such as the passage of information or of infectious diseases. The first part of this work investigates how the ubiquitous modular hierarchical structure of static real-world networks allows for fast delivery of messages. New heuristics are developed to evaluate random walk mean first passage times and cover times on locally clustered networks. A comparison to average medium approximations shows that the emergence of these minima are pure network phenomena. It is further found that not all modular hierarchical network models provide optimal message delivery structure. In the second part, temporally varying face-to-face contact networks are investigated for their susceptibility to infection. Several studies have shown that people tend to spend time in small, densely-connected groups or in isolation, and that their connection behavior follows a circadian rhythm. To what extent both of these features influence the spread of diseases is as yet unclear. Therefore, a new temporal network model is devised here. Based on this model, circadially varying networks can for the first time be interpreted as following trajectories through a newly defined systemic state space. It is further revealed that in many temporally varying networks the system becomes less susceptible to infection when the time-scale of the disease approaches the time-scale of the network variation. This is in direct conflict with findings of other studies that predict increasing susceptibility of temporal networks, a discrepancy which is attributed to the invalidity of a widely applied approximation. The results presented here imply that new theoretical advances are necessary to study the spread of diseases in temporally varying networks.