Wie man Netzwerke effizient zerlegt
Sowohl Viren als auch Kriminalität und andere Probleme breiten sich über Netzwerke aus. ETH-Forscher haben nun einen neuen Ansatz entwickelt, wie man Netze kostengünstiger schützen kann. Wenn das Budget eine Rolle spielt, sollte man mit mittelgrossen Netzwerkknoten beginnen.
In der Schlussszene des Kinohits «Planet der Affen: Prevolution» aus dem Jahr 2011 trägt ein Flugzeugpilot unwissentlich ein gefährliches Grippe-Virus von San Francisco nach Paris. Von dort verbreiten es unzählige Flugpassagiere rund um die Welt. Im Gegensatz zu den Affen überlebt ein Grossteil der Menschheit die anschliessende Pandemie nicht.
Natürlich ist der Aufstieg intelligenter Affen (im Original heisst der Film Rise of the Planet of the Apes) Science-Fiction. Die Ausbreitung krankmachender Viren über den Flugverkehr hingegen ist ein reales Risiko. Forscher der ETH-Professur für Computational Social Science und des Informatikdepartments haben nun untersucht, wie die Zerlegung von Netzwerken helfen könnte, die Verbreitung von Viren durch Flugverkehr kosteneffizienter einzugrenzen.
Eine manchmal diskutierte Schutzmassnahme ist, bestimmte Flughäfen zu schliessen und unter Quarantäne zu stellen. Eine Möglichkeit wäre, sich dabei auf die weltgrössten Flughafen-Hubs mit den meisten Flugverbindungen zu konzentrieren – schliesslich landen dort sehr viele Passagiere oder steigen um. Dies ist allerdings nicht die beste Idee.
Der Eingriff wäre wegen der hohen Anzahl betroffener Flugreisender massiv. Die ETH-Forscher Xiao-Long Ren, Niels Gleinig, Dirk Helbing und Nino Antulov-Fantulin haben nun in der Wissenschaftszeitschrift PNAS gezeigt, dass es weniger radikale und wirkungsvollere Massnahmen geben könnte, die deutlich weniger Passagiere in Mitleidenschaft ziehen.
Die Mittelgrossen zuerst
«Würde man zum Beispiel zuerst einige mittelgrosse Flughäfen anstatt die grössten Hubs schliessen, dann würde das Szenario, das wir untersuchten, viermal weniger Kosten verursachen. Trotzdem scheint dies genauso wirksam zu sein, um die Ausbreitung des Virus einzudämmen», sagt Nino Antulov-Fantulin.
Dieses Szenario haben die ETH-Forscher für Europa, Nordamerika und Asien als Bestandteile eines globalen Flugverkehrsnetzwerks durchgespielt. Ihre Ergebnisse zeigen, dass die Schliessung von mittelgrossen Flughäfen nur 6 Prozent der weltweiten Flugpassagiere beträfe, wohingegen es bei einer Schliessung der grössten Hubs 25 Prozent wären.
Um herauszufinden, welche Flughäfen man am besten schliesst, wenn man das Virus kostengünstig und wirksam eindämmen will, griffen die Forscher einen Ansatz auf, der in der Netzwerkforschung als «Dismantling Problem» (dts. «Zerlegungs-Problem») bekannt ist und zu den grundlegenden Problemen der Netzwerkforschung zählt. Dabei geht es darum, welche Knoten man deaktivieren oder aus einem Netzwerk entfernen muss, um ein darin auftretendes Problem oder eine Fehlfunktion zu beheben.
Die ETH-Forscher versuchten, verschiedene fehlerhafte Netzwerke mit möglichst minimalen Gesamtkosten in isolierte Teilnetze zu zerlegen, um so die Ausbreitung der Fehler einzudämmen und die Funktionsfähigkeit des Gesamtnetzes zu erhalten. Je nachdem, ob es sich um ein soziales, biologisches oder technisches Netzwerk handelt, können die Fehler beispielsweise Computerviren sein, Grippeerreger oder Kriminelle.
Kriminalität eindämmen
Auch in anderen Fallbeispielen konnten die ETH-Forscher zeigen, dass die Zerlegung eines Netzwerks kostengünstiger und wirksamer ist, wenn man sich zunächst nicht auf die grössten, sondern auf mittelgrosse Knoten konzentriert: Das trifft zum Beispiel auf kriminelle Netzwerke zu.
Wenn man in kriminellen Netzwerken an der Spitze anfängt, entstehen sehr hohe Kosten. Nicht nur wegen der besonderen Schutzmassnahmen für die Chefs, sondern auch, weil in der Regel schnell jemand anderes die Führung übernimmt und das Netzwerk weiterführt. Wenn man zuerst mittlere Positionen entfernt, lässt sich das Netzwerk mindestens genauso wirksam zerschlagen und man muss dafür deutlich weniger Aufwand betreiben, so die Forscher.
«Im Vergleich zu einer State-of-the-art-Methode sind die Kosten der Netzwerk-Zerlegung in unserem Ansatz 2,5-mal tiefer, wenn wir ein kriminelles Netzwerk auf 10 Prozent seiner ursprünglichen Größe reduzieren», sagt Xiao-Long Ren, Doktorand und Erstautor der Studie. Der Fall des kriminellen Netzwerks illustriert eine weitere Besonderheit des ETH-Ansatzes: Im Unterschied zu anderen Methoden behandelt er nicht alle Knoten gleich.
«Wir gehen nicht mehr davon aus, dass alle Knoten in einem Netzwerk die gleichen Entfernungskosten haben», erklärt Ren weiter, «vielmehr sind die Kosten, um die grossen Knoten zu entfernen, höher, weil sie stärker mit anderen verbunden sind.»
Herausforderung in Theorie und Anwendung
Die ETH-Forscher haben auch in der Zerlegung besonders grosser Netzwerke, die mehrere Millionen Knoten umfassen, Fortschritte gemacht. Das «Zerlegungs-Problem» gehört nämlich zur Klasse schwieriger Computerprobleme, den so genannten NP-harten Problemen.
Auch wenn die theoretische Methode mit empirischen Daten demonstriert wurde, empfehlen sich vor ihrer praktischen Anwendung ergänzende Studien. Die Methode sollte auf den jeweiligen Anwendungsbereich angepasst und getestet werden. Nicht nur die Netzwerkstruktur und Entfernungskosten der Netzwerkknoten, sondern auch weitere Faktoren können eine Rolle spielen.
Ausserdem betonen die Forscher: «Legitime Anwendungen unserer Methode müssen ethische Fragen ausreichend, angemessen und transparent berücksichtigen.»
Literaturhinweis
Ren X-L, Gleinig N, Helbing D, Antulov-Fantulin, N. Generalized network dismantling. PNAS Proceedings of the National Academy of Sciences, April 2, 2019 116 (14) 6554-6559; published ahead of print March 15, 2019. DOI: externe Seite 10.1073/pnas.1806108116.