Untersuchung von epidemischen Prozessen und Algorithmen in großen Netzwerken

Epidemische Prozesse spielen eine bedeutende Rolle bei der Modellierung und Simulation von Krankheitsverläufen in Netzwerken menschlicher Interaktion (auch soziale Netzwerke genannt). Randomisierte Verfahren, die auf solchen Prozessen aufbauen, heißen epidemische Algorithmen und haben vielfältige Anwendungen in der Theoretischen Informatik. Im Rahmen dieses Projektes haben wir zwei Hauptziele identifiziert. Zum einen wollen wir das sog. Gossiping- Problem theoretisch untersuchen. Dabei nimmt man an, dass am Anfang jeder Knoten eines Netzwerks eine Nachricht besitzt, die an alle Knoten in möglichst wenig Zeitschritten und mit minimalem Kommunikationsaufwand verteilt werden soll. Mit Hilfe von epidemischen Algorithmen lässt sich dieses Problem einfach und robust lösen. Erste Untersuchungen zeigen allerdings, dass die Güte dieser Algorithmen auf vollständigen Graphen bzgl. Gossiping weitaus schlechter ist als in dem Fall von Broadcasting. Ein Hauptziel unseres Projektes besteht darin, die Qualität dieser Algorithmen auf allgemeineren Graphen zu untersuchen und zu verbessern. Das zweite Hauptziel des Projektes ist die theoretische Analyse epidemischer Prozesse in großen Netzwerken. In den meisten Veröffentlichungen über das Ausbreitungsverhalten von Krankheiten werden statische Netzwerke zu Grunde gelegt. Dabei ist die immer wachsende Mobilität der Individueneine der wichtigsten Ursachen für globale Epidemien in der heutigen Gesellschaft. In unserer Forschung werden wir Ausbreitungsszenarien in gängigen dynamischen Netzwerk-Modellen untersuchen, die sowohl die räumliche Lage der verschiedenen Orte als auch die Mobilität von Individuen in großen Ballungszentren berücksichtigen. Darüber hinaus wollen wir in statischen sozialen Netzwerken den Einfluss der Verbreitung von Informationen über die Epidemie auf den Verlauf der Krankheit analysieren.

Epidemische Prozesse spielen bei der Modellierung und Simulation von Krankheitsverlaufen in Netzwerken menschlicher Interaktion (auch soziale Netzwerke genannt) eine bedeutende Rolle. Randomisierte Verfahren, die auf solchen Prozessen aufbauen, heißen epidemische Algorithmen und haben vielfaltige Anwendungen in der Theoretischen Informatik und dem Verteilten Rechnen.Im Rahmen dieses Projektes haben wir zwei Hauptziele identifiziert. Zum einen wollen wir das sog. Gossiping-Problem theoretisch untersuchen. Dabei nimmt man an, dass am Anfang jeder Knoten eines Netzwerks eine Nachricht besitzt, die an alle Knoten in möglichst wenig Zeit- schritten und mit minimalem Kommunikationsaufwand verteilt werden soll. Mit Hilfe von epidemischen Algorithmen lässt sich dieses Problem einfach und robust losen. Erste Untersuchungen zeigen allerdings, dass die Güte dieser Algorithmen auf vollständigen Graphen bzgl. Gossiping weitaus schlechter ist als im Fall von Broadcasting. Es stellt sich also die Frage, wie sich Gossiping in dünneren Graphen verhalt. Wir haben festgestellt, dass der Einfluss, den die Knotengrade auf das Verhalten des Broadcasting-Algorithmus haben, im Falle des Gossiping-Verfahrens nicht beobachtet werden kann und somit ein fundamentaler Unterschied zwischen Gossiping und Broadcasting vorliegt.Das zweite Hauptziel des Projektes war die theoretische Analyse epidemischer Prozesse in großen Netzwerken. In den meisten Veröffentlichungen über das Ausbreitungsverhalten von Krankheiten werden statische Netzwerke zu Grunde gelegt. Dabei ist die immer wachsende Mobilität der Individuen eine der wichtigsten Ursachen für globale Epidemien in der heutigen Gesellschaft. In unserer Forschung haben wir gewisse Ausbreitungsszenarien in gängigen dynamischen Netzwerk-Modellen untersucht, die sowohl die Attraktivität der verschiedenen Orte als auch die Mobilität von Individuen in großen Netzwerken berücksichtigen. Darüber hinaus konnten wir in bestimmten power law Netzwerken den Einfluss der Verbreitung von Informationen über die Epidemie auf den Verlauf der Krankheit analysieren.