Wofür sind Graph-Analytics-Werkzeuge in der Praxis gut?

Mit der Entwicklung von Graph-Datenbanken wie Neo4j und Amazon Neptune oder Packages wie GraphX und GraphFrame für Apache Spark stehen heute Tools für die Analyse sehr großer Netzwerke zur Verfügung, während auf der anderen Seite die zur Analyse verfügbaren Daten, z.B. aus sozialen Netzwerken und dem Internet of Things (IoT), immer umfangreicher werden.

Dieser Blogeintrag beschreibt einige Anwendungsbereiche, in denen mittels Graph Analytics wertvolle Informationen aus Daten generiert werden können.

Was ist ein (mathematischer) Graph?

Mathematische Graphen sind Datenstrukturen, die aus einer Menge von beliebigen Objekten (genannt Knoten, „nodes“) sowie einer Menge von direkten Verbindungen (genannt Kanten, „edges“) zwischen diesen Objekten bestehen.

Abbildung 1: Gerichteter Graph

Hier einige Beispiele:

  • Facebook kann als Graph aufgefasst werden: Die User sind die Knoten des Graphen, und sind zwei User befreundet, dann stellt diese Verbindung eine Kante des Graphen dar.
  • Bei einem Zeitschriftenverlag bilden die Abonnenten die Menge der Knoten eines Graphen. Zwei Abonnenten sind durch eine Kante verbunden, wenn einer den anderen Abonnenten geworben hat. Dies ist ein Beispiel für gerichtete Graphen, bei denen die Kanten zusätzlich eine Richtung haben: Eine Kante zeigt vom Werber zum Geworbenen.
  • Auf einer Website stellt jede (Unter-)Seite einen Knoten dar. Ein Link, der von einer auf eine andere Seite verweist, ist eine Kante. Dasselbe funktioniert natürlich auch für die Gesamtheit aller Websites.
  • Jede Bus- oder Tram-Haltestelle in Zürich ist ein Knoten. Jede direkte Verbindung zwischen zwei Haltestellen bildet dann eine Kante.

Abbildung 2: Liniennetz von Zürich als Graph

Use Case 1: Features für Machine Learning generieren

Die Qualität eines Machine-Learning-Modells hängt in hohem Maß von den verfügbaren Input-Datenmerkmalen ab. Dafür werden oft Merkmale über das Kaufverhalten, demographische Merkmale oder extern erworbene Merkmale verwendet.

In den Kundenbeständen größerer Unternehmen sind jedoch auch Netzwerke vorhanden. Kunden kennen sich, sind verwandt oder befreundet und kommunizieren miteinander. Sie sprechen auch über die Erfahrungen, die sie als Kunden mit dem Unternehmen machen, über Werbung, die sie erhalten, über neue Produkte und Angebote. Firmenkunden können wirtschaftlich verbunden sein, z. B. über Konzernverflechtungen und Beteiligungen, aber auch durch Geschäftsbeziehungen.

Obwohl dem Unternehmen vieles davon verborgen bleibt, gibt es Möglichkeiten, Verbindungen zwischen Kunden festzustellen. Im Privatkundenbestand einer Bank etwa kann man Netzwerke identifizieren, indem man Gemeinschaftskonten und Bevollmächtigungen betrachtet. Bei Telekommunikationsunternehmen können Telefon- und SMS-Verbindungsdaten genutzt werden. Über Namens- und Adressanalysen werden Familienverbünde und Hausgemeinschaften identifiziert. Kundenempfehlungsprogramme liefern gute Hinweise auf persönliche Bekanntschaften.

Um diese Informationen für Machine Learning zu nutzen, muss die in den Netzwerken enthaltene Information extrahiert und aufbereitet werden. Dafür sind Graphenanalyse-Tools prädestiniert. Folgende Merkmale können z. B. wichtige Beiträge leisten:

  • Die Rolle des Kunden im Netzwerk: Beeinflusst sie/er andere Kunden? Ist der Kunde eher isoliert? Hat er/sie viele Kontakte außerhalb des Kundennetzwerks?
  • Die Anzahl der direkten oder indirekten Kontakte (Kontakte 2. Grades).
  • Die „Betweenness“ ist ein Maß für die Bedeutung eines Kunden für die Kommunikation im Netzwerk.

Es gibt viele weitere Kennzahlen, die für die Knoten eines Graphen berechnet werden können. Wie so oft bei der Datenvorbereitung innerhalb des Machine-Learning-Prozesses kann es sich lohnen, verschiedene davon auszuprobieren und zu kombinieren.

Use Case 2: Erkennung von Bots in Netzwerken

Eine wichtige Erfolgskennzahl für Twitter-Posts ist die Anzahl der Retweets. Um diese Zahl künstlich in die Höhe zu treiben, werden Bot-Accounts angelegt, die den Ziel-Account automatisiert mehrfach retweeten. 

Beim Einsatz von Twitter-Daten zu Analysezwecken stehen Unternehmen dann vor dem Problem, dass von den beschriebenen Bots getätigte Retweets die Daten massiv verzerren und somit die Analyseergebnisse wertlos machen können.

Um Bot-Accounts zu erkennen, wird ein gerichteter Graph aufgebaut: Accounts sind die Knoten, die Retweets bestimmen die Kanten. Die gerichteten Kanten werden dabei mit Gewichten belegt: Je mehr Retweets, desto höher das Kantengewicht.

Durch Berechnung von geeigneten Kennzahlen für die Knoten können auf Basis des beschriebenen Graphen Bot-Accounts identifiziert und von der eigentlichen Analyse ausgeschlossen werden.

Use Case 3: Kunden als Multiplikatoren

Netzwerke im Privatkundenbestand eines Unternehmens können vor allem im Marketing genutzt werden. Manche Kunden sind sehr wichtig für das Unternehmen, und zwar nicht (nur), weil sie besonders viel zum Umsatz beitragen, sondern wegen ihrer sozialen Kontakte zu anderen Kunden.

In Netzwerken werden die Teilnehmer in drei Typen eingeteilt:

  • „Konnektoren“, die sehr viele Verbindungen zu anderen Individuen haben,
  • „Experten“, die das Netzwerk mit neuen Informationen versorgen, und
  • „Verkäufer“, die andere von einer Sache überzeugen können.

Speziell Konnektoren und Verkäufer fungieren dann als Multiplikatoren, um die gewünschte Botschaft weiter im Kundenbestand zu kommunizieren. Hat man diese Schlüsselfiguren identifiziert, so ist man in der Lage, mit relativ wenig Aufwand einen großen Teil seiner Kunden zu erreichen.

Weitere Use Cases: kürzeste Wege, optimale Matchings etc.

Vor allem in der Industrie finden sich viele Anwendungen klassischer Graphenalgorithmen wie das Auffinden des kürzesten Weges zwischen zwei Knoten, die Bestimmung der kürzesten Rundreise über alle Knoten oder des maximalen Durchflusses von einem Knoten zu einem anderen. Diese Verfahren sind teilweise sehr rechenintensiv und profitieren daher besonders von neuen Technologien, wie verteiltes Rechnen mit Spark.

Kürzeste Wege

Problem: Finde zwischen zwei festgelegten Knoten (Start und Ziel) eines Graphen den kürzesten Weg über die Kanten des Graphen. „Kurz“ bezieht sich dabei auf die Kantengewichte.

Für die Lösung dieses Problems gibt es sehr effiziente Algorithmen (am bekanntesten ist der von Dijkstra) und fast jeder dürfte schon davon profitiert haben: In Navigationsgeräten und

Karten-Apps werden diese Verfahren intensiv genutzt.

Abbildung 3: Routenplanung

Kürzeste Rundreise, Travelling Salesman Problem (TSP)

Problem: Finde den kürzesten Weg, der jeden Knoten eines Graphen genau einmal enthält und am Ende wieder beim Ausgangspunkt ankommt.

Im Gegensatz zum Kürzeste-Wege-Problem ist die Lösung dieses Problems sehr rechenintensiv. Von den vielen denkbaren Anwendungen seien nur zwei herausgegriffen:

Routenplanung für Außendienstmitarbeiter: Ein Unternehmen mit einer hohen Zahl von Mitarbeitern im Außendienst kann hohe Effizienzgewinne durch eine optimale Routenplanung erzielen.

Fertigungsoptimierung: In ein Werkstück, das in großer Zahl produziert wird, müssen an vielen Stellen Löcher gebohrt werden. Der Bohrer fährt in einer festzulegenden Reihenfolge über das Werkstück, um am Ende wieder seine ursprüngliche Position einzunehmen. Die Reihenfolge, in der die Bohrpositionen angesteuert werden, kann mit einem TSP-Algorithmus optimiert werden.

Optimale Zuordnung, Matching

Problem: Bei einer gegebenen Menge von Objekten und deren Verbindungen, wobei diesen ein Wert oder Gewicht gegeben wurde, finde eine Auswahl der Verbindungen, sodass jedes Objekt mit höchstens einem anderen Objekt verbunden und die Summe der Werte maximal ist.

Beispielsweise können auf diese Weise anstehende Aufgaben optimal an die Mitarbeiter eines Unternehmens vergeben werden. Der Graph besteht aus den Mitarbeitern und den zu erledigenden Aufgaben, wobei die Eignung der Mitarbeiter für die Aufgaben jeweils mit einem Wert versehen ist.

Die Abbildung zeigt dies an einem kleinen Beispiel: 4 Aufgaben sind zu erledigen, dafür stehen 3 Mitarbeiter zur Verfügung. Als Vorbereitung wird jedem Mitarbeiter für die verschiedenen Aufgaben jeweils eine Maßzahl zwischen 1 und 9 zugeordnet, wobei 1 eine sehr geringe und 9 eine sehr hohe Kompetenz bedeutet.

Die optimale Zuordnung der Aufgaben hat einen Gesamtwert von 20. Aufgabe 4 wird von Mitarbeiter 1 erledigt, obwohl Mitarbeiter 3 dafür etwas besser geeignet wäre. Der erledigt jedoch Aufgabe 3, da er dafür viel besser geeignet ist als Mitarbeiter 2. Aufgabe 1 bleibt vorläufig unerledigt.

Abbildung 4: Optimierung des Mitarbeitereinsatzes

Zusammenfassung

In der Wirtschaft finden sich viele Anwendungsbereiche für Graph Analytics. Ob im Marketing, in der Betrugserkennung, der Webdatenanalyse, dem Risikomanagement, der Produktion oder in anderen Bereichen: Die Datenmengen werden immer größer, und viele Datenbestände bilden Beziehungen zwischen Objekten ab. Zum Glück gibt es heute Technologien, die Graphen mit sehr großen Datenmengen effizient speichern und analysieren können.

In einem folgenden Blog-Eintrag wird die Verarbeitung und Analyse von Graphen mit der GraphFrame-API von Apache Spark beleuchtet.


Peter-Gerngross

Kontakt

Peter Gerngross
Senior Consultant
DE +49 89 122 281 110
CH +41 44 585 39 80
marketing@btelligent.com
Views: 385
clear