Die richtige Reihenfolge
Ingo Scholtes vom Lehrstuhl für Systemgestaltung hat ein Analyseverfahren entwickelt, das die zeitliche Reihenfolge von Verbindungen innerhalb von Netzwerken berücksichtigt. Damit lässt sich nicht nur genauer bestimmen, welche Themen im Internet miteinander zusammenhängen, sondern es ermöglicht beispielsweise auch, die Verbreitung von Epidemien besser vorauszusagen.
Warum etwas ändern, wenn es offenbar gut funktioniert? Seit vielen Jahrzehnten werden Netzwerke nach dem mehr oder weniger gleichen Muster analysiert. So wird beispielsweise ein Artikel im Web als umso relevanter eingestuft, je mehr Pfade im Netz zu ihm führen. Entsprechend wird ein Artikel auf den viele andere wichtige Artikel verweisen, von Suchmaschinen ganz oben gelistet. Ausschlaggebend hierfür ist also die komplexe Struktur der Verbindungen, das heisst, welche Artikel mit welchen anderen Artikeln verbunden sind.
Zeitliche Reihenfolge sehr wichtig
«Aktuelle Netzwerkanalyseverfahren lassen eine ganz wichtige Dimension ausser Acht, nämlich die zeitliche Abfolge der Verbindungen», sagt Ingo Scholtes, Oberassistent am Lehrstuhl für Systemgestaltung. Das heisst, die Algorithmen, die Links zwischen Artikeln im Web analysieren, berücksichtigen nicht, in welcher zeitlichen Abfolge User Artikel aufrufen. Genau dies wäre jedoch wichtig. Denn die Reihenfolge, in der wir uns durch Informationsnetze bewegen, enthält wertvolle Informationen darüber, welche Artikel thematisch besonders eng miteinander verbunden und deshalb für Nutzer relevant sind.
Beispiel Wikipedia: Wenn ein User von einem Artikel über «Albert Einstein» per Link zur «ETH Zürich» klickt, dann ist es wahrscheinlicher, dass er als nächstes einen Artikel mit Bezug zu Physik aufruft als einen zu Erdwissenschaften. «Wenn wir die zeitliche Dimension bei der Netzwerkanalyse berücksichtigen, können wir viel bessere Vorhersagen zum Nutzerverhalten machen und darauf aufbauend auch relevantere Suchergebnisse erzielen und bessere Empfehlungen geben», sagt Scholtes.
Modell auf alle Netzwerke anwendbar
Die Erkenntnisse von Ingo Scholtes sind nicht allein für Suchalgorithmen im Internet wichtig. Seine Analysemethode kann auf jegliche Form von Netzwerken angewandt werden. «Netzwerke sind abstrakte Modelle für Sachen, die miteinander verbunden sind», erläutert der Informatikspezialist. «Dazu gehören beispielsweise auch Verkehrsinfrastrukturen, das globale Finanzsystem, Energienetze, die Zellen in unserem Körper und neben den virtuellen Netzwerken wie Facebook auch die realen Verbindungen zwischen Menschen.»
Wie wichtig die zeitliche Reihenfolge ist, macht die Anwendung von Scholtes’ neuer Netzwerkanalysemethode bei der Vorhersage von Epidemien deutlich: Um voraussagen zu können, wie stark sich eine Grippewelle ausbreiten wird und welche Bevölkerungsgruppen betroffen sein werden, reicht es nicht aus, zu wissen, welche Personen einander kennen – also in einem Netzwerk miteinander verbunden sind. Auch die Reihenfolge ihrer Begegnungen ist entscheidend, um beispielsweise vorhersagen zu können, ob Alice ihre Grippeerkrankung an Bob und auch an Carol weitergeben wird. Nur wenn Alice erst Bob und Bob anschliessend Carol trifft, kann sich Carol anstecken. Wenn Bob zunächst Carol trifft und erst später Alice, wird Carol nicht an Grippe erkranken.
Auch bei der Analyse des Londoner U-Bahn-Netzes hat Scholtes festgestellt, dass die häufig verwendeten Netzwerkmodelle der «Tube» oft danebenliegen. Nur weil zum Beispiel eine U-Bahn-Station viele Querverbindungen aufweise, bedeute dies nicht, dass die Passagiere von hier aus alle Strecken gleich wahrscheinlich nutzen würden. Liegt diese Station nämlich eher am Stadtrand, dann werden die Passagiere Verbindungen bevorzugen, die sie weiter in die Innenstadt bringen. Auf Linie A folgt also viel häufiger Linie B als die Linien C oder D – auch wenn aus der Netzwerkperspektive alle gleich möglich erscheinen. «Unsere Ergebnisse in Bezug auf die ‹London Tube› werfen ein kritisches Licht auf die Anwendung netzwerkbasierter Verfahren, die zum Beispiel auch bei der Analyse von Risiken im Schweizer Bahnnetz eingesetzt werden», sagt Scholtes.
Abschied von bisheriger Analysemethode
Es sei wichtig, künftig sowohl die Struktur als auch die zeitlichen Zusammenhänge bei der Analyse und Modellierung von Netzwerken zu berücksichtigen, betont Scholtes: «Es ist von elementarer Bedeutung für unsere Gesellschaft, dass wir die richtigen Methoden zur Untersuchung von Netzwerken nutzen, da dies unmittelbare Auswirkungen auf so unterschiedliche Fragen wie der Resilienz kritischer Infrastrukturen oder der Verbreitung von Epidemien hat.»
Vorstellung der neuen Netzwerkanalysemethode
Ingo Scholtes präsentiert seine Ergebnisse an der externe Seite KDD2017-Konferenz, dem weltweit grössten Informatikkongress zu Data Science und Big Data, in Halifax, Canada. Zudem hat er eine kostenlose Software zur Netzwerkanalyse entwickelt, welche die zeitliche Reihenfolge berücksichtigt. Diese ist zum Download verfügbar unter: externe Seite https://github.com/IngoScholtes/pathpy