Details

Autor(en) / Beteiligte

• Ogierman, Adrian
• Elsässer, Robert
• Scheideler, Christian

Titel

Epidemic spreading and information dissemination in technological and social systems

Erscheinungsjahr

2014

Verknüpfte Titel

Beschreibungen/Notizen

• Tag der Verteidigung: 24.10.2014
• Paderborn, Univ., Diss., 2014
• ger: In dieser Arbeit betrachten wir Probleme aus dem Bereich der Nachrichten- und Krankheitsverbreitung in dynamischen als auch statischen Strukturen aus dem Gebiet der technologischen und der sozialen Netzwerke. Als erste Fragestellung untersuchen wir, ob ein verteiltes Protokoll zur Nachrichtenverbreitung in Netzwerken mit Power Law Knotengradverteilung existiert, so dass sich die Knotengradverteilung nicht negativ bemerkbar macht. Wir präsentieren ein Protokoll, welches mit hoher Wahrscheinlichkeit nur O(log n) viele Runden mit O(n loglog n) vielen Nachrichten benötigt um alle n Knoten zu informieren. Als nächstes untersuchen wir wie Strategien zur Eindämmung einer solchen Ausbreitung aussehen könnten. Sei V der für die Ausbreitung der schädlichen Nachricht verantwortliche Prozess. Wir lassen V sich von jedem infizierten Knoten über eine konstante Anzahl von Verbindungen verbreiten. Unsere Strategie zur Bekämpfung von V wird an jedem infizierten Knoten nach einer konstanten Anzahl von Schritten aktiviert. Ist der minimale Knotengrad loglog n, so zeigen wir, dass die Immunisierung der direkten Nachbarschaft ausreicht um die Infektion mit hoher Wahrscheinlichkeit zu eliminieren. Ist der minimale Knotengrad eine Konstante und immunisiert jeder infizierte Knoten v alle Knoten in seiner O(log(d(v)))-Nachbarschaft, wobei d(v) den Knotengrad von Knoten v bezeichnet, lassen sich ähnliche Abschätzungen zeigen. Zudem betrachten wir eine Epidemie in einer städtischen Umgebung mit mobilen Einwohnern. Werden keinerlei Gegenmaßnahmen getroffen, so bleibt dennoch mit hoher Wahrscheinlichkeit ein polynomieller Anteil der Population von der Epidemie unberührt. Werden jedoch Gegenmaßnahmen genutzt, so werden mit Wahrscheinlichkeit 1-o(1) nur polylogarithmisch viele Individuen infiziert.
• eng: In this thesis we consider the problems of information dissemination and epidemic spreading in dynamic as well as static technological and social networks. We start by wondering if there might be a fast decentralized dissemination protocol, such that a power law degree distribution does not slow down the dissemination process in the network. We present a protocol that informs all n nodes within O(log n) many rounds using O(n loglog n) many transmissions with high probability. But how do we design a counteracting dissemination process to combat the malicious one denoted by V? Suppose V uses a constant number of randomly chosen connections of each infected node to infect others for one time only and suppose that the counteracting dissemination process is activated on each infected node after a constant delay. We show that it suffices to immunize the neighborhood of each infected node, provided the minimum degree of the network is loglog n. Otherwise, if the minimum degree of the network is constant, we propose to immunize every node within O(log(d(v))) many hops of each infected node v, where d(v) denotes the degree of node v. Executing these strategies we prove that V does not infect more than o(n) many nodes until it is eliminated with high probability. Finally, we take mobility into account and examine an epidemic outbreak in an urban environment inhabited by mobile individuals on a small and on a large scale. Amongst others, we show that at least a polynomial fraction of the individuals remains uninfected even if they do not respond to the epidemic outbreak in any way. However, if the epidemic outbreak does influence the individual's behavioral pattern and certain countermeasures are applied, then only a polylogarithmic amount of individuals is infected until the epidemic is embanked with probability 1-o(1).