Graph Algorithms

Mit dem Buch über Graph-Algorithmen ist den Autoren eine verständliche Einführung in das Thema gelungen, die theoretische Grundlagen mit anschaulichen Praxisbeispielen verbindet.

Literatur Christian Winkler  –  0 Kommentare

Mark Needham, Amy E. Hodler
Graph Algorithms – Practical Examples in Apache Spark and Neo4j

O’Reilly, 2019
239 Seiten, EUR 67,30
ISBN: 978-1-492-05781-9

Graphen sind in der Informatik wichtige Datenstrukturen. Sie repräsentieren auf natürliche Weise verschiedenste Zusammenhänge aus dem echten Leben. Eine wahre Renaissance erleben sie durch die sozialen Netzwerke – zumal die immer weiter steigende Rechenleistung von IT-Systemen die Anwendung vieler Graph-Algorithmen erst alltagstauglich gemacht hat.

Einführung in Graphen

Das Buch beginnt mit einer leichtverständlichen Einführung in Graphen und einer Motivation, wann sich Graphen besonders effizient und sinnvoll einsetzen lassen. Die Autoren stellen verbundene und unverbundene, gerichtete und ungerichtete sowie zyklische und azyklische Graphen vor. Darauf folgt eine anschauliche und detaillierte Erklärung der verwendeten Terminologie. Die geschickt gewählten Beispiele erleichtern das Verständnis der unterschiedlichen Graphentypen. Auch die Beschreibung der wichtigsten Algorithmen kommt nicht zu kurz.

Plattformen, Pfade und Graphsuche

Das folgende Kapitel beschäftigt sich mit der Data Processing Engine Apache Spark und der Graphdatenbank Neo4j. Darin differenzieren die Autoren zumindest grob, zu welchem Zweck und wie diese beiden Plattformen bei der Arbeit mit den Graphen zum Einsatz kommen. Wichtige Detailinformationen zum Speicherverbrauch, zur Laufzeit und Skalierbarkeit der Algorithmen sucht man allerdings vergeblich.

Graph Algorithms – Practical Examples in Apache Spark and Neo4j (Bild: O'Reilly)

Stattdessen konzentrieren sich die Autoren auf unterschiedliche Methoden, wie man Graphen durchsuchen kann, und stellen die beiden wichtigsten Algorithmen (Suche in die Tiefe beziehungsweise Breite) im Detail vor. Dazu ziehen sie beispielhaft die Entfernungsdaten niederländischer und englischer Städte heran. Eine Besprechung, wie man kürzeste Verbindungen in Graphen findet, rundet das Kapitel ab. Auch die Diskussion von Spanning Tree und Random Walk kommt nicht zu kurz. Sämtliche Beispiele sind sowohl in Spark als auch in Neo4j illustriert.

Zentralitäten und Communities

Eine wichtige Größe für die Knoten in Graphen ist die sogenannte Zentralität. Mit ihr beschäftigen sich die Autoren anschließend ausführlich und in unterschiedlichen Varianten. Die Bedeutung der unterschiedlichen Zentralitätsmaße wird detailliert erläutert, nicht jedoch die Unterschiede in der algorithmischen Komplexität zur Berechnung. Mithilfe von Zentralitäten lassen sich Knoten zu sogenannten Communities zusammenfassen. Dieser wichtigen Aufgabe widmen die Autoren ein weiteres Kapitel – mit ebenfalls vielen, gut beschriebenen Beispielen.

Anwendungen von Graphen

In den beiden letzten Kapiteln des Buchs dreht sich alles um die Anwendung von Graphen. Dazu greifen die Autoren zunächst auf Yelp-Daten zurück, die aufgrund ihrer freien (akademischen) Verfügbarkeit in vergleichbaren Situationen häufig herangezogen werden. Das gewählte Beispiel zur Trip-Planung erscheint allerdings etwas konstruiert. Viel besser ist hingegen die Bestimmung der einflussreichsten Hotel-Bewerter, weil sich Graphen besonders für die Influencer-Detection über alle sozialen Netzwerke hinweg eignen.

Beim zweiten Beispiel steht die Analyse von Flugdaten amerikanischer Flughäfen im Fokus. Mithilfe von Spark bestimmen die Autoren darin den Grad von Flughäfen und clustern diese mit Label Propagation.

Das letzte Kapitel schließlich zeigt, wie sich Graphen mit Machine Learning verbinden lassen. In dem Beispiel erreichen die Autoren überdurchschnittlich gute Ergebnisse für Precision und Recall bei der Vorhersage eines Autorennetzwerks. Die Beiträge der einzelnen Features sind dabei nachvollziehbar beschrieben. Es zeigt sich, dass die Graph-Features tatsächlich eine entscheidende Rolle spielen. Ein eher unkonventionelles Beispiel, das die Lektüre auch für Machine-Learning-Experten lohnenswert macht.

Nicht nur für Apache Spark und Neo4j

Obwohl der Titel impliziert, dass die Beispiele ausschließlich für Apache Spark und Neo4j gedacht sind, ist deren Benutzung oft nur im letzten Schritt der dargestellten Vorgehensweise relevant. Alle vorausgehenden Erklärungen sind völlig unabhängig von der Software und ermöglichen so einen leicht verständlichen allgemeinen Einstieg in das Thema Graphen.

Fazit

Den Autoren ist ein optisch ansprechendes und gut lesbares Buch mit Liebe zum Detail gelungen. Die Beispiele sind praxisnah – und der Leser lernt ganz nebenbei auch noch ein bisschen über die Geografie der Niederlande und Südengland.

Leider fehlt an den entscheidenden Stellen für viele Algorithmen die Angabe zum Laufzeitverhalten (O(N)) und für den Speicherbedarf. Das ist schade, denn in der Praxis stoßen gerade Analysen der umfangreichen Daten sozialer Netzwerke schnell an die Grenzen der vorhandenen IT-Systeme. Es wäre daher spannend gewesen, zu erfahren, wie Spark und Neo4j mit diesen Anforderungen umgehen.

Eine Kaufempfehlung ist das Buch trotzdem, denn fast alle wichtigen Algorithmen sind auch für Einsteiger detailliert und anschaulich erklärt. Wer hingegen "richtig große" Graphen analysieren will, wagt sich in neues, unbekanntes Terrain und sollte gegebenenfalls auf passende Erfahrungsberichte aus der Praxis zurückgreifen. (map)

Christian Winkler
arbeitet seit 20 Jahren in der Softwareentwicklung im Bereich Big Data/KI, insbesondere mit Fokus auf intelligente Algorithmen zur Massendatenverarbeitung im Bereich des maschinellen Lernens, der Geodatenverarbeitung und Statistik. Er ist Speaker auf Konferenzen und Autor von Artikeln zu Big Data/KI.