Analysis of epidemic processes and algorithms in large networks

Epidemic processes are often used to model and simulate the spread of a disease in networks, which describe certain interactions between individuals (also called social networks). Randomized algorithms based on such processes are called epidemic algorithms. In this project we have two main objectives. First, we analyze the so called gossiping problem. Here, we assume that at the beginning each node of a network possesses a message, and all these messages have to be distributed to all nodes of the underlying graph. The goal is to solve this problem in a small number of time steps and with a reduced number of message transmissions. First results show that the quality of such algorithms in complete graphs is worse than in the case of broadcasting. In this project, we consider these algorithms in general graphs, and try to improve their performance. Our second objective consists of the theoretical analysis of epidemic processes in large networks. In most cases, epidemics are studied in static networks. However, one of the main reasons for the spread of diseases in a modern society is due to the mobility of the people. We analyze epidemics in several state-of-the-art network mobility models, which take into account the spacial situation of different locations as well as the mobility of the people within a large urban area. Furthermore, we also consider the impact of the spread of awareness about a disease on the behavior of the underlying epidemic.

Epidemic processes play an important role in modeling and simulating the spread of diseases. In order to simulate these processes, one needs a proper model for the way how people interact in society. Motivated by the behavior of epidemic processes, randomized algorithms were developed in order to solve some fundamental communication problems in theoretical computer science and distributed computing. These epidemic algorithms are usually simple, act in a fully distributed manner and only require local knowledge at a node in a distributed network.Within this project, we identified two main goals. Our first aim was to analyze the gossiping problem theoretically. Initially, each node possesses some message. These messages have to be efficiently disseminated to all nodes in the network such that the number of time steps as well as the number of message transmissions is minimized. In the case of broadcasting it is known that the graph density influences the performance of certain natural and simple algorithms. The problem of gossiping has been analyzed before in different settings; however, one major question was whether a similar influence of the graph density as in the case of broadcasting also holds in the case of gossiping. Our results indicate that, unlike in broadcasting, there is no significant difference between the performance of randomized gossiping in complete graphs and sparse random graphs.The second main goal of the project was the theoretical analysis of epidemic processes in large networks. In most papers about the spread of epidemics, the networks on which they are studied are static, i.e., their topology does not change over time. However, the main reason for global epidemics is usually related to the movement of individuals around the world. Therefore, we implemented certain movement models in a large networks, and analyzed theoretically as well as empirically the spread of diseases while taking into consideration these movements. Moreover, we studied the impact of the spread of information about an epidemic on the spread of the disease in certain power law networks.