Neuer Algorithmus verbessert faire Informationsverteilung in sozialen Netzwerken

Die rasche Verbreitung von Nachrichten in Online‑Social‑Netzwerken hat die Informationslandschaft revolutioniert – doch nicht alle Nutzer profitieren gleichermaßen. Besonders Mitglieder von Minderheitengruppen sind oft benachteiligt, weil ihre Position im Netzwerk sie von wichtigen Informationspfaden ausschließt.

In einer kürzlich veröffentlichten Studie wird das Problem formalisiert: Man möchte gezielt neue Verbindungen hinzufügen, um die Fairness beim Informationszugang zwischen verschiedenen demografischen Gruppen zu erhöhen. Der Zugriff wird dabei anhand der sogenannten Resistenzdistanz gemessen, ein Maß, das die globale Netzwerkstruktur und die Mehrfachverbindungen berücksichtigt. Die Optimierung ist NP‑schwer, sodass effiziente Lösungen gefragt sind.

Die Autoren stellen zunächst einen einfachen, aber genauen Greedy‑Ansatz vor, dessen Laufzeit jedoch kubisch ist und daher bei großen Netzwerken unpraktisch wird. Durch eine Reihe neuartiger Approximationstechniken gelingt es ihnen, die Komplexität auf linear zu reduzieren. In umfangreichen Experimenten mit realen und synthetischen Datensätzen zeigen sie, dass der lineare Algorithmus präzise Ergebnisse liefert – selbst für Netzwerke mit Millionen von Knoten.