Projekte

Wie verhindert man, dass Viren viral werden?

Computerwissenschaftler:innen entdeckten eine Parallele: Viren verbreiten sich ähnlich wie Nachrichten in den sozialen Medien. Ihre Berechnungsmodelle, wie Posts viral werden, wollen sie nun verfeinern und auf die Ausbreitungswege von SARS-CoV-2 übertragen. Quelle: Felipe Esquivel Reed, CC BY-SA 4.0, via Wikimedia Commons

Eigentlich beschäftigte sich der Forscher Markus Sinnl in seiner bisherigen Arbeit mit sozialen Medien wie Twitter. In den vergangenen Jahren entwickelte er Methoden, die klären sollten, wie bestimmte Posts viral werden. Als die Coronapandemie ausbrach, erkannte er, dass die Situation der Ausbreitung von Informationen in sozialen Medien der Ausbreitung des Coronavirus in der Bevölkerung stark ähnelt. In einem vom Wissenschaftsfonds FWF finanzierten Projekt will er nun seine Tools für den Kampf gegen Corona nutzen.

Suche nach exakten Lösungen

Projektleiter Sinnl plant, dazu die für Social Media entwickelten Methoden zu erweitern. Das Virus entspricht hier einem Akteur in einem Netzwerk, der maximale Ausbreitung erreichen will. „Das würden wir genau so modellieren wie die Ausbreitung einer Message in einem sozialen Netzwerk, doch wir wollen noch eine Ebene darüberlegen, mit von außen getroffenen Maßnahmen, die eine Ausbreitung verhindern sollen“, erklärt Sinnl.

Die dabei von Sinnl angewandte Methode nennt sich ganzzahlige Programmierung. Dabei geht es um die Lösungen von Gleichungen, die keine Kommazahlen, sondern nur ganze Zahlen enthalten. Viele praktische Probleme in der Industrie oder beispielsweise bei Fahrplänen im öffentlichen Verkehr lassen sich auf diese Weise gut behandeln. Darauf weist auch Sinnls Arbeitsumfeld am Institut für Produktions- und Logistikmanagement der Johannes Kepler Universität Linz hin. Der Vorteil der ganzzahligen Programmierung: Die Gleichungen liefern mehr als nur Wahrscheinlichkeiten. „Unsere Methoden geben die beweisbar optimale Lösung des Problems an“, betont Sinnl.

Methoden aus Werbung

„In den letzten Jahren habe ich ganzzahlige Programmierung unter anderem zum Lösen von Influence-Maximisation angewandt“, erzählt er. „Die Frage war: Wie kann man in sozialen Netzwerken Leute beeinflussen?“ Solche Probleme hätten durchaus eine Tradition in den Computerwissenschaften, so der Forscher, doch die meisten versuchten, sie „heuristisch“ zu lösen, also Näherungslösungen zu finden.

In der Beschreibung der Ausbreitungsdynamik des Coronavirus seien exakte Lösungen eine Neuerung, auch dort wird bisher mit heuristischen Methoden und Näherungslösungen gearbeitet. Außerdem würden bestimmte Maßnahmen zur Verhinderung der Ausbreitung zwar mit Modellen auf ihre Wirksamkeit geprüft, erklärt der Forscher, doch ob das auch die optimale Lösung ist, lasse sich kaum feststellen. Sinnl hingegen nähert sich der Situation, indem er sie als Optimierungsproblem betrachtet. Er bildet verschiedene Maßnahmen zur Reduktion der Ausbreitung in seinen Methoden ab und sucht dann direkt die optimale Kombination.

Die Grafik illustriert einen Teilschritt im Lösungsverfahren für das Competitive Influence Maximization Problem. Dabei kämpfen zwei Agenten, Leader und Follower, um Einfluss im Netzwerk. Teilgrafik (a) skizziert den gegebenen Input. Für jede der dargestellten Verbindungen zwischen zwei Knoten im Netzwerk ist im Input auch noch eine Influence-Wahrscheinlichkeit gegeben. Basierend auf diesen Wahrscheinlichkeiten werden verschiedenste sogenannte Live-Arc-Graphen erstellt, wie in (b) und (c) skizziert. Mit diesen kann man dann den Einfluss des Leaders (L) und Followers (F) für gewählte Anfangsknoten einfach berechnen. In dem Beispiel kann sowohl L als auch F einen Anfangsknoten wählen. Die vom Leader beeinflussten Knoten am Ende des Beeinflussungsprozesses sind hellblau hinterlegt, die vom Follower dunkelblau. Quelle: Michael Kahr et al., CC BY-SA 4.0

Hoher Rechenaufwand

Der Forscher betont, dass sein Zugang rechenaufwändig ist. Bisher lassen sich mit seinen Möglichkeiten nicht mehr als 30.000 Netzwerkknoten simulieren, wobei ein Knoten einer Person entspricht. Doch ein praktischer Einsatz in der Pandemiebekämpfung sei derzeit noch nicht das vorrangige Ziel. „Es geht hier um Grundlagenforschung. Wir versuchen zu zeigen, dass es machbar ist“, sagt Sinnl. Das Projekt, das Ende 2020 vom FWF bewilligt wurde, startet im Dezember und soll eine Laufzeit von zwei Jahren haben.

Problem auf mehreren Ebenen

Mit der Betrachtung mehrerer Ebenen werde das Problem deutlich komplexer und verwandle sich in ein sogenanntes „hierarchisches“ Problem. „Das sind grundsätzlich sehr schwierige Optimierungsprobleme“, erläutert der Forscher. „Die Forschung dazu stammt aus den letzten 10 bis 15 Jahren. Davor reichte die Rechenleistung einfach nicht aus.“ Sinnl will für seine Berechnungen Parallelrechner verwenden, das sind Supercomputer mit oft vielen hundert Einzelprozessoren, die parallel an einem Problem arbeiten. Bei seiner Arbeit wird der Computerwissenschaftler von seiner Forscherkollegin Kübra Taninmiş unterstützt, mit der er schon bei seinen Forschungen zu hierarchischen Problemen gearbeitet hat und die aus Mitteln des Projekts beschäftigt ist.

Neue Lösungen finden

„Es ist klar, dass Simulationen mit viel größeren Datenmengen umgehen können und wir mit unseren exakten Methoden nur kleinere und abstraktere modellierte Probleme ansehen werden“, sagt Sinnl. „Aber es gibt bisher sehr wenige Arbeiten in die Richtung, wie wir sie versuchen. Wir können so vielleicht neue Lösungen zur Pandemiebekämpfung finden, die als alternative Ansätze für die bisherigen heuristischen Modelle dienen können.“


Zur Person

Markus Sinnl ist Computerwissenschaftler am Institut für Produktions- und Logistikmanagement der Johannes Kepler Universität Linz. Er interessiert sich für ganzzahlige Programmierung, Social-Media-Optimierung und hierarchische Optimierungsprobleme. Das vom Wissenschaftsfonds FWF finanzierte Projekt „Epidemieverhinderung in Netzwerken mit Integer Programming“ läuft von 2021 bis 2023 und wird mit 154.000 Euro gefördert.


Publikationen

Kübra Tanınmış, Necati Aras, İ. Kuban Altınel: Improved x-space algorithm for min-max bilevel problems with an application to misinformation spread in social networks, in: European Journal of Operational Research, Vol. 297, Issue 1, 2022

Evren Güney, Markus Leitner, Mario Ruthmair, Markus Sinnl: Large-scale influence maximization via maximal covering location, in: European Journal of Operational Research, Vol. 289, Issue 1, 2021

Michael Kahr, Markus Leitner, Mario Ruthmair, Markus Sinnl: Benders decomposition for competitive influence maximization in (social) networks, in: Omega, Vol. 100, 2021

Kommentare (0)

Aktuell sind keine Kommentare für diesen Artikel vorhanden.

Einen Kommentar schreiben

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.