Kapitel 4. Pfadfindungs- und Graphensuchalgorithmen

Diese Arbeit wurde mithilfe von KI übersetzt. Wir freuen uns über dein Feedback und deine Kommentare: translation-feedback@oreilly.com

Graphen-Suchalgorithmen erforschen einen Graphen entweder zur allgemeinen Entdeckung oder zur expliziten Suche.Diese Algorithmen schneiden Pfade durch den Graphen, aber es wird nicht erwartet, dass diese Pfade rechnerisch optimal sind. Wir werden die Breadth First Search und die Depth First Search behandeln, weil sie grundlegend für die Durchquerung eines Graphen sind und oft ein notwendiger erster Schritt für viele andere Arten von Analysen sind.

Pfadfindungsalgorithmen bauen auf Graphen-Suchalgorithmen auf und erkunden Routen zwischen Knoten, indem sie an einem Knoten beginnen und Beziehungen durchlaufen, bis das Ziel erreicht ist. Diese Algorithmen werden verwendet, um optimale Routen durch einen Graphen zu ermitteln, z. B. für die Logistikplanung, das Least-Cost-Call- oder IP-Routing und die Spielsimulation.

Die Algorithmen zur Wegfindung, die wir behandeln werden, sind im Einzelnen

Kürzester Weg, mit zwei nützlichen Varianten (A* und Yen's): Suche nach dem kürzesten Weg oder den kürzesten Wegen zwischen zwei ausgewählten Knotenpunkten
Kürzester Weg für alle Paare und kürzester Weg für eine Quelle: Um die kürzesten Wege zwischen allen Paaren oder von einem ausgewählten Knoten zu allenanderen zu finden
Minimum Spanning Tree: Um eine zusammenhängende Baumstruktur mit den geringsten Kosten für den Besuch aller Knoten von einem gewählten Knoten aus zu finden
Random Walk: Weil es ein nützlicher Vorverarbeitungs-/Sampling-Schritt für Workflows des maschinellen Lernens und andere Graphenalgorithmen ist

In diesem Kapitel erklären wir, wie diese Algorithmen funktionieren und zeigen Beispiele in Spark und Neo4j. Wenn ein Algorithmus nur auf einer Plattform verfügbar ist, stellen wir nur dieses eine Beispiel vor oder zeigen, wie du unsere Implementierung anpassen kannst.

Abbildung 4-1 zeigt die wichtigsten Unterschiede zwischen diesen Algorithmen und Tabelle 4-1 gibt einen schnellen Überblick über die Berechnungen der einzelnen Algorithmen mit einem Anwendungsbeispiel.

Tabelle 4-1. Überblick über Pfadfindungs- und Graphensuchalgorithmen
Algorithmus-Typ	Was sie tut	Beispiel Verwendung	Beispiel Spark	Neo4j Beispiel
Breitensuche zuerst	Durchläuft eine Baumstruktur, indem er die nächstgelegenen Nachbarn und dann deren Nachbarn auf den unteren Ebenen erkundet	Ortung von Nachbarknoten in GPS-Systemen, um nahe gelegene Orte von Interesse zu identifizieren	Ja	Nein
Suche in der Tiefe	Durchläuft eine Baumstruktur, indem er jeden Zweig so weit wie möglich erkundet, bevor er wieder zurückgeht	Entdeckung eines optimalen Lösungsweges in Spielsimulationen mit hierarchischen Wahlmöglichkeiten	Nein	Nein
Kürzester Weg Variationen:A*, Yen's	Berechnet den kürzesten Weg zwischen einem Paar von Knoten	Suche nach Wegbeschreibungen zwischen zwei Orten	Ja	Ja
Alle Paare Kürzester Weg	Berechnet den kürzesten Weg zwischen allen Knotenpaaren im Graphen	Prüfung alternativer Routen um einen Stau herum	Ja	Ja
Einzelne Quelle Kürzester Weg	Berechnet den kürzesten Weg zwischen einem einzelnen Wurzelknoten und allen anderen Knoten	Least Cost Routing von Anrufen	Ja	Ja
Minimum Spanning Tree	Berechnet den Pfad in einer zusammenhängenden Baumstruktur mit den geringsten Kosten für den Besuch aller Knotenpunkte	Optimierung der angeschlossenen Streckenführung, z. B. Kabelverlegung oder Speicherbereinigung	Nein	Ja
Random Walk	Liefert eine Liste von Knoten entlang eines Pfades der angegebenen Größe, indem die Beziehungen, die durchlaufen werden, zufällig ausgewählt werden.	Erweitertes Training für maschinelles Lernen oder Daten für Graphenalgorithmen.	Nein	Ja

Zunächst werfen wir einen Blick auf den Datensatz für unsere Beispiele und gehen durch, wie die Daten in Apache Spark und Neo4j importiert werden. Für jeden Algorithmus beginnen wir mit einer kurzen Beschreibung des Algorithmus und allen relevanten Informationen zu seiner Funktionsweise. Die meisten Abschnitte enthalten auch Hinweise, wann verwandte Algorithmen verwendet werden sollten. Am Ende jedes Algorithmus-Abschnitts stellen wir einen funktionierenden Beispielcode mit dem Beispieldatensatz bereit.

Lass uns loslegen!

Beispieldaten: Das Transportdiagramm

Alle zusammenhängenden Daten enthalten Pfade zwischen den Knoten. Deshalb sind Suche und Pfadfindung die Ausgangspunkte für die Graphenanalyse. Verkehrsdatensätze veranschaulichen diese Beziehungen auf intuitive und zugängliche Weise. Die Beispiele in diesem Kapitel laufen auf einem Graphen, der eine Teilmenge des europäischen Straßennetzes enthält. Du kannst die Knoten- und Beziehungsdateien aus dem GitHub-Repository des Buches herunterladen.

Tabelle 4-2. *transport-nodes.csv*
id	Breitengrad	Längengrad	Bevölkerung
Amsterdam	52.379189	4.899431	821752
Utrecht	52.092876	5.104480	334176
Den Haag	52.078663	4.288788	514861
Immingham	53.61239	-0.22219	9642
Doncaster	53.52285	-1.13116	302400
Hoek van Holland	51.9775	4.13333	9382
Felixstowe	51.96375	1.3511	23689
Ipswich	52.05917	1.15545	133384
Colchester	51.88921	0.90421	104390
London	51.509865	-0.118092	8787892
Rotterdam	51.9225	4.47917	623652
Gouda	52.01667	4.70833	70939

Tabelle 4-3. *transport-relationships.csv*
src	dst	Beziehung	Kosten
Amsterdam	Utrecht	EROAD	46
Amsterdam	Den Haag	EROAD	59
Den Haag	Rotterdam	EROAD	26
Amsterdam	Immingham	EROAD	369
Immingham	Doncaster	EROAD	74
Doncaster	London	EROAD	277
Hoek van Holland	Den Haag	EROAD	27
Felixstowe	Hoek van Holland	EROAD	207
Ipswich	Felixstowe	EROAD	22
Colchester	Ipswich	EROAD	32
London	Colchester	EROAD	106
Gouda	Rotterdam	EROAD	25
Gouda	Utrecht	EROAD	35
Den Haag	Gouda	EROAD	32
Hoek van Holland	Rotterdam	EROAD	33

Abbildung 4-2 zeigt den Zielgraphen, den wir konstruieren wollen.

Der Einfachheit halber betrachten wir den Graphen in Abbildung 4-2 als ungerichtet, da die meisten Straßen zwischen den Städten in beide Richtungen verlaufen. Wir würden etwas andere Ergebnisse erhalten, wenn wir den Graphen als gerichtet bewerten würden, da es nur wenige Einbahnstraßen gibt, aber der Gesamtansatz bleibt ähnlich. Sowohl Spark als auch Neo4j arbeiten jedoch mit gerichteten Graphen. In Fällen wie diesem, in denen wir mit ungerichteten Graphen arbeiten wollen (z. B. mit Straßen in beide Richtungen), gibt es eine einfache Möglichkeit, dies zu erreichen:

Für Spark erstellen wir zwei Beziehungen für jede Zeile in transport-relationships.csv - einevon dst zu src und eine von src zu dst.
Für Neo4j erstellen wir eine einzelne Beziehung und ignorieren dann die Beziehungsrichtung, wenn wir die Algorithmen ausführen.

Nachdem wir diese kleinen Workarounds für die Modellierung verstanden haben, können wir jetzt damit beginnen, Graphen aus den CSV-Dateien in Spark und Neo4j zu laden.

Importieren der Daten in Apache Spark

Wir beginnen mit Spark und importieren zunächst die Pakete, die wir von Spark und dem GraphFrames-Paket benötigen:

from pyspark.sql.types import *
from graphframes import *

Die folgende Funktion erstellt einen GraphFrame aus den Beispiel-CSV-Dateien:

def create_transport_graph():
    node_fields = [
        StructField("id", StringType(), True),
        StructField("latitude", FloatType(), True),
        StructField("longitude", FloatType(), True),
        StructField("population", IntegerType(), True)
    ]
    nodes = spark.read.csv("data/transport-nodes.csv", header=True,
                           schema=StructType(node_fields))

    rels = spark.read.csv("data/transport-relationships.csv", header=True)
    reversed_rels = (rels.withColumn("newSrc", rels.dst)
                     .withColumn("newDst", rels.src)
                     .drop("dst", "src")
                     .withColumnRenamed("newSrc", "src")
                     .withColumnRenamed("newDst", "dst")
                     .select("src", "dst", "relationship", "cost"))

    relationships = rels.union(reversed_rels)

    return GraphFrame(nodes, relationships)

Das Laden der Knoten ist einfach, aber für die Beziehungen müssen wir ein wenig Vorarbeit leisten, damit wir jede Beziehung zweimal erstellen können.

Rufen wir nun diese Funktion auf:

g = create_transport_graph()

Importieren der Daten in Neo4j

Nun zu Neo4j. Wir beginnen mit der Erstellung einer Datenbank, die wir für die Beispiele in diesem Kapitel verwenden werden:

:use system; 
CREATE DATABASE chapter4; 
:use chapter4;

: Wechsle zur Systemdatenbank.
: Erstelle eine neue Datenbank mit dem Namen chapter4. Dieser Vorgang ist asynchron, daher müssen wir möglicherweise ein paar Sekunden warten, bevor wir zur Datenbank wechseln.
: Wechsle zur Datenbank chapter4.

Jetzt laden wir die Knotenpunkte:

WITH 'https://github.com/neo4j-graph-analytics/book/raw/master/data/' AS base
WITH base + 'transport-nodes.csv' AS uri
LOAD CSV WITH HEADERS FROM uri  AS row
MERGE (place:Place {id:row.id})
SET place.latitude = toFloat(row.latitude),
    place.longitude = toFloat(row.longitude),
    place.population = toInteger(row.population);

Und jetzt die Beziehungen:

WITH 'https://github.com/neo4j-graph-analytics/book/raw/master/data/' AS base
WITH base + 'transport-relationships.csv' AS uri
LOAD CSV WITH HEADERS FROM uri AS row
MATCH (origin:Place {id: row.src})
MATCH (destination:Place {id: row.dst})
MERGE (origin)-[:EROAD {distance: toInteger(row.cost)}]->(destination);

Obwohl wir gerichtete Beziehungen speichern, werden wir die Richtung ignorieren, wenn wir später im Kapitel Algorithmen ausführen.

Breitensuche zuerst

Breadth First Search (BFS) ist einer der grundlegenden Algorithmen zur Durchquerung von Graphen, der von einem ausgewählten Knoten ausgeht und alle seine Nachbarn in einer Entfernung von einem Hop erkundet, bevor er alle Nachbarn in einer Entfernung von zwei Hops besucht, und so weiter.

Der Algorithmus wurde erstmals 1959 von Edward F. Moore veröffentlicht, der ihn benutzte, um den kürzesten Weg aus einem Labyrinth zu finden.Er wurde dann 1961 von C. Y. Lee zu einem Routing-Algorithmus für Leitungen weiterentwickelt, wie in "An Algorithm for Path Connections and Its Applications" beschrieben .

Der BFS-Algorithmus wird meist als Grundlage für andere, zielorientiertere Algorithmen verwendet. So nutzen zum Beispiel der kürzeste Weg, die Connected Components und die Closeness Centrality alle den BFS-Algorithmus. Er kann auch verwendet werden, um den kürzesten Weg zwischen Knoten zu finden.

Abbildung 4-3 zeigt die Reihenfolge, in der wir die Knoten unseres Transportgraphen besuchen würden, wenn wir eine Breitensuche durchführen würden, die in der niederländischen Stadt Den Haag (auf Englisch: The Hague) beginnt. Die Zahlen neben den Städtenamen geben die Reihenfolge an, in der die einzelnen Knoten besucht werden.

Wir besuchen zuerst alle direkten Nachbarn von Den Haag, dann ihre Nachbarn und die Nachbarn ihrer Nachbarn, bis wir keine Beziehungen mehr haben, die wir durchqueren können.

Breadth First Search mit Apache Spark

Die Spark-Implementierung des Breadth-First-Search-Algorithmus findet den kürzesten Weg zwischen zwei Knoten anhand der Anzahl der Beziehungen (d.h. der Hops) zwischen ihnen. Du kannst deinen Zielknoten explizit benennen oder Kriterien hinzufügen, die erfüllt werden müssen.

Wir können zum Beispiel die Funktion bfs verwenden, um die erste mittelgroße (nach europäischen Maßstäben) Stadt mit einer Einwohnerzahl zwischen 100.000 und 300.000 zu finden. Überprüfen wir zunächst, welche Orte eine Einwohnerzahl haben, die diesen Kriterien entspricht:

(g.vertices
 .filter("population > 100000 and population < 300000")
 .sort("population")
 .show())

Das ist die Ausgabe, die wir sehen werden:

id	Breitengrad	Längengrad	Bevölkerung
Colchester	51.88921	0.90421	104390
Ipswich	52.05917	1.15545	133384

Es gibt nur zwei Orte, die unseren Kriterien entsprechen, und wir würden erwarten, dass wir Ipswich zuerst erreichen, wenn wir zuerst in der Breite suchen.

Der folgende Code findet den kürzesten Weg von Den Haag zu einer mittelgroßen Stadt:

from_expr = "id='Den Haag'"
to_expr = "population > 100000 and population < 300000 and id <> 'Den Haag'"
result = g.bfs(from_expr, to_expr)

result enthält Spalten, die die Knotenpunkte und Beziehungen zwischen den beiden Städten beschreiben. Wir können den folgenden Code ausführen, um die Liste der zurückgegebenen Spalten zu sehen:

print(result.columns)

Das ist die Ausgabe, die wir sehen werden:

['from', 'e0', 'v1', 'e1', 'v2', 'e2', 'to']

Spalten, die mit e beginnen, stehen für Beziehungen (Kanten) und Spalten, die mit v beginnen, für Knoten (Scheitelpunkte). Da uns nur die Knoten interessieren, filtern wir alle Spalten, die mit e beginnen, aus dem resultierenden Datenrahmen heraus:

columns = [column for column in result.columns if not column.startswith("e")]
result.select(columns).show()

Wenn wir den Code in pyspark ausführen, sehen wir diese Ausgabe:

von	v1	v2	zu
[Den Haag, 52.078...	[Hoek van Holland...	[Felixstowe, 51.9...	[Ipswich, 52.0591...

Wie erwartet liefert der bfs Algorithmus Ipswich! Erinnere dich daran, dass diese Funktion zufrieden ist, wenn sie die erste Übereinstimmung findet, und wie du in Abbildung 4-3 sehen kannst, wird Ipswich vor Colchester ausgewertet.

Suche in der Tiefe

Depth First Search (DFS) ist ein weiterer grundlegender Algorithmus zur Durchquerung von Graphen, der von einem ausgewählten Knoten ausgeht, einen seiner Nachbarn auswählt und dann diesen Pfad so weit wie möglich durchquert, bevor er wieder zurückgeht.

Das DFS wurde ursprünglich von dem französischen Mathematiker Charles Pierre Trémaux als Strategie zum Lösen von Labyrinthen erfunden. Sie ist ein nützliches Werkzeug, um mögliche Wege für die Modellierung von Szenarien zu simulieren. Abbildung 4-4 zeigt die Reihenfolge, in der wir die Knoten unseres Transportgraphen besuchen würden, wenn wir eine DFS durchführen würden, die in Den Haag beginnt.

Beachte, wie unterschiedlich die Reihenfolge der Knoten im Vergleich zum BFS ist. Bei diesem DFS beginnen wir mit der Durchquerung von Den Haag nach Amsterdam und können dann zu jedem anderen Knoten im Graphen gelangen, ohne überhaupt zurückgehen zu müssen!

Wir können sehen, wie Suchalgorithmen die Grundlage für die Bewegung durch Graphen legen. Sehen wir uns nun die Algorithmen zur Wegfindung an, die den günstigsten Weg in Bezug auf die Anzahl der Sprünge oder die Gewichtung finden. Gewichte können alles sein, was gemessen wird, wie Zeit, Entfernung, Kapazität oder Kosten.

Zwei besondere Pfade/Zyklen

In der Graphenanalyse gibt es zwei besondere Pfade, die erwähnenswert sind. Erstens: Ein Eulerscher Pfad ist ein Pfad, bei dem jede Beziehung genau einmal besucht wird. Zweitens: Ein Hamilton-Pfad ist ein Pfad, bei dem jeder Knoten genau einmal besucht wird. Ein Pfad kann sowohl eulerisch als auch hamiltonisch sein, und wenn du am selben Knotenpunkt beginnst und endest, wird er als Zyklus oder Tour bezeichnet. Ein visueller Vergleich wird in Abbildung 4-5 gezeigt.

Abbildung 4-5. Eulersche und Hamiltonsche Zyklen haben eine besondere historische Bedeutung.

Das Königsberger Brückenproblem aus Kapitel 1 war die Suche nach einem Eulerschen Kreislauf. Es ist leicht einzusehen, dass dies auch für Routing-Szenarien wie die Steuerung von Schneepflügen oder die Postzustellung gilt. Eulersche Pfade werden aber auch von anderen Algorithmen zur Verarbeitung von Daten in Baumstrukturen verwendet und sind mathematisch einfacher zu untersuchen als andere Zyklen.

Der Hamilton-Zyklus ist vor allem durch seine Beziehung zum Traveling Salesman Problem (TSP) bekannt, bei dem es um die Frage geht: "Welches ist die kürzestmögliche Route für einen Verkäufer, um jede seiner zugewiesenen Städte zu besuchen und zur Ausgangsstadt zurückzukehren?" Obwohl das TSP auf den ersten Blick einer Euler'schen Tour ähnelt, ist es rechenintensiver und bietet mehr Alternativen zur Annäherung. Es wird bei einer Vielzahl von Planungs-, Logistik- und Optimierungsproblemen eingesetzt .

Kürzester Weg

Der Shortest Path Algorithmus berechnet den kürzesten (gewichteten) Pfad zwischen zwei Knotenpunkten. Er ist nützlich für Benutzerinteraktionen und dynamische Workflows, da er in Echtzeit arbeitet.

Die Pfadfindung hat eine Geschichte, die bis ins 19. Jahrhundert zurückreicht, und gilt als klassisches Graphenproblem. In den frühen 1950er Jahren erlangte sie im Zusammenhang mit der alternativen Routenplanung, d.h. der Suche nach der zweitkürzesten Route, wenn die kürzeste Route blockiert ist, große Bedeutung.Im Jahr 1956 entwickelte Edsger Dijkstra den bekanntesten dieser Algorithmen.

Der Dijkstra-Algorithmus für den kürzesten Weg ermittelt zunächst die Beziehung mit der geringsten Gewichtung zwischen dem Startknoten und den direkt verbundenen Knoten. Er behält diese Gewichte im Auge und bewegt sich zum "nächstgelegenen" Knoten. Der Algorithmus fährt damit fort, indem er eine "Welle" von kumulativen Gewichtungen auswertet und immer den kumulativen Pfad mit der niedrigsten Gewichtung wählt, bis er den Zielknoten erreicht.

Hinweis

In der Diagrammanalyse werden die Begriffe Gewicht, Kosten, Entfernung und Sprung verwendet, um Beziehungen und Pfade zu beschreiben. "Gewicht" ist der numerische Wert einer bestimmten Eigenschaft einer Beziehung."Kosten" wird ähnlich verwendet, aber wir sehen es häufiger, wenn wir das Gesamtgewicht eines Pfades betrachten.

"Entfernung" wird in einem Algorithmus oft als Name für die Beziehungseigenschaft verwendet, die die Kosten für die Durchquerung eines Knotenpaares angibt. Es ist nicht erforderlich, dass es sich dabei um ein physikalisches Maß für die Entfernung handelt. "Hop" wird häufig verwendet, um die Anzahl der Beziehungen zwischen zwei Knoten auszudrücken. Manchmal werden diese Begriffe auch kombiniert, z. B. in "Die Entfernung nach London beträgt fünf Hüpfer" oder "Das sind die niedrigsten Kosten für die Entfernung".

Wann sollte ich den kürzesten Weg verwenden?

Verwende den kürzesten Weg, um optimale Routen zwischen zwei Knoten zu finden, die entweder auf der Anzahl der Hops oder einem gewichteten Beziehungswert basieren. Er kann zum Beispiel Echtzeit-Antworten über den Trennungsgrad, die kürzeste Entfernung zwischen Punkten oder die kostengünstigste Route liefern. Du kannst diesen Algorithmus auch verwenden, um einfach die Verbindungen zwischen bestimmten Knoten zu untersuchen.

Beispiele für Anwendungsfälle sind:

Wegbeschreibungen zwischen Orten finden. Web-Mapping-Tools wie Google Maps verwenden den Algorithmus des kürzesten Weges oder eine ähnliche Variante, um eine Wegbeschreibung zu erstellen.
Finde den Trennungsgrad zwischen Personen in sozialen Netzwerken. Wenn du dir zum Beispiel das Profil einer Person auf LinkedIn ansiehst, wird angezeigt, wie viele Personen euch im Graphen trennen, und es werden eure gemeinsamen Verbindungen aufgelistet.
Die Anzahl der Trennungsgrade zwischen einem Schauspieler und Kevin Bacon auf der Grundlage der Filme, in denen sie aufgetreten sind (die Bacon-Nummer). Ein Beispiel dafür findest du auf der Website Oracle of Bacon.Das Erdös Number Project bietet eine ähnliche Graphenanalyse, die auf der Zusammenarbeit mit Paul Erdös, einem der produktivsten Mathematiker des 20.

Tipp

Dijkstras Algorithmus unterstützt keine negativen Gewichte. Der Algorithmus geht davon aus, dass das Hinzufügen einer Beziehung zu einem Pfad niemals einen Pfad kürzer machen kann - eine Invariante, die mit negativen Gewichten verletzt würde.

Kürzester Weg mit Neo4j

Die Neo4j Graph Data Science Bibliothek hat ein eingebautes Verfahren, mit dem wir sowohl ungewichtete als auch gewichtete kürzeste Pfade berechnen können. Lernen wir zunächst, wie man ungewichtete kürzeste Pfade berechnet.

Der Shortest Path Algorithmus von Neo4j nimmt eine Config Map mit den folgenden Schlüsseln auf:

startNode: Der Knoten, an dem unsere Suche nach dem kürzesten Weg beginnt.
endNode: Der Knoten, an dem unsere Suche nach dem kürzesten Weg endet.
nodeProjection: Ermöglicht die Abbildung bestimmter Arten von Knoten in den In-Memory-Graphen. Wir können eine oder mehrere Knotenbeschriftungen deklarieren.
relationshipProjection: Ermöglicht das Mapping von Beziehungstypen in den In-Memory-Graphen. Wir können einen oder mehrere Beziehungstypen zusammen mit der Richtung und den Eigenschaften deklarieren.
relationshipWeightProperty: Die Beziehungseigenschaft, die die Kosten für die Überquerung zwischen zwei Knoten angibt. Die Kosten sind die Anzahl der Kilometer zwischen zwei Orten.

Damit der Shortest Path Algorithmus von Neo4j die Gewichte ignoriert, setzen wir den Schlüssel relationshipWeightProperty nicht. Der Algorithmus nimmt dann für jede Beziehung ein Standardgewicht von 1.0 an.

Die folgende Abfrage berechnet den ungewichteten kürzesten Weg von Amsterdam nach London:

MATCH (source:Place {id: "Amsterdam"}),
      (destination:Place {id: "London"})

CALL gds.alpha.shortestPath.stream({
  startNode: source,
  endNode: destination,
  nodeProjection: "*",
  relationshipProjection: {
    all: {
      type: "*",
      orientation:  "UNDIRECTED"
    }
  }
})
YIELD nodeId, cost
RETURN gds.util.asNode(nodeId).id AS place, cost;

In dieser Abfrage übergeben wir nodeProjection: "*", was bedeutet, dass alle Knotenbeschriftungen berücksichtigt werden sollen. Die relationshipProjection ist etwas komplizierter. Wir verwenden den erweiterten Konfigurationsmodus, der eine flexiblere Definition der Beziehungstypen ermöglicht, die beim Traversal berücksichtigt werden sollen. Schauen wir uns die Werte an, die wir übergeben haben:

type: "*": Alle Beziehungsarten sollten berücksichtigt werden.
orientation: "UNDIRECTED": Jede Beziehung in der zugrunde liegenden Grafik wird in beide Richtungen projiziert.

Hinweis

Eine ausführlichere Dokumentation zu Knoten- und Beziehungsprojektionen findest du im Kapitel Native Projection des Graph Data Science Benutzerhandbuchs.

Diese Abfrage liefert die folgende Ausgabe:

Platz	Kosten
Amsterdam	0.0
Immingham	1.0
Doncaster	2.0
London	3.0

Hier sind die Kosten die kumulierte Summe der Beziehungen (oder Hops). Das ist derselbe Weg, den wir bei der Breadth First Search in Spark sehen.

Wir können sogar die Gesamtentfernung für diesen Weg berechnen, indem wir ein kleines Postprocessing für Cypher schreiben. Die folgende Prozedur berechnet den kürzesten ungewichteten Weg und berechnet dann, wie hoch die tatsächlichen Kosten für diesen Weg wären:

MATCH (source:Place {id: "Amsterdam"}),
      (destination:Place {id: "London"})

CALL gds.alpha.shortestPath.stream({
  startNode: source,
  endNode: destination,
  nodeProjection: "*",
  relationshipProjection: {
    all: {
      type: "*",
      orientation:  "UNDIRECTED"
    }
  }
})
YIELD nodeId, cost

WITH collect(gds.util.asNode(nodeId)) AS path
UNWIND range(0, size(path)-1) AS index
WITH path[index] AS current, path[index+1] AS next
WITH current, next, [(current)-[r:EROAD]-(next) | r.distance][0] AS distance

WITH collect({current: current, next:next, distance: distance}) AS stops
UNWIND range(0, size(stops)-1) AS index
WITH stops[index] AS location, stops, index
RETURN location.current.id AS place,
       reduce(acc=0.0,
              distance in [stop in stops[0..index] | stop.distance] |
              acc + distance) AS cost;

Wenn dir der vorherige Code etwas unhandlich vorkommt, solltest du wissen, dass der schwierige Teil darin besteht, die Daten so zu massieren, dass sie die Kosten für die gesamte Strecke enthalten. Das ist hilfreich, wenn wir die kumulierten Wegekosten benötigen.

Die Abfrage liefert das folgende Ergebnis:

Platz	Kosten
Amsterdam	0.0
Immingham	369.0
Doncaster	443.0
London	720.0

Abbildung 4-6 zeigt den ungewichteten kürzesten Weg von Amsterdam nach London, der uns durch die wenigsten Städte führt. Er hat Gesamtkosten von 720 km.

Die Wahl einer Route mit der geringsten Anzahl an besuchten Knotenpunkten kann in Situationen wie U-Bahn-Systemen, in denen weniger Haltestellen sehr wünschenswert sind, sehr nützlich sein. In einem Fahrszenario sind wir jedoch wahrscheinlich eher an den Gesamtkosten interessiert, wenn wir den kürzesten gewichteten Weg wählen.

Kürzester Weg (gewichtet) mit Neo4j

Wir können den Weighted Shortest Path Algorithmus ausführen, um den kürzesten Weg zwischen Amsterdam und London zu finden:

MATCH (source:Place {id: "Amsterdam"}),
      (destination:Place {id: "London"})

CALL gds.alpha.shortestPath.stream({
  startNode: source,
  endNode: destination,
  nodeProjection: "*",
  relationshipProjection: {
    all: {
      type: "*",
      properties: "distance",
      orientation:  "UNDIRECTED"
    }
  },
  relationshipWeightProperty: "distance"
})
YIELD nodeId, cost
RETURN gds.util.asNode(nodeId).id AS place, cost;

Wir übergeben nun die optionale relationshipWeightProperty, die den Namen der Beziehungseigenschaft angibt, die die Kosten für die Überquerung zwischen einem Knotenpaar angibt.

Die Kosten sind die Anzahl der Kilometer zwischen zwei Orten. Die Abfrage liefert das folgende Ergebnis:

Platz	Kosten
Amsterdam	0.0
Den Haag	59.0
Hoek van Holland	86.0
Felixstowe	293.0
Ipswich	315.0
Colchester	347.0
London	453.0

Die schnellste Route führt uns über Den Haag, Hoek van Holland, Felixstowe, Ipswich und Colchester! Die angezeigten Kosten sind die kumulierten Gesamtkosten, wenn wir durch die Städte fahren. Zuerst fahren wir von Amsterdam nach Den Haag, was 59 km kostet. Dann fahren wir von Den Haag nach Hoek van Holland, was 86 km kostet - und so weiter. Schließlich kommen wir von Colchester aus in London an, was insgesamt 453 km kostet.

Erinnere dich daran, dass der ungewichtete kürzeste Weg insgesamt 720 km gekostet hat. Wir konnten also 267 km einsparen, indem wir die Gewichte bei der Berechnung des kürzesten Weges berücksichtigt haben.

Kürzester Weg (gewichtet) mit Apache Spark

Im Abschnitt Breadth First Search mit Apache Spark haben wir gelernt, wie man den kürzesten Weg zwischen zwei Knoten findet. Dieser kürzeste Weg basiert auf Hops und ist daher nicht dasselbe wie der kürzeste gewichtete Weg, der uns die kürzeste Gesamtdistanz zwischen Städten anzeigen würde.

Wenn wir den kürzesten gewichteten Pfad (in diesem Fall die Entfernung) finden wollen, müssen wir die Eigenschaft cost verwenden, die für verschiedene Arten der Gewichtung genutzt wird.Diese Option ist bei GraphFrames nicht standardmäßig verfügbar, sodass wir unsere eigene Version von Weighted Shortest Path schreiben müssen, die das aggregateMessages Framework nutzt. Die meisten unserer Algorithmus-Beispiele für Spark verwenden den einfacheren Prozess des Aufrufs von Algorithmen aus der Bibliothek, aber wir haben auch die Möglichkeit, unsere eigenen Funktionen zu schreiben. Weitere Informationen zu aggregateMessages findest du im Abschnitt "Message passing via AggregateMessages" im GraphFrames Benutzerhandbuch.

Tipp

Wenn verfügbar, empfehlen wir, bereits vorhandene, getestete Bibliotheken zu nutzen. Das Schreiben eigener Funktionen, insbesondere für kompliziertere Algorithmen, erfordert ein tieferes Verständnis unserer Daten und Berechnungen.

Das folgende Beispiel sollte als Referenzimplementierung betrachtet werden und müsste optimiert werden, bevor es auf einen größeren Datensatz angewendet werden kann. Wer nicht daran interessiert ist, seine eigenen Funktionen zu schreiben, kann dieses Beispiel überspringen.

Bevor wir unsere Funktion erstellen, importieren wir einige Bibliotheken, die wir verwenden werden:

from graphframes.lib import AggregateMessages as AM
from pyspark.sql import functions as F

Das Modul aggregateMessages ist Teil der GraphFrames-Bibliothek und enthält einige nützliche Hilfsfunktionen.

Zuerst erstellen wir eine benutzerdefinierte Funktion, mit der wir die Pfade zwischen unserer Quelle und unserem Ziel erstellen:

add_path_udf = F.udf(lambda path, id: path + [id], ArrayType(StringType()))

Und nun zur Hauptfunktion, die den kürzesten Weg von einem Startpunkt aus berechnet und zurückkehrt, sobald das Ziel besucht worden ist:

def shortest_path(g, origin, destination, column_name="cost"):
    if g.vertices.filter(g.vertices.id == destination).count() == 0:
        return (spark.createDataFrame(sc.emptyRDD(), g.vertices.schema)
                .withColumn("path", F.array()))

    vertices = (g.vertices.withColumn("visited", F.lit(False))
                .withColumn("distance", F.when(g.vertices["id"] == origin, 0)
                            .otherwise(float("inf")))
                .withColumn("path", F.array()))
    cached_vertices = AM.getCachedDataFrame(vertices)
    g2 = GraphFrame(cached_vertices, g.edges)

    while g2.vertices.filter('visited == False').first():
        current_node_id = g2.vertices.filter('visited == False').sort
                                            ("distance").first().id

        msg_distance = AM.edge[column_name] + AM.src['distance']
        msg_path = add_path_udf(AM.src["path"], AM.src["id"])
        msg_for_dst = F.when(AM.src['id'] == current_node_id,
                             F.struct(msg_distance, msg_path))
        new_distances = g2.aggregateMessages(F.min(AM.msg).alias("aggMess"),
                                             sendToDst=msg_for_dst)

        new_visited_col = F.when(
            g2.vertices.visited | (g2.vertices.id == current_node_id),
                                                True).otherwise(False)
        new_distance_col = F.when(new_distances["aggMess"].isNotNull() &
                                 (new_distances.aggMess["col1"]
                                 < g2.vertices.distance),
                                 new_distances.aggMess["col1"])
                                 .otherwise(g2.vertices.distance)
        new_path_col = F.when(new_distances["aggMess"].isNotNull() &
                       (new_distances.aggMess["col1"]
                       < g2.vertices.distance), new_distances.aggMess["col2"]
                       .cast("array<string>")).otherwise(g2.vertices.path)

        new_vertices = (g2.vertices.join(new_distances, on="id",
                                         how="left_outer")
                        .drop(new_distances["id"])
                        .withColumn("visited", new_visited_col)
                        .withColumn("newDistance", new_distance_col)
                        .withColumn("newPath", new_path_col)
                        .drop("aggMess", "distance", "path")
                        .withColumnRenamed('newDistance', 'distance')
                        .withColumnRenamed('newPath', 'path'))
        cached_new_vertices = AM.getCachedDataFrame(new_vertices)
        g2 = GraphFrame(cached_new_vertices, g2.edges)
        if g2.vertices.filter(g2.vertices.id == destination).first().visited:
            return (g2.vertices.filter(g2.vertices.id == destination)
                    .withColumn("newPath", add_path_udf("path", "id"))
                    .drop("visited", "path")
                    .withColumnRenamed("newPath", "path"))
    return (spark.createDataFrame(sc.emptyRDD(), g.vertices.schema)
            .withColumn("path", F.array()))

Warnung

Wenn wir Verweise auf Datenrahmen in unseren Funktionen speichern, müssen wir sie mit der Funktion AM.getCachedDataFrame zwischenspeichern, sonst kommt es bei der Ausführung zu einem Speicherleck. In der Funktion shortest_path verwenden wir diese Funktion, um die Datenrahmen vertices und new_vertices zwischenzuspeichern.

Wenn wir den kürzesten Weg zwischen Amsterdam und Colchester finden wollen, können wir die Funktion wie folgt aufrufen:

result = shortest_path(g, "Amsterdam", "Colchester", "cost")
result.select("id", "distance", "path").show(truncate=False)

was das folgende Ergebnis liefern würde:

id	Entfernung	Pfad
Colchester	347.0	[Amsterdam, Den Haag, Hoek van Holland, Felixstowe, Ipswich, Colchester]

Die Gesamtdistanz des kürzesten Weges zwischen Amsterdam und Colchester beträgt 347 km und führt uns über Den Haag, Hoek van Holland, Felixstowe und Ipswich. Der kürzeste Weg in Bezug auf die Anzahl der Beziehungen zwischen den Orten, den wir mit dem Breadth First Search Algorithmus berechnet haben (siehe Abbildung 4-4), würde uns dagegen über Immingham, Doncaster und London führen.

Variation des kürzesten Weges: A*

Der A* Shortest Path Algorithmus verbessert den Dijkstra-Algorithmus, indem er kürzeste Pfade schneller findet, indem er zusätzliche Informationen einbezieht, die der Algorithmus als Teil einer heuristischen Funktion verwenden kann, um zu entscheiden, welche Pfade als nächstes untersucht werden sollen.

Der Algorithmus wurde von Peter Hart, Nils Nilsson und Bertram Raphael erfunden und 1968 in ihrer Arbeit "A Formal Basis for the Heuristic Determination of Minimum Cost Paths" beschrieben .

Der A*-Algorithmus bestimmt bei jeder Iteration seiner Hauptschleife, welcher seiner Teilpfade erweitert werden soll. Er tut dies auf der Grundlage einer Schätzung der Kosten (Heuristik), die noch übrig sind, um den Zielknoten zu erreichen.

Warnung

Sei vorsichtig bei der Heuristik, die du zur Schätzung der Pfadkosten verwendest. Wenn du die Pfadkosten unterschätzt, werden möglicherweise unnötigerweise einige Pfade einbezogen, die hätten eliminiert werden können, aber die Ergebnisse sind trotzdem genau. Wenn die Heuristik jedoch die Pfadkosten überschätzt, kann es passieren, dass sie kürzere Pfade (die fälschlicherweise als länger eingeschätzt werden) überspringt, die eigentlich hätten bewertet werden müssen, was zu ungenauen Ergebnissen führen kann.

A* wählt den Weg, der die folgende Funktion minimiert:

`f(n) = g(n) + h(n)`

wo:

g(n) sind die Kosten des Weges vom Startpunkt zum Knoten n.
h(n) sind die geschätzten Kosten des Weges vom Knoten n zum Zielknoten, die von einer Heuristik berechnet werden.

Hinweis

In der Neo4j-Implementierung wird die räumliche Distanz als Heuristik verwendet. In unserem Beispiel-Datensatz für Verkehrsmittel verwenden wir die geografische Breite und Länge jedes Ortes als Teil der Heuristikfunktion.

A* mit Neo4j

Der A*-Algorithmus von Neo4j nimmt eine Config-Map mit den folgenden Schlüsseln auf:

startNode: Der Knoten, an dem unsere Suche nach dem kürzesten Weg beginnt.
endNode: Der Knoten, an dem unsere Suche nach dem kürzesten Weg endet.
nodeProjection: Ermöglicht die Abbildung bestimmter Arten von Knoten in den In-Memory-Graphen. Wir können eine oder mehrere Knotenbeschriftungen deklarieren.
relationshipProjection: Ermöglicht das Mapping von Beziehungstypen in den In-Memory-Graphen. Wir können einen oder mehrere Beziehungstypen zusammen mit der Richtung und den Eigenschaften deklarieren.
relationshipWeightProperty: Die Beziehungseigenschaft, die die Kosten für die Überquerung zwischen zwei Knoten angibt. Die Kosten sind die Anzahl der Kilometer zwischen zwei Orten.
propertyKeyLat: Der Name der Knoteneigenschaft, die verwendet wird, um den Breitengrad jedes Knotens als Teil der georäumlichen heuristischen Berechnung darzustellen.
propertyKeyLon: Der Name der Knoteneigenschaft, die verwendet wird, um den Längengrad eines jeden Knotens als Teil der georäumlichen heuristischen Berechnung darzustellen.

Die folgende Abfrage führt den A*-Algorithmus aus, um den kürzesten Weg zwischen Den Haag und London zu finden:

MATCH (source:Place {id: "Den Haag"}),
      (destination:Place {id: "London"})
CALL gds.alpha.shortestPath.astar.stream({
  startNode: source,
  endNode: destination,
  nodeProjection: "*",
  relationshipProjection: {
    all: {
      type: "*",
      properties: "distance",
      orientation:  "UNDIRECTED"
    }
  },
  relationshipWeightProperty: "distance",
  propertyKeyLat: "latitude",
  propertyKeyLon: "longitude"
})
YIELD nodeId, cost
RETURN gds.util.asNode(nodeId).id AS place, cost;

Wenn du diese Prozedur ausführst, erhältst du das folgende Ergebnis:

Platz	Kosten
Den Haag	0.0
Hoek van Holland	27.0
Felixstowe	234.0
Ipswich	256.0
Colchester	288.0
London	394.0

Mit dem Shortest Path Algorithmus würden wir das gleiche Ergebnis erhalten, aber bei komplexeren Datensätzen ist der A*-Algorithmus schneller, da er weniger Pfade auswertet.

Variation der kürzesten Wege: Yen's k-Kürzeste Pfade

Yen's k-Shortest Paths Algorithmus ähnelt dem Shortest Path Algorithmus, aber anstatt nur den kürzesten Weg zwischen zwei Knotenpaaren zu finden, berechnet er auch den zweitkürzesten Weg, den drittkürzesten Weg und so weiter bis zu k-1 Abweichungen der kürzesten Wege.

Jin Y. Yen erfand den Algorithmus 1971 und beschrieb ihn in "Finding the K Shortest Loopless Paths in a Network". Dieser Algorithmus ist nützlich, um alternative Pfade zu finden, wenn die Suche nach dem absolut kürzesten Pfad nicht unser einziges Ziel ist. Er kann besonders hilfreich sein, wenn wir mehr als einen Ausweichplan brauchen!

Yen ist mit Neo4j

Der Algorithmus von Yen nimmt eine Konfigurationskarte mit den folgenden Schlüsseln auf:

startNode: Der Knoten, an dem unsere Suche nach dem kürzesten Weg beginnt.
endNode: Der Knoten, an dem unsere Suche nach dem kürzesten Weg endet.
nodeProjection: Ermöglicht die Abbildung bestimmter Arten von Knoten in den In-Memory-Graphen. Wir können eine oder mehrere Knotenbeschriftungen deklarieren.
relationshipProjection: Ermöglicht das Mapping von Beziehungstypen in den In-Memory-Graphen. Wir können einen oder mehrere Beziehungstypen zusammen mit der Richtung und den Eigenschaften deklarieren.
relationshipWeightProperty: Die Beziehungseigenschaft, die die Kosten für die Überquerung zwischen zwei Knoten angibt. Die Kosten sind die Anzahl der Kilometer zwischen zwei Orten.
k: Die maximale Anzahl der zu findenden kürzesten Wege.

Die folgende Abfrage führt den Algorithmus von Yen aus, um die kürzesten Wege zwischen Gouda und Felixstowe zu finden:

MATCH (start:Place {id:"Gouda"}),
      (end:Place {id:"Felixstowe"})

CALL gds.alpha.kShortestPaths.stream({
  startNode: start,
  endNode: end,
  nodeProjection: "*",
  relationshipProjection: {
    all: {
      type: "*",
      properties: "distance",
      orientation:  "UNDIRECTED"
    }
  },
  relationshipWeightProperty: "distance",
  k: 5
})

YIELD index, sourceNodeId, targetNodeId, nodeIds, costs, path
RETURN index,
       [node in gds.util.asNodes(nodeIds[1..-1]) | node.id] AS via,
       reduce(acc=0.0, cost in costs | acc + cost) AS totalCost;

Nachdem wir die kürzesten Pfade zurückbekommen haben, suchen wir mit der Funktion gds.util.asNodes den zugehörigen Knoten für jede Knoten-ID und filtern dann die Start- und Endknoten aus der resultierenden Sammlung heraus. Außerdem berechnen wir die Gesamtkosten für jeden Pfad, indem wir die zurückgegebenen Kosten zusammenzählen.

Wenn du diese Prozedur ausführst, erhältst du das folgende Ergebnis:

index	über	totalCost
0	[Rotterdam, Hoek van Holland]	265.0
1	[Den Haag, Hoek van Holland]	266.0
2	[Rotterdam, Den Haag, Hoek van Holland]	285.0
3	[Den Haag, Rotterdam, Hoek van Holland]	298.0
4	[Utrecht, Amsterdam, Den Haag, Hoek van Holland]	374.0

Abbildung 4-7 zeigt den kürzesten Weg zwischen Gouda und Felixstowe.

Der kürzeste Weg in Abbildung 4-7 ist im Vergleich zu den nach Gesamtkosten geordneten Ergebnissen interessant. Er zeigt, dass du manchmal mehrere kürzeste Wege oder andere Parameter in Betracht ziehen solltest. In diesem Beispiel ist die zweitkürzeste Route nur 1 km länger als die kürzeste. Wenn wir die Landschaft bevorzugen, könnten wir die etwas längere Route wählen.

Alle Paare Kürzester Weg

Der Algorithmus All Pairs Shortest Path (APSP) berechnet den kürzesten (gewichteten) Pfad zwischen allen Knotenpaaren. Er ist effizienter als der Algorithmus Single Source Shortest Path, der für jedes Knotenpaar im Graphen ausgeführt wird.

APSP optimiert die Abläufe, indem es die bisher berechneten Entfernungen speichert und auf den Knoten parallel laufen lässt. Diese bekannten Entfernungen können dann bei der Berechnung des kürzesten Weges zu einem ungesehenen Knoten wiederverwendet werden. Du kannst dem Beispiel im nächsten Abschnitt folgen, um ein besseres Verständnis dafür zu bekommen, wie der Algorithmus funktioniert.

Hinweis

Einige Knotenpaare sind möglicherweise nicht voneinander erreichbar, was bedeutet, dass es keinen kürzesten Weg zwischen diesen Knoten gibt. Für diese Knotenpaare liefert der Algorithmus keine Entfernungsangaben.

Ein genauerer Blick auf den kürzesten Weg aller Paare

Die Berechnung des APSP ist am einfachsten zu verstehen, wenn du einer Abfolge von Vorgängen folgst. Das Diagramm in Abbildung 4-8 führt dich durch die Schritte für Knoten A.

Zu Beginn geht der Algorithmus von einem unendlichen Abstand zu allen Knoten aus. Wenn ein Startknoten ausgewählt wird, wird der Abstand zu diesem Knoten auf 0 gesetzt. Die Berechnung läuft dann wie folgt ab:

Vom Startknoten A aus bewerten wir die Kosten für die Bewegung zu den Knoten, die wir erreichen können, und aktualisieren diese Werte. Auf der Suche nach dem kleinsten Wert haben wir die Wahl zwischen B (Kosten von 3) und C (Kosten von 1). C wird für die nächste Phase der Durchquerung ausgewählt.
Vom Knoten C aus aktualisiert der Algorithmus nun die kumulierten Entfernungen von A zu den Knoten, die direkt von C aus erreicht werden können. Die Werte werden nur aktualisiert, wenn niedrigere Kosten gefunden wurden:
```
A=0, B=3, C=1, D=8, E=∞
```
Dann wird B als der nächstgelegene Knoten ausgewählt, der noch nicht besucht wurde. Er hat Beziehungen zu den Knoten A, D und E. Der Algorithmus berechnet die Entfernung zu diesen Knoten, indem er die Entfernung von A nach B mit der Entfernung von B zu jedem dieser Knoten addiert. Beachte, dass die niedrigsten Kosten vom Startknoten A zum aktuellen Knoten immer als versunkene Kosten erhalten bleiben. Die Berechnung der Entfernung (d) ergibt sich:
```
d(A,A) = d(A,B) + d(B,A) = 3 + 3 = 6
d(A,D) = d(A,B) + d(B,D) = 3 + 3 = 6
d(A,E) = d(A,B) + d(B,E) = 3 + 1 = 4
```
- In diesem Schritt ist die Entfernung von Knoten A nach B und zurück nach A, dargestellt als d(A,A) = 6, größer als die bereits berechnete kürzeste Entfernung (0), daher wird ihr Wert nicht aktualisiert.
- Die Entfernungen für die Knoten D (6) und E (4) sind geringer als die zuvor berechneten Entfernungen, also werden ihre Werte aktualisiert.
E wird als nächstes ausgewählt. Nur die kumulierte Summe für das Erreichen von D (5) ist jetzt niedriger und wird daher als einzige aktualisiert.
Wenn D schließlich ausgewertet wird, gibt es keine neuen minimalen Pfadgewichte; nichts wird aktualisiert und der Algorithmus wird beendet.

Tipp

Auch wenn der All Pairs Shortest Path Algorithmus so optimiert ist, dass er die Berechnungen für jeden Knoten parallel durchführt, kann sich das bei einem sehr großen Graphen summieren. Ziehe in Erwägung, einen Untergraphen zu verwenden, wenn du nur Pfade zwischen einer Unterkategorie von Knoten auswerten musst.

Wann sollte ich den kürzesten Weg für alle Paare verwenden?

All Pairs Shortest Path wird häufig verwendet, wenn die kürzeste Route blockiert oder suboptimal ist. Dieser Algorithmus wird zum Beispiel in der logischen Routenplanung verwendet, um die besten Mehrfachpfade für Diversity Routing zu gewährleisten. Verwende All Pairs Shortest Path, wenn du alle möglichen Routen zwischen allen oder den meisten deiner Knotenpunkte berücksichtigen musst.

Beispiele für Anwendungsfälle sind:

Optimierung des Standorts städtischer Einrichtungen und der Verteilung von Gütern. Ein Beispiel dafür ist die Bestimmung der zu erwartenden Verkehrsbelastung auf verschiedenen Abschnitten eines Verkehrsnetzes. Weitere Informationen findest du in dem Buch Urban Operations Research von R. C. Larson und A. R. Odoni (Prentice-Hall).
Die Suche nach einem Netzwerk mit maximaler Bandbreite und minimaler Latenz als Teil eines Algorithmus für das Design von Rechenzentren. Weitere Einzelheiten zu diesem Ansatz findest du in dem Papier "REWIRE: An Optimization-Based Framework for Data Center Network Design" von A. R. Curtis et al.

Alle Paare kürzester Weg mit Apache Spark

Die Funktion shortestPaths von Spark wurde entwickelt, um die kürzesten Pfade von allen Knoten zu einer Gruppe von Knoten, den Landmarken, zu finden. Wenn wir den kürzesten Pfad von jedem Ort nach Colchester, Immingham und Hoek van Holland finden wollten, würden wir die folgende Abfrage schreiben:

result = g.shortestPaths(["Colchester", "Immingham", "Hoek van Holland"])
result.sort(["id"]).select("id", "distances").show(truncate=False)

Wenn wir diesen Code in pyspark ausführen, sehen wir diese Ausgabe:

id	Entfernungen
Amsterdam	[Immingham → 1, Hoek van Holland → 2, Colchester → 4]
Colchester	[Colchester → 0, Hoek van Holland → 3, Immingham → 3]
Den Haag	[Hoek van Holland → 1, Immingham → 2, Colchester → 4]
Doncaster	[Immingham → 1, Colchester → 2, Hoek van Holland → 4]
Felixstowe	[Hoek van Holland → 1, Colchester → 2, Immingham → 4]
Gouda	[Hoek van Holland → 2, Immingham → 3, Colchester → 5]
Hoek van Holland	[Hoek van Holland → 0, Immingham → 3, Colchester → 3]
Immingham	[Immingham → 0, Colchester → 3, Hoek van Holland → 3]
Ipswich	[Colchester → 1, Hoek van Holland → 2, Immingham → 4]
London	[Colchester → 1, Immingham → 2, Hoek van Holland → 4]
Rotterdam	[Hoek van Holland → 1, Immingham → 3, Colchester → 4]
Utrecht	[Immingham → 2, Hoek van Holland → 3, Colchester → 5]

Die Zahl neben jedem Ort in der Spalte distances gibt die Anzahl der Beziehungen (Straßen) zwischen den Städten an, die wir überqueren müssen, um vom Quellknoten dorthin zu gelangen. In unserem Beispiel ist Colchester eine unserer Zielstädte und du kannst sehen, dass wir 0 Knoten überqueren müssen, um dorthin zu gelangen, aber 3 Sprünge von Immingham und Hoek van Holland machen müssen. Wenn wir eine Reise planen würden, könnten wir diese Informationen nutzen, um unsere Zeit an den gewählten Zielen zu optimieren.

Alle Paare Kürzester Weg mit Neo4j

Neo4j hat eine parallele Implementierung des All Pairs Shortest Path Algorithmus, der die Entfernung zwischen jedem Knotenpaar ermittelt.

Der All Pairs Shortest Path Algorithmus nimmt eine Konfigurationskarte mit den folgenden Schlüsseln auf:

nodeProjection: Ermöglicht die Abbildung bestimmter Arten von Knoten in den In-Memory-Graphen. Wir können eine oder mehrere Knotenbeschriftungen deklarieren.
relationshipProjection: Ermöglicht das Mapping von Beziehungstypen in den In-Memory-Graphen. Wir können einen oder mehrere Beziehungstypen zusammen mit der Richtung und den Eigenschaften deklarieren.
relationshipWeightProperty: Die Beziehungseigenschaft, die die Kosten für die Überquerung eines Knotenpunktpaares angibt. Die Kosten sind die Anzahl der Kilometer zwischen zwei Orten.

Wenn wir relationshipWeightProperty nicht einstellen, berechnet der Algorithmus die ungewichteten kürzesten Wege zwischen allen Knotenpaaren.

Die folgende Abfrage tut dies:

CALL gds.alpha.allShortestPaths.stream({
  nodeProjection: "*",
  relationshipProjection: {
    all: {
      type: "*",
      properties: "distance",
      orientation: "UNDIRECTED"
    }
  }
})
YIELD sourceNodeId, targetNodeId, distance
WHERE sourceNodeId < targetNodeId
RETURN gds.util.asNode(sourceNodeId).id AS source,
       gds.util.asNode(targetNodeId).id AS target,
       distance
ORDER BY distance DESC
LIMIT 10;

Dieser Algorithmus gibt den kürzesten Weg zwischen jedem Knotenpaar zweimal zurück - einmal mit jedem der Knoten als Ausgangsknoten. Das wäre hilfreich, wenn du einen gerichteten Graphen mit Einbahnstraßen auswerten würdest. Wir brauchen aber nicht jeden Weg zweimal zu sehen, also filtern wir die Ergebnisse mit dem Prädikat sourceNodeId < targetNodeId so, dass nur einer von ihnen erhalten bleibt.

Die Abfrage liefert die folgenden Ergebnisse:

Quelle	Ziel	Entfernung
Colchester	Utrecht	5.0
London	Rotterdam	5.0
London	Gouda	5.0
Ipswich	Utrecht	5.0
Colchester	Gouda	5.0
Colchester	Den Haag	4.0
London	Utrecht	4.0
London	Den Haag	4.0
Colchester	Amsterdam	4.0
Ipswich	Gouda	4.0

Diese Ausgabe zeigt die 10 Ortspaare, die die meisten Beziehungen zwischen ihnen haben, da wir nach Ergebnissen in absteigender Reihenfolge gefragt haben (DESC).

Wenn wir die kürzesten gewichteten Pfade berechnen wollen, sollten wir relationshipWeightProperty auf den Eigenschaftsnamen setzen, der die cost enthält, die bei der Berechnung des kürzesten Pfades verwendet werden soll. Diese Eigenschaft wird dann ausgewertet, um den kürzesten gewichteten Pfad zwischen jedem Knotenpaar zu ermitteln.

Die folgende Abfrage tut dies:

CALL gds.alpha.allShortestPaths.stream({
  nodeProjection: "*",
  relationshipProjection: {
    all: {
      type: "*",
      properties: "distance",
      orientation: "UNDIRECTED"
    }
  },
  relationshipWeightProperty: "distance"
})
YIELD sourceNodeId, targetNodeId, distance
WHERE sourceNodeId < targetNodeId
RETURN gds.util.asNode(sourceNodeId).id AS source,
       gds.util.asNode(targetNodeId).id AS target,
       distance
ORDER BY distance DESC
LIMIT 10;

Die Abfrage liefert das folgende Ergebnis:

Quelle	Ziel	Entfernung
Doncaster	Hoek van Holland	529.0
Rotterdam	Doncaster	528.0
Gouda	Doncaster	524.0
Felixstowe	Immingham	511.0
Den Haag	Doncaster	502.0
Ipswich	Immingham	489.0
Utrecht	Doncaster	489.0
London	Utrecht	460.0
Colchester	Immingham	457.0
Immingham	Hoek van Holland	455.0

Jetzt sehen wir die 10 Ortspaare, die am weitesten voneinander entfernt sind, gemessen an der Gesamtentfernung zwischen ihnen. Du siehst, dass Doncaster häufig auftaucht, ebenso wie mehrere Städte in den Niederlanden. Es sieht so aus, als ob es eine lange Fahrt wäre, wenn wir einen Roadtrip zwischen diesen Gebieten machen wollten .

Einzelne Quelle Kürzester Weg

Der Single Source Shortest Path (SSSP) Algorithmus, der etwa zur gleichen Zeit wie Dijkstras Shortest Path Algorithmus bekannt wurde, dient als Implementierung für beide Probleme.

Der SSSP-Algorithmus berechnet den kürzesten (gewichteten) Pfad von einem Wurzelknoten zu allen anderen Knoten im Graphen, wie in Abbildung 4-9 dargestellt.

Sie geht folgendermaßen vor:

Sie beginnt mit einem Wurzelknoten, von dem aus alle Pfade gemessen werden. In Abbildung 4-9 haben wir den Knoten A als Wurzel ausgewählt.
Die Beziehung mit dem kleinsten Gewicht, die von diesem Wurzelknoten ausgeht, wird ausgewählt und dem Baum hinzugefügt, zusammen mit dem mit ihr verbundenen Knoten. In diesem Fall ist das d(A,D)=1.
Die nächste Beziehung mit dem kleinsten kumulativen Gewicht von unserem Wurzelknoten zu einem beliebigen nicht besuchten Knoten wird ausgewählt und dem Baum auf die gleiche Weise hinzugefügt. In Abbildung 4-9 haben wir die Wahl zwischen d(A,B)=8, d(A,C)=5 direkt oder 4 über A-D-C, und d(A,E)=5. Wir entscheiden uns also für den Weg über A-D-C und fügen C zu unserem Baum hinzu.
Der Prozess wird so lange fortgesetzt, bis keine weiteren Knoten mehr hinzukommen und wir unseren kürzesten Pfad mit einer Quelle haben.

Wann sollte ich den kürzesten Weg mit einer einzigen Quelle verwenden?

Verwende Single Source Shortest Path, wenn du die optimale Route von einem festen Startpunkt zu allen anderen einzelnen Knoten ermitteln musst. Da die Route auf der Grundlage des Gesamtpfadgewichts von der Wurzel aus gewählt wird, ist sie nützlich, um den besten Pfad zu jedem Knoten zu finden, aber nicht unbedingt, wenn alle Knoten in einer einzigen Reise besucht werden müssen.

SSSP ist zum Beispiel hilfreich, um die Hauptrouten für Rettungsdienste zu ermitteln, bei denen du nicht jeden Ort bei jedem Vorfall besuchst, aber nicht, um eine einzige Route für die Speicherbereinigung zu finden, bei der du jedes Haus in einer Fahrt besuchen musst. (Im letzteren Fall würdest du den Minimum Spanning Tree Algorithmus verwenden, der später behandelt wird).

Beispiele für Anwendungsfälle sind:

Erkennen von Änderungen in der Topologie, wie z. B. Verbindungsausfälle, und Vorschlagen einer neuen Routingstruktur in Sekundenschnelle
Verwendung von Dijkstra als IP-Routing-Protokoll für den Einsatz in autonomen Systemen wie einem lokalen Netzwerk (LAN)

Single Source Shortest Path mit Apache Spark

Wir können die Funktion shortest_path, die wir geschrieben haben, um den kürzesten Weg zwischen zwei Orten zu berechnen, so anpassen, dass sie uns stattdessen den kürzesten Weg von einem Ort zu allen anderen liefert. Beachte, dass wir wieder das aggregateMessages Framework von Spark verwenden, um unsere Funktion anzupassen.

Zunächst importieren wir die gleichen Bibliotheken wie zuvor:

from graphframes.lib import AggregateMessages as AM
from pyspark.sql import functions as F

Und wir werden die gleiche benutzerdefinierte Funktion verwenden, um Pfade zu konstruieren:

add_path_udf = F.udf(lambda path, id: path + [id], ArrayType(StringType()))

Nun zur Hauptfunktion, die den kürzesten Weg ausgehend von einem Ursprung berechnet:

def sssp(g, origin, column_name="cost"):
    vertices = g.vertices \
        .withColumn("visited", F.lit(False)) \
        .withColumn("distance",
            F.when(g.vertices["id"] == origin, 0).otherwise(float("inf"))) \
        .withColumn("path", F.array())
    cached_vertices = AM.getCachedDataFrame(vertices)
    g2 = GraphFrame(cached_vertices, g.edges)

    while g2.vertices.filter('visited == False').first():
        current_node_id = g2.vertices.filter('visited == False')
                            .sort("distance").first().id

        msg_distance = AM.edge[column_name] + AM.src['distance']
        msg_path = add_path_udf(AM.src["path"], AM.src["id"])
        msg_for_dst = F.when(AM.src['id'] == current_node_id,
                      F.struct(msg_distance, msg_path))
        new_distances = g2.aggregateMessages(
            F.min(AM.msg).alias("aggMess"), sendToDst=msg_for_dst)

        new_visited_col = F.when(
            g2.vertices.visited | (g2.vertices.id == current_node_id),
                                  True).otherwise(False)
        new_distance_col = F.when(new_distances["aggMess"].isNotNull() &
                                  (new_distances.aggMess["col1"] <
                                  g2.vertices.distance),
                                  new_distances.aggMess["col1"]) \
                                  .otherwise(g2.vertices.distance)
        new_path_col = F.when(new_distances["aggMess"].isNotNull() &
                              (new_distances.aggMess["col1"] <
                              g2.vertices.distance),
                              new_distances.aggMess["col2"]
                              .cast("array<string>")) \
                              .otherwise(g2.vertices.path)

        new_vertices = g2.vertices.join(new_distances, on="id",
                                        how="left_outer") \
            .drop(new_distances["id"]) \
            .withColumn("visited", new_visited_col) \
            .withColumn("newDistance", new_distance_col) \
            .withColumn("newPath", new_path_col) \
            .drop("aggMess", "distance", "path") \
            .withColumnRenamed('newDistance', 'distance') \
            .withColumnRenamed('newPath', 'path')
        cached_new_vertices = AM.getCachedDataFrame(new_vertices)
        g2 = GraphFrame(cached_new_vertices, g2.edges)

    return g2.vertices \
                .withColumn("newPath", add_path_udf("path", "id")) \
                .drop("visited", "path") \
                .withColumnRenamed("newPath", "path")

Wenn wir den kürzesten Weg von Amsterdam zu allen anderen Orten finden wollen, können wir die Funktion wie folgt aufrufen:

via_udf = F.udf(lambda path: path[1:-1], ArrayType(StringType()))

result = sssp(g, "Amsterdam", "cost")
(result
 .withColumn("via", via_udf("path"))
 .select("id", "distance", "via")
 .sort("distance")
 .show(truncate=False))

Wir definieren eine weitere benutzerdefinierte Funktion, um die Start- und Endknoten aus dem resultierenden Pfad herauszufiltern. Wenn wir diesen Code ausführen, erhalten wir die folgende Ausgabe:

id	Entfernung	über
Amsterdam	0.0	[]
Utrecht	46.0	[]
Den Haag	59.0	[]
Gouda	81.0	[Utrecht]
Rotterdam	85.0	[Den Haag]
Hoek van Holland	86.0	[Den Haag]
Felixstowe	293.0	[Den Haag, Hoek van Holland]
Ipswich	315.0	[Den Haag, Hoek van Holland, Felixstowe]
Colchester	347.0	[Den Haag, Hoek van Holland, Felixstowe, Ipswich]
Immingham	369.0	[]
Doncaster	443.0	[Immingham]
London	453.0	[Den Haag, Hoek van Holland, Felixstowe, Ipswich, Colchester]

In diesen Ergebnissen sehen wir die physischen Entfernungen in Kilometern vom Wurzelknoten, Amsterdam, zu allen anderen Städten im Graphen, geordnet nach der kürzesten Entfernung.

Kürzester Weg mit einer Quelle mit Neo4j

Neo4j implementiert eine Variante von SSSP, den sogenannten Delta-Stepping-Algorithmus, der Dijkstras Algorithmus in mehrere Phasen unterteilt, die parallel ausgeführt werden können.

Der Single Source Shortest Path Algorithmus nimmt eine Konfigurationskarte mit den folgenden Schlüsseln auf:

startNode: Der Knoten, an dem unsere Suche nach dem kürzesten Weg beginnt.
nodeProjection: Ermöglicht die Zuordnung bestimmter Arten von Knoten zum In-Memory-Graphen. Wir können eine oder mehrere Knotenbeschriftungen deklarieren.
relationshipProjection: Ermöglicht das Mapping von Beziehungstypen in den In-Memory-Graphen. Wir können einen oder mehrere Beziehungstypen zusammen mit der Richtung und den Eigenschaften deklarieren.
relationshipWeightProperty: Die Beziehungseigenschaft, die die Kosten für die Überquerung zwischen zwei Knoten angibt. Die Kosten sind die Anzahl der Kilometer zwischen zwei Orten.
delta: Der Grad der Gleichzeitigkeit, der verwendet werden soll

Die folgende Abfrage führt den Delta-Stepping-Algorithmus aus:

MATCH (n:Place {id:"London"})
CALL gds.alpha.shortestPath.deltaStepping.stream({
  startNode: n,
  nodeProjection: "*",
  relationshipProjection: {
    all: {
      type: "*",
      properties: "distance",
      orientation:  "UNDIRECTED"
    }
  },
  relationshipWeightProperty: "distance",
  delta: 1.0
})
YIELD nodeId, distance
WHERE gds.util.isFinite(distance)
RETURN gds.util.asNode(nodeId).id AS destination, distance
ORDER BY distance;

Die Abfrage liefert die folgende Ausgabe:

Ziel	Entfernung
London	0.0
Colchester	106.0
Ipswich	138.0
Felixstowe	160.0
Doncaster	277.0
Immingham	351.0
Hoek van Holland	367.0
Den Haag	394.0
Rotterdam	400.0
Gouda	425.0
Amsterdam	453.0
Utrecht	460.0

In diesen Ergebnissen sehen wir die physischen Entfernungen in Kilometern vom Wurzelknoten, London, zu allen anderen Städten im Graphen, geordnet nach der kürzesten Entfernung.

Minimum Spanning Tree

Der Minimum (Weight) Spanning Tree Algorithmus geht von einem bestimmten Knoten aus und findet alle erreichbaren Knoten und die Menge der Beziehungen, die die Knoten mit dem geringstmöglichen Gewicht miteinander verbinden. Er geht von jedem besuchten Knoten zum nächsten unbesuchten Knoten mit dem geringsten Gewicht, um Zyklen zu vermeiden.

Der erste bekannte Minimum Weight Spanning Tree Algorithmus wurde 1926 von dem tschechischen Wissenschaftler Otakar Borůvka entwickelt.Prim's Algorithmus, der 1957 erfunden wurde, ist der einfachste und bekannteste.

Der Algorithmus von Prim ähnelt dem Dijkstra-Algorithmus für den kürzesten Weg, aber anstatt die Gesamtlänge eines Pfades zu minimieren, der an jeder Beziehung endet, minimiert er die Länge jeder einzelnen Beziehung. Im Gegensatz zu Dijkstras Algorithmus toleriert er Beziehungen mit negativem Gewicht.

Der Minimum Spanning Tree Algorithmus funktioniert wie in Abbildung 4-10 dargestellt.

Die Schritte sind wie folgt:

Sie beginnt mit einem Baum, der nur einen Knoten enthält. In Abbildung 4-10 beginnen wir mit dem Knoten A.
Die Beziehung mit dem kleinsten Gewicht, die von diesem Knoten ausgeht, wird ausgewählt und dem Baum hinzugefügt (zusammen mit dem mit ihr verbundenen Knoten). In diesem Fall: A-D.
Dieser Vorgang wird wiederholt, wobei immer die Beziehung mit dem geringsten Gewicht gewählt wird, die einen Knoten verbindet, der noch nicht im Baum vorhanden ist. Wenn du unser Beispiel hier mit dem SSSP-Beispiel in Abbildung 4-9 vergleichst, wirst du feststellen, dass sich die Pfade im vierten Diagramm unterscheiden. Das liegt daran, dass SSSP den kürzesten Weg anhand der kumulierten Summen von der Wurzel aus bewertet, während der Minimum Spanning Tree nur die Kosten des nächsten Schritts berücksichtigt.
Wenn es keine weiteren Knoten mehr gibt, ist der Baum ein Minimum Spanning Tree.

Es gibt auch Varianten dieses Algorithmus, die den maximal gewichteten Spannbaum (Baum mit den höchsten Kosten) und den k-spannenden Baum (Baumgröße begrenzt) finden.

Wann sollte ich den minimalen Spanning Tree verwenden?

Verwende den Minimum Spanning Tree, wenn du die beste Route brauchst, um alle Knoten zu besuchen. Da die Route auf der Grundlage der Kosten jedes nächsten Schritts gewählt wird, ist er nützlich, wenn du alle Knoten in einem einzigen Durchgang besuchen musst. (Lies den vorherigen Abschnitt über "Single Source Shortest Path" (Kürzester Weg mit einer Quelle), wenn du keinen Weg für eine einzelne Reise brauchst).

Du kannst diesen Algorithmus zur Optimierung von Pfaden für zusammenhängende Systeme wie Wasserleitungen und Schaltkreise verwenden. Er wird auch eingesetzt, um einige Probleme mit unbekannten Rechenzeiten zu approximieren, z. B. das Traveling Salesman Problem und bestimmte Arten von Rundungsproblemen. Auch wenn er nicht immer die absolut optimale Lösung findet, macht dieser Algorithmus potenziell komplizierte und rechenintensive Analysen viel zugänglicher.

Beispiele für Anwendungsfälle sind:

Minimierung der Reisekosten für die Erkundung eines Landes."An Application of Minimum Spanning Trees to Travel Planning" beschreibt, wie der Algorithmus zu diesem Zweck Flug- und Schiffsverbindungen analysiert.
Visualisierung von Korrelationen zwischen Währungsrenditen. Dies wird in "Minimum Spanning Tree Application in the Currency Market" beschrieben .
Rückverfolgung des Verlaufs der Infektionsübertragung bei einem Ausbruch. Weitere Informationen findest du unter "Verwendung des Minimum Spanning Tree Model für die molekulare epidemiologische Untersuchung eines nosokomialen Ausbruchs einer Hepatitis-C-Virusinfektion".

Warnung

Der Minimum Spanning Tree Algorithmus liefert nur dann aussagekräftige Ergebnisse, wenn er auf einen Graphen angewendet wird, in dem die Beziehungen unterschiedliche Gewichte haben. Wenn der Graph keine Gewichte hat oder alle Beziehungen das gleiche Gewicht haben, ist jeder Spannbaum ein Minimum Spanning Tree.

Minimaler Spanning Tree mit Neo4j

Sehen wir uns den Minimum Spanning Tree Algorithmus in Aktion an. Der Minimum Spanning Tree Algorithmus nimmt eine Konfigurationskarte mit den folgenden Schlüsseln auf:

startNodeId: Die ID des Knotens, an dem unsere Suche nach dem kürzesten Weg beginnt.
nodeProjection: Ermöglicht die Abbildung bestimmter Arten von Knoten in den In-Memory-Graphen. Wir können eine oder mehrere Knotenbeschriftungen deklarieren.
relationshipProjection: Ermöglicht das Mapping von Beziehungstypen in den In-Memory-Graphen. Wir können einen oder mehrere Beziehungstypen zusammen mit der Richtung und den Eigenschaften deklarieren.
relationshipWeightProperty: Die Beziehungseigenschaft, die die Kosten für die Überquerung zwischen zwei Knoten angibt. Die Kosten sind die Anzahl der Kilometer zwischen zwei Orten.
writeProperty: Der Name des Beziehungstyps, der als Ergebnis zurückgeschrieben wird
weightWriteProperty: Der Name der Gewichtseigenschaft auf dem zurückgeschriebenen Beziehungstyp writeProperty

Die folgende Abfrage findet einen Spanning Tree, der in Amsterdam beginnt:

MATCH (n:Place {id:"Amsterdam"})
CALL gds.alpha.spanningTree.minimum.write({
  startNodeId: id(n),
  nodeProjection: "*",
  relationshipProjection: {
    EROAD: {
      type: "EROAD",
      properties: "distance",
      orientation:  "UNDIRECTED"
    }
  },
  relationshipWeightProperty: "distance",
  writeProperty: 'MINST',
  weightWriteProperty: 'cost'
})
YIELD createMillis, computeMillis, writeMillis, effectiveNodeCount
RETURN createMillis, computeMillis, writeMillis, effectiveNodeCount;

Die Parameter, die an diesen Algorithmus übergeben werden, sind:

Place: Die Knotenbeschriftungen, die bei der Berechnung des Spanning Tree berücksichtigt werden
EROAD: Die Beziehungstypen, die bei der Berechnung des Spanning Tree zu berücksichtigen sind
distance: Der Name der Beziehungseigenschaft, die die Kosten für die Überquerung zwischen einem Knotenpaar angibt
id(n): Die interne Knotennummer des Knotens, an dem der Spanning Tree beginnen soll

Diese Abfrage speichert ihre Ergebnisse im Graphen. Wenn wir den Spannbaum mit dem geringsten Gewicht zurückgeben wollen, können wir die folgende Abfrage ausführen:

MATCH path = (n:Place {id:"Amsterdam"})-[:MINST*]-()
WITH relationships(path) AS rels
UNWIND rels AS rel
WITH DISTINCT rel AS rel
RETURN startNode(rel).id AS source,
       endNode(rel).id AS destination,
       rel.cost AS cost;

Und das ist die Ausgabe der Abfrage:

Quelle	Ziel	Kosten
Amsterdam	Utrecht	46.0
Utrecht	Gouda	35.0
Gouda	Rotterdam	25.0
Rotterdam	Den Haag	26.0
Den Haag	Hoek van Holland	27.0
Hoek van Holland	Felixstowe	207.0
Felixstowe	Ipswich	22.0
Ipswich	Colchester	32.0
Colchester	London	106.0
London	Doncaster	277.0
Doncaster	Immingham	74.0

Wenn wir in Amsterdam wären und jeden anderen Ort in unserem Datensatz während der gleichen Reise besuchen wollten, zeigt Abbildung 4-11 die kürzeste durchgehende Route, um dies zu erreichen.

Random Walk

Der Random Walk Algorithmus liefert eine Reihe von Knoten auf einem zufälligen Pfad in einem Graphen.Der Begriff wurde erstmals 1905 von Karl Pearson in einem Brief an die Zeitschrift Nature mit dem Titel "The Problem of the Random Walk" erwähnt . Obwohl das Konzept noch weiter zurückreicht, werden Random Walks erst seit kurzem in der Netzwerkwissenschaft eingesetzt.

Ein Spaziergang nach dem Zufallsprinzip wird manchmal so beschrieben, als würde eine betrunkene Person durch eine Stadt laufen. Sie weiß, in welche Richtung oder zu welchem Ziel sie will, nimmt aber vielleicht einen sehr umständlichen Weg, um dorthin zu gelangen.

Der Algorithmus beginnt an einem Knoten und folgt eher zufällig einer der Beziehungen vorwärts oder rückwärts zu einem Nachbarknoten. Dann macht er dasselbe von diesem Knoten aus und so weiter, bis er die festgelegte Pfadlänge erreicht hat. (Wir sagen eher zufällig, weil die Anzahl der Beziehungen, die ein Knoten und seine Nachbarn haben, die Wahrscheinlichkeit beeinflusst, dass ein Knoten durchlaufen wird).

Wann sollte ich Random Walk verwenden?

Verwende den Random Walk Algorithmus als Teil anderer Algorithmen oder Datenpipelines, wenn du eine größtenteils zufällige Menge verbundener Knotenpunkte erzeugen musst.

Beispiele für Anwendungsfälle sind:

Als Teil der Algorithmen node2vec und graph2vec, die Knoteneinbettungen erstellen. Diese Knoteneinbettungen können dann als Eingabe für ein neuronales Netz verwendet werden.
Als Teil der Walktrap- und Infomap-Community-Erkennung: Wenn ein Random Walk wiederholt eine kleine Gruppe von Knoten zurückbringt, deutet das darauf hin, dass diese Knotengruppe eine Community-Struktur haben könnte.
Dies wird im Artikel "Review Prediction with Neo4j and TensorFlow" von David Mack näher beschrieben, der sich mit dem Training von Machine Learning-Modellen beschäftigt .

Weitere Anwendungsbeispiele findest du in einem Artikel von N. Masuda, M. A. Porter und R. Lambiotte, "Random Walks and Diffusion on Networks".

Random Walk mit Neo4j

Neo4j hat den Random Walk Algorithmus implementiert und unterstützt zwei Modi für die Auswahl der nächsten Beziehung, die in jeder Phase des Algorithmus verfolgt wird:

random: Wählt zufällig eine Beziehung aus, der du folgen kannst
node2vec: Wählt die Beziehung aus, der er folgt, indem er eine Wahrscheinlichkeitsverteilung der vorherigen Nachbarn berechnet

Das Random Walk Verfahren nimmt eine Konfigurationskarte mit den folgenden Schlüsseln auf:

start: Die ID des Knotens, an dem unsere Suche nach dem kürzesten Weg beginnt.
nodeProjection: Ermöglicht die Abbildung bestimmter Arten von Knoten in den In-Memory-Graphen. Wir können eine oder mehrere Knotenbeschriftungen deklarieren.
relationshipProjection: Ermöglicht das Mapping von Beziehungstypen in den In-Memory-Graphen. Wir können einen oder mehrere Beziehungstypen zusammen mit der Richtung und den Eigenschaften deklarieren.
walks: Die Anzahl der zurückgegebenen Pfade ``

Im Folgenden wird ein zufälliger Spaziergang ausgehend von London durchgeführt:

MATCH (source:Place {id: "London"})
CALL gds.alpha.randomWalk.stream({
  start: id(source),
  nodeProjection: "*",
  relationshipProjection: {
    all: {
      type: "*",
      properties: "distance",
      orientation:  "UNDIRECTED"
    }
  },
  steps: 5,
  walks: 1
})
YIELD nodeIds
UNWIND gds.util.asNodes(nodeIds) as place
RETURN place.id AS place

Sie liefert das folgende Ergebnis:

Platz
London
Doncaster
Immingham
Amsterdam
Utrecht
Amsterdam

In jeder Phase des Random Walk wird die nächste Beziehung zufällig ausgewählt. Das bedeutet, dass wir bei einem erneuten Durchlauf des Algorithmus, selbst mit denselben Parametern, wahrscheinlich nicht dasselbe Ergebnis erhalten. Es ist auch möglich, dass ein Walk auf sich selbst zurückfällt, wie wir in Abbildung 4-12 sehen können, wo wir von Amsterdam nach Den Haag und zurück gehen.

Zusammenfassung

Pfadfindungsalgorithmen sind nützlich, um zu verstehen, wie unsere Daten miteinander verbunden sind. In diesem Kapitel haben wir mit den grundlegenden Breadth- und Depth-First-Algorithmen begonnen, bevor wir zu Dijkstra und anderen Algorithmen für kürzeste Pfade übergegangen sind. Wir haben uns auch Varianten der Algorithmen für kürzeste Pfade angesehen, die dafür optimiert sind, den kürzesten Pfad von einem Knoten zu allen anderen Knoten oder zwischen allen Knotenpaaren in einem Graphen zu finden. Zum Schluss haben wir uns mit dem Random Walk Algorithmus beschäftigt, mit dem man beliebige Mengen von Pfaden finden kann.

Als Nächstes lernen wir die Zentralitätsalgorithmen kennen, mit denen man einflussreiche Knoten in einem Graphen finden kann.

Get Graph-Algorithmen now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Kapitel 4. Pfadfindungs- und Graphensuchalgorithmen

Abbildung 4-1. Pfadfindungs- und Suchalgorithmen

Beispieldaten: Das Transportdiagramm

Abbildung 4-2. Das Transportdiagramm

Importieren der Daten in Apache Spark

Importieren der Daten in Neo4j

Breitensuche zuerst

Abbildung 4-3. Breadth First Search ausgehend von Den Haag. Die Knotennummern geben die Reihenfolge an, in der sie durchlaufen werden.

Breadth First Search mit Apache Spark

Suche in der Tiefe

Abbildung 4-4. Die Suche in der Tiefe beginnt in Den Haag. Die Knotennummern geben die Reihenfolge an, in der sie durchlaufen werden.

Kürzester Weg

Hinweis

Wann sollte ich den kürzesten Weg verwenden?

Tipp

Kürzester Weg mit Neo4j

Hinweis

Abbildung 4-6. Der ungewichtete kürzeste Weg zwischen Amsterdam und London

Kürzester Weg (gewichtet) mit Neo4j

Kürzester Weg (gewichtet) mit Apache Spark

Tipp

Warnung

Variation des kürzesten Weges: A*

Warnung

Hinweis

A* mit Neo4j

Variation der kürzesten Wege: Yen's k-Kürzeste Pfade

Yen ist mit Neo4j

Abbildung 4-7. Der kürzeste Weg zwischen Gouda und Felixstowe

Alle Paare Kürzester Weg

Hinweis

Ein genauerer Blick auf den kürzesten Weg aller Paare

Abbildung 4-8. Die Schritte zur Berechnung des kürzesten Weges von Knoten A zu allen anderen Knoten, mit schattierten Aktualisierungen.

Tipp

Wann sollte ich den kürzesten Weg für alle Paare verwenden?

Alle Paare kürzester Weg mit Apache Spark

Alle Paare Kürzester Weg mit Neo4j

Einzelne Quelle Kürzester Weg

Abbildung 4-9. Die Schritte des Single Source Shortest Path Algorithmus

Wann sollte ich den kürzesten Weg mit einer einzigen Quelle verwenden?

Single Source Shortest Path mit Apache Spark

Kürzester Weg mit einer Quelle mit Neo4j

Minimum Spanning Tree

Abbildung 4-10. Die Schritte des Minimum Spanning Tree Algorithmus

Wann sollte ich den minimalen Spanning Tree verwenden?

Warnung

Minimaler Spanning Tree mit Neo4j

Abbildung 4-11. Ein spannender Baum mit minimalem Gewicht aus Amsterdam

Random Walk

Wann sollte ich Random Walk verwenden?

Random Walk mit Neo4j

Abbildung 4-12. Ein zufälliger Spaziergang ausgehend von London

Zusammenfassung

Don’t leave empty-handed

It’s yours, free.

Check it out now on O’Reilly