Wichtige Verbindungen in einem Netzwerk aufspüren - automatisch

Einer der Bereiche, in dem sich Daten gut als Graph darstellen lassen, ist der Handel. Wir können jedes handelbare Gut nehmen, die Handelsakteure als Knoten darstellen und die (Menge der) gehandelten Güter als (Eigenschaften der) Kanten darstellen. Das nachstehende Diagramm zeigt zum Beispiel den internationalen Handel mit Fisch im Jahr 1998(Quelldaten), wobei die Knoten Länder darstellen, die Größe der Knoten die Gesamtexporte pro Land und die Kanten die Tatsache, dass das Herkunftsland der Kante eine bestimmte Menge Fisch in das Zielland exportiert hat:

Da der internationale Handel von verschiedenen Faktoren wie Angebot und Nachfrage vor Ort, Zöllen oder Wechselkursen beeinflusst wird, könnte es interessant sein zu sehen, welche Handelsrouten zwischen Ländern gegenüber Alternativen bevorzugt werden. Zoomen Sie zum Beispiel auf einige der größeren Akteure,

wir würden gerne wissen, welches die bevorzugten Handelsrouten zwischen den Nachbarländern Großbritannien, Island und Norwegen sind. Generell wäre es schön, wenn wir solche Routen automatisch für das globale Handelsnetz auf einmal entdecken könnten. Wie lässt sich das bewerkstelligen?

Die einfache Lösung: Filtern nach Volumen

Als erstes Experiment könnten wir versuchen, einen Filter anzuwenden, der alle Verbindungen ausschließt, bei denen das Handelsvolumen nicht zu den obersten 1 % gehört. Dies führt zu folgendem Ergebnis (nach erneuter Anwendung des Layouts für die Grafik):

Daraus können wir lernen, dass es nur eine kleine Gruppe von Ländern gibt, zwischen denen der meiste Fischhandel stattfindet, in absoluten Zahlen. Allerdings können wir die zuvor gestellte Frage nicht beantworten, denn durch die Anwendung des volumenbasierten Filters haben wir bereits jegliche Verbindung zwischen Island und unseren "Kernländern" (und mehr als 80% der anderen Länder, die in der obigen Abbildung nicht angezeigt werden) verloren. Wenn wir das Experiment fortsetzen, können wir den Filter herabsetzen, um die Verbindungen mit den obersten 5 Prozent des Handelsvolumens durchzulassen, was zu dem folgenden Ergebnis führt:

Wie man sieht, hat die Herabsetzung der Volumenschwelle nur die Komplexität des Netzwerks zwischen den großen Exporteuren/Importeuren von Fisch erhöht und kaum neue Erkenntnisse über bevorzugte Handelsrouten mit Ländern in der Peripherie des Netzwerks geliefert. Daraus können wir schließen, dass die einfache Filterung nach dem Handelsvolumen zwei große Probleme hat:

• Je nach gewähltem Schwellenwert wird entweder der größte Teil des Netzwerks komplett verworfen oder der verbundene Teil wird so komplex, dass es schwierig wird, die bevorzugten Routen zu finden,
• Die Wahl eines bestimmten Schwellenwertes erfordert im besten Fall Fachwissen und ist im schlechtesten Fall völlig willkürlich.

Eine fortschrittlichere (aber elegante) Lösung: Link Salience

Letztes Jahr wurde in Nature Communications eine Arbeit veröffentlicht , die sich mit den oben genannten Problemen befasst. Darin wird eine Methode zum automatischen Auffinden von"auffälligen" Links in Netzwerken beschrieben, die auf dem folgenden Ansatz beruht:

1. Wählen Sie eine Eigenschaft, die das Gewicht einer Kante in einem bestimmten Netzwerk definiert,
2. Definieren Sie den Abstand zwischen zwei Knoten als 1 / das Gewicht,
3. Nehmen Sie einen Knoten und berechnen Sie anhand des oben genannten Abstandsmaßes den kürzesten Weg zu allen anderen Knoten im Netzwerk,
4. Kombinieren Sie alle Kanten aus dem vorherigen Schritt zu einer Menge, die als kürzester Pfadbaum (SPT) bezeichnet wird,
5. Erhöhen Sie für jede Kante in der SPT einen Zähler für die "Auffälligkeit",
6. Wiederholen Sie die Schritte 3-5 für jeden anderen Knoten im Netzwerk,
7. Teilen Sie für jede Kante den Zähler für die Wichtigkeit durch die Gesamtzahl der Knoten im Netzwerk, was zu einer Wichtigkeitseigenschaft mit einem Wert im Bereich [0..1] führt.

In dem Papier wird behauptet, dass (u.a.) bei Netzwerken, in denen die Knotengrade und Kantengewichte nach einem Potenzgesetz verteilt sind, die Wichtigkeit der Kanten eine bimodale Verteilung aufweist, mit Clustern nahe den Werten 0 und 1. Dies ist eine schöne Eigenschaft, denn sie kann nun als (nahezu) binärer Klassifikator für die Wichtigkeit von Netzwerkverbindungen verwendet werden. Wenn wir zum Beispiel dasselbe Fischnetzwerk nehmen und die Verbindungen auf der Grundlage der obersten 5 % der Link-Salienz filtern (anstelle unseres vorherigen Versuchs, d.h. der Kantenfilterung auf der Grundlage des absoluten Gewichts), erhalten wir das folgende Bild:

Und wenn wir näher herangehen, um eine Antwort auf unsere ursprüngliche Frage zu finden, stellen wir fest, dass Island lieber Fisch aus Norwegen als direkt aus Großbritannien importiert:

Wie wir sehen, hat das Filtern auf der Grundlage der Bedeutung zwei deutliche Vorteile gegenüber dem Filtern auf der Grundlage absoluter Kantengewichte:

• Es erfordert keine Parameter. Das einzige erforderliche Domänenwissen ist die Auswahl der Eigenschaft, die als Kantengewicht für die Berechnung der Salienz verwendet werden soll,
• In einem natürlichen Netzwerk, wie es hier besprochen wird, führt die Auswahl der obersten paar Prozent der Kanten mit der höchsten Bedeutung zu einem fast vollständig verbundenen Netzwerk, in dem die meisten Routen zwischen zwei beliebigen Knoten einzigartig sind.

Andere Anwendungen

In dem oben erwähnten Artikel über die Bedeutung von Links werden verschiedene Anwendungen erwähnt, z. B. im Flugverkehr und in Lebensmittelketten. Die Entdeckung hervorstechender Links im Flugverkehr kann helfen, den Ausbruch von Krankheiten einzudämmen, während wir bei Nahrungsketten lernen können, wie das Entfernen bestimmter Knoten eine komplette Nahrungskette unterbrechen kann. Ein weiterer interessanter Bereich ist die Analyse von IT-Netzwerken: Durch die Entdeckung hervorstechender Links in einem komplexen Netzwerk (z.B. auf der Grundlage des Netzwerkverkehrs) können wir lernen, für welche Verbindungen eine niedrige Latenz am wichtigsten ist, und unsere Bemühungen zur Leistungsoptimierung auf diese Verbindungen konzentrieren.

Möchten Sie es selbst ausprobieren?

Wir haben ein Plugin für die Neo4j-Graphdatenbank entwickelt, das die Link Salience für Ihr Netzwerk berechnen kann. Den Quellcode und die Installationsanweisungen finden Sie in diesem Github-Repository.