5 wichtige Graph-Algorithmen im Überblick

Anbieter zum Thema

Parasoft® Deutschland GmbH

Neo4j c/o Workrepublic

Graph-Algorithmen bilden in Graphdatenbanken die Grundlage für die Analyse realer Netzwerke. Ihre Anwendungsgebiete reichen von der Betrugsaufdeckung bis hin zur Planung städtischer Infrastrukturen. Hier ist eine Übersicht der technischen Voraussetzungen sowie der fünf bekannten Basis-Algorithmen.

Um einen umfassenden Einblick in die Beziehungen zwischen bestimmten Datenpunkten zu erhalten sowie Muster zu erkennen, benötigen Data Scientists zweierlei: Eine Echtzeit-Visualisierung der vielfältigen Beziehungen zwischen Datenpunkten sowie globale Algorithmen, die darin enthaltene Muster und Zusammenhänge aufdecken.

Beides ist nur möglich, wenn die zugrundeliegende Datenbanktechnologie eine entsprechend hohe Performance aufweist und der Rechenaufwand gering bleibt.

Framework für Data Scientists

Nicht alle Datenbank-Managementsysteme (DBMS) können diese Anforderungen erfüllen. Relationale Datenbanken beispielsweise eignen sich nur bedingt für die Echtzeitsuche in mehrschichtigen, komplexen Daten. Je mehr Joins (Datenbank-Verbünde) nötig sind, desto höher der Aufwand und desto langsamer die Abfrage.

Um Graph-Workloads unterstützen zu können, wird in vielen Fällen auch eine Graph-API auf ein vorhandenes Datenbanksystem aufgesetzt. Im Vergleich zu nativen Graph-Technologien schneiden diese Hybridlösungen jedoch bei der Datenintegrität, Performance, Effizienz und Skalierbarkeit tendenziell schlechter ab.

Graph-Analytik ist dann sinnvoll, wenn sie richtig genutzt wird und Erkenntnisse in Echtzeit liefern kann. Daher sind die besten Graph-Algorithmen einfach in der Anwendung, schnell in der Ausführung und liefern zuverlässige Ergebnisse. Lösungen, die native Graphdatenbanken mit skalierbaren Graph-Algorithmen und anschaulicher Visualisierung innerhalb einer Plattform verknüpfen, ermöglichen einen direkten und unkomplizierten Einstieg in die Graph-Analytik.

Die Graph Data Science Library von Neo4j beispielsweise bietet eine ganze Reihe an skalierbaren Graph-Algorithmen, die Anwender für ihre Analysen heranziehen können. So entdecken sie auch Datenbeziehungen und -strukturen, die bei normalen Abfragen weitgehend ungenutzt bzw. unentdeckt geblieben waren. Richtig eingesetzt helfen die Algorithmen, die Vorhersagegenauigkeit von Machine Learning-Modellen zu optimieren und offene Fragen der Datenanalytik zu beantworten.

Top 5 Graph-Algorithmen

Je nach Suchanfrage und Aufgabe lassen sich Graph-Algorithmen in unterschiedliche Kategorien zusammenfassen: Pathfinding, Centrality, Community Detection, Link Prediction und Similiarity. Während Pathfinding- (und Traversal-)Algorithmen den kürzesten Weg in einem Graphen ermitteln, bestimmen Centrality-Algorithmen den Einfluss einzelner Knoten in einem Netzwerk. Community Detection-Algorithmen wiederum bewerten, wie ein Graphen in Gruppen/Cluster aufgeteilt sind.

Die folgenden fünf Graph-Algorithmen stellen nur einen kleiner Ausschnitt der Möglichkeiten dar, erklären aber beispielhaft grundlegende Abfragen und Anwendungsgebiete:

1. PageRank

Der „PageRank“-Algorithmus misst die Wichtigkeit jedes Knotens innerhalb eines Graphen basierend auf der Anzahl der transitiven Beziehungen sowie der Wichtigkeit der verbundenen Knoten. Je mehr Beziehungen direkt und indirekt auf einen Knoten verweisen, desto höher ist das Gewicht dieses Knoten. Und je höher das Gewicht der verweisenden Beziehungen und Knoten, desto größer ist der Effekt.

PageRank (von Larry Page) wurde vor allem durch Google bekannt, um Suchergebnisse anhand ihrer akkumulierten Wichtigkeit zu sortieren. Sprich, eine Seite ist nur so wichtig wie der PageRank der Seiten, die auf sie verweisen. PageRank wird für unterschiedliche Zwecke genutzt – von Folge-Vorschlägen auf Twitter über allgemeine Sentiment Analysen und Sprachanalyse bis hin zur Identifizierung relevanter Merkmale für die Datenerfassung bei Machine Learning-Verfahren.

In der Biologie wird der Algorithmus beispielsweise dafür eingesetzt, um Kettenreaktion innerhalb eines ökologischen Systems vorherzusagen (Stichwort: Artensterben). Wie in der obigen Abbildung zu sehen, erscheinen die Knoten mit einem hohen PageRank Score in der Ansicht größer und fallen sofort ins Auge. So lassen sich Analysen und Untersuchungen auf bestimmte Objekte priorisieren.

2. Shortest Path

Der Algorithmus „Shortest Path“ berechnet den kürzesten Pfad zwischen einem Knoten und allen anderen Knoten. Dieser Algorithmus wurde ursprünglich vom niederländischen Informatiker Edsger Dijkstra in den frühen 1950er Jahren entwickelt und ist heute auch als Dijkstra-Algorithmus bekannt. Variationen des Dijkstra-Algorithmus (A*) werden zum Beispiel in Google Maps genutzt, um die kürzeste Route zwischen verschiedenen Städten zu ermitteln. Dabei sind die Städte die Knoten des Graphen und die Straßen die Kanten.

Wie das in der Praxis funktioniert lässt sich anhand der vorangestellten Abbildung erklären: Wie komme ich auf den schnellsten Weg von München nach Köln? Im Graphen ist die Stadt München als Startpunkt A und Köln als Zielort F dargestellt. Die Kanten bilden das Straßennetz ab und geben die Distanz zwischen verschiedenen Städten bzw. Drehkreuzen an. Im Beispiel verläuft der kürzeste Weg von A nach F über die Knoten C, D und E. Die Kantenbewertungen können aber auch etwas anderes darstellen, wie Mautkosten oder die Unterscheidung in Autobahn oder Landstraße. Hier wird statt dem kürzesten der kosteneffektivste oder der schnellste Weg bestimmt.

3. Betweenness Centrality

Der Algorithmus „Betweenness Centrality“ stützt sich auf „Shortest Path“ und misst die Anzahl der aller kürzesten Wege in Graphen, die durch einen Knoten verlaufen. Knoten, die am häufigsten auf kürzesten Wegen liegen, haben einen höheren „Centrality“-Wert und bilden eine Brücken zwischen verschiedenen Clustern. Sie haben somit einen höheren Einfluss auf den Informationsfluss in einem Graphen.

Wie das funktioniert, erkennt man in der Abbildung oben: „Alice“ bildet hier den wesentlichen Knoten im Graphen. Wird Alice entfernt, sind alle Verbindungen im Graphen abgeschnitten und isoliert. Das macht Alice zu einer zentralen Person, da sie als Brücke zu den anderen Personen dient.

„Betweenness Centrality“ wird in unterschiedlichen Bereichen verwendet, vor allem bei Netzwerkanalysen und beim Identifizieren von Flaschenhälsen in diversen Prozessen und Verteilungsnetzen. In der Logistik lässt sich so beispielsweises erkennen, wenn verschiedene Hersteller denselben Zulieferer oder Spediteur für eine Ware nutzen und wo es bei einem plötzlichen Ausfall schnell zu Lieferengpässen kommen kann. Ein weiterer Anwendungsfall ist die Betrugsaufdeckung. Hier wird der Algorithmus zur Identifizierung von einflussreichen Kriminellen in einem Betrügerring genutzt.

4. Weakly Connected Components

Der Algorithmus „Weakly Connected Components“ (Union Find) ermittelt Gruppen von verbundenen Knoten in einem ungerichteten Graphen, wobei jeder Knoten von einem beliebig anderen Knoten in der gleichen Gruppe erreichbar ist. Im Gegensatz zu „Strongly Connected Components (SCC)“, benötigt der Algorithmus zwischen zwei Knotenpaaren nur einen Pfad in eine Richtung, während in SCC ein Pfad in beide Richtungen nötig ist. Wie bei SCC wird Union Find oft zu Beginn einer Analyse eingesetzt, um ein Verständnis der Graphstruktur zu gewinnen, da beide Algorithmen sehr effizient und schnell zu Ergebnissen führen.

Die Überprüfung, ob ein Graph auch tatsächlich verbunden ist, gehört zu den wichtigsten Vorverarbeitungsschritten in der Graph-Analytik. Ein schneller Test zu Beginn stellt sicher, dass darauf folgende Abfragen korrekt verlaufen und tatsächlich alle Teile des Graphen mit einschließen. Schwer auffindbare Fehler lassen sich so oft darauf zurückführen, dass Algorithmen nur auf einen isolierten Teilbereich des Graphen ausgeführt wurden. Die obige Abbildung zeigt zwei solche „Inseln“ von verbundenen Knoten innerhalb eines Graphen, zwischen denen keine Verbindung besteht.

5. Minimum Weight Spanning Tree (MWST)

Der „Minimum Weight Spanning Tree“-Algorithmus berechnet die Pfade entlang einer Graphstruktur, bei der mehrere Knotenpunkte mit dem kleinsten Wert (Attribute der Kanten, wie Kosten, Zeit oder Kapazität) miteinander verbunden werden. MWST wird häufig bei der Modellierung zusammenhängender Netzwerke verwendet, zum Beispiel in der Telekommunikation oder der Routenführung (Kabelverlegung, Transport etc.).

Ein gutes Beispiel ist das Verlegen von Wasserleitungen oder Glasfaserkabeln in Städten. Hier ist das Ziel, alle Häuser (Knoten) mit möglichst wenig Aufwand, sprich einem Minimum an Rohren oder Kabeln, miteinander zu verbinden. In der letzten Abbildung sind die Häuser jeweils als Knotenpunkte A bis E abgebildet. Um den „Minimum Weight Spanning Tree“ zu ermitteln, startet der Algorithmus vom Knoten D aus und findet den kosteneffektivsten Weg, die Leitungen über alle nötigen Knotenpunkte hinweg zu verlegen. Dank dieser Berechnung erübrigt sich der kostspielige Anschluss von D nach E und von B nach C.

* Michael Hunger arbeitet bei Neo4j seit 2010 in den verschiedensten Funktionen an der Weiterentwicklung der Graphdatenbank mit. Als erster Ansprechpartner für die Neo4j Community unterstützt er Anwender bei der Realisierung graphbasierter Anwendungen aller Art. Als Entwickler beteiligt er sich an ambitionierten Open-Source-Projekten und schreibt in Büchern, Blogs und Fachartikeln über Software. Michael organisiert und betreut darüber hinaus die Neo4j-Entwicklerkonferenz NODES 2020 am 20. Oktober. Auf der Online-Veranstaltung sprechen 63 Referenten aus über 15 Ländern zu Themen rund um Graphtechnologie – von Spatial und GraphQL/GRANDstack bis zu Software-Analytik und Applikationen.

Dieser Beitrag erschien zuerst auf unserem Partnerportal Dev-Insider.de.

(ID:46965416)