Graph-Algorithmen

Vorwort

Diese Arbeit wurde mithilfe von KI übersetzt. Wir freuen uns über dein Feedback und deine Kommentare: [e-mail]

Was haben die folgenden Dinge gemeinsam: Marketing-Attributions-Analyse, Anti-Geldwäsche-Analyse (AML), Customer Journey Modeling, Kausalanalyse von Sicherheitsvorfällen, literaturbasierte Entdeckung, Erkennung von Betrugsnetzwerken, Analyse von Internet-Suchknoten, Erstellung von Kartenanwendungen, Analyse von Krankheitsclustern und die Analyse der Aufführung eines William Shakespeare-Stücks. Wie du vielleicht schon vermutet hast, haben sie alle die Verwendung von Graphen gemeinsam und beweisen, dass Shakespeare Recht hatte, als er sagte: "Die ganze Welt ist ein Graph!"

Okay, der Barde von Avon hat in diesem Satz nicht wirklich Graph geschrieben, sondern Stage. Beachte jedoch, dass die oben aufgeführten Beispiele alle Entitäten und die Beziehungen zwischen ihnen betreffen, sowohl direkte als auch indirekte (transitive) Beziehungen. Entitäten sind die Knoten im Graphen - das können Menschen, Ereignisse, Objekte, Konzepte oder Orte sein. Die Beziehungen zwischen den Knoten sind die Kanten im Diagramm. Besteht das Wesen eines Shakespeare-Stücks also nicht gerade in der aktiven Darstellung von Personen (den Knoten) und ihren Beziehungen (den Kanten)? Daher hätte Shakespeare in seiner berühmten Erklärung vielleicht auch Graph schreiben können.

Was Graphenalgorithmen und Graphdatenbanken so interessant und leistungsfähig macht, ist nicht die einfache Beziehung zwischen zwei Entitäten, bei der A mit B in Beziehung steht. Schließlich hat das standardmäßige relationale Datenbankmodell diese Art von Beziehungen schon vor Jahrzehnten in seinem Fundament, dem Entity Relationship Diagram (ERD), verankert. Was Graphen so bemerkenswert wichtig macht, sind gerichtete Beziehungen und transitive Beziehungen. Bei direktionalen Beziehungen kann A B verursachen, aber nicht das Gegenteil. Bei transitiven Beziehungen kann A direkt mit B und B direkt mit C verbunden sein, während A nicht direkt mit C verbunden ist, so dass A folglich transitiv mit C verbunden ist.

Mit diesen transitiven Beziehungen - insbesondere wenn sie zahlreich und vielfältig sind, mit vielen möglichen Beziehungs-/Netzwerkmustern und Trennungsgraden zwischen den Entitäten - deckt das Graphenmodell Beziehungen zwischen Entitäten auf, die andernfalls unverbunden oder unzusammenhängend erscheinen würden und von einer relationalen Datenbank nicht erkannt werden. Daher kann das Graphenmodell in vielen Anwendungsfällen der Netzwerkanalyse produktiv und effektiv eingesetzt werden.

Betrachte folgenden Anwendungsfall der Marketing-Attribution: Person A sieht die Marketingkampagne; Person A spricht darüber in den sozialen Medien; Person B ist mit Person A verbunden und sieht den Kommentar; und anschließend kauft Person B das Produkt. Aus der Sicht des Marketingkampagnenmanagers schlägt das Standard-Beziehungsmodell fehl, da B die Kampagne nicht gesehen und A nicht darauf reagiert hat. Die Kampagne sieht wie ein Misserfolg aus, aber ihr tatsächlicher Erfolg (und positiver ROI) wird vom Graph-Analytics-Algorithmus durch die transitive Beziehung zwischen der Marketingkampagne und dem endgültigen Kundenkauf über einen Vermittler (Entität in der Mitte) entdeckt.

Betrachten wir als Nächstes einen Analysefall zur Bekämpfung der Geldwäsche (AML): Die Personen A und C stehen im Verdacht, illegalen Handel zu treiben. Jede Interaktion zwischen den beiden (z. B. eine Finanztransaktion in einer Finanzdatenbank) würde von den Behörden bemerkt und streng geprüft werden. Wenn A und C jedoch nie gemeinsam Geschäfte tätigen, sondern ihre Finanztransaktionen über die sichere, angesehene und nicht gekennzeichnete Finanzbehörde B abwickeln, was könnte die Transaktion aufspüren? Der Graph-Analyse-Algorithmus! Die Graph-Engine würde die transitive Beziehung zwischen A und C über den Vermittler B entdecken.

Bei der Internetsuche verwenden die großen Suchmaschinen einen Algorithmus, der auf einem Hyperlink-Netzwerk (einem Graphen) basiert, um den zentralen maßgeblichen Knoten im gesamten Internet für eine bestimmte Menge von Suchbegriffen zu finden. Die Richtung der Kanten ist in diesem Fall entscheidend, da der maßgebliche Knoten im Netzwerk derjenige ist, auf den viele andere Knoten zeigen.

Mit der literaturbasierten Entdeckung (LBD) - einer Wissensnetzwerkanwendung (graphenbasiert), die bedeutende Entdeckungen in der Wissensbasis von Tausenden (oder sogar Millionen) von Forschungszeitschriftenartikeln ermöglicht - wird "verstecktes Wissen" nur durch die Verbindung zwischen veröffentlichten Forschungsergebnissen entdeckt, die viele Trennungsgrade (transitive Beziehungen) zwischen ihnen haben können. LBD wird auf Krebsforschungsstudien angewandt, bei denen die riesige semantische medizinische Wissensbasis von Symptomen, Diagnosen, Behandlungen, Wechselwirkungen von Medikamenten, genetischen Markern, kurzfristigen Ergebnissen und langfristigen Folgen bisher unbekannte Heilmittel oder nützliche Behandlungen für die undurchdringlichsten Fälle "verstecken" könnte. Das Wissen könnte bereits im Netzwerk vorhanden sein, aber wir müssen die Punkte miteinander verbinden, um es zu finden.

Ähnliche Beschreibungen der Leistungsfähigkeit von Graphen lassen sich auch für die anderen oben aufgeführten Anwendungsfälle geben, die alle Beispiele für die Netzwerkanalyse durch Graphenalgorithmen sind. In jedem Fall geht es um Entitäten (Menschen, Objekte, Ereignisse, Aktionen, Konzepte und Orte) und ihre Beziehungen (Berührungspunkte, sowohl kausale als auch einfache Assoziationen).

Wenn wir über die Leistungsfähigkeit von Graphen nachdenken, sollten wir bedenken, dass der vielleicht mächtigste Knoten in einem Graphenmodell für reale Anwendungsfälle der "Kontext" sein könnte. Der Kontext kann Zeit, Ort, verwandte Ereignisse, nahe gelegene Objekte und vieles mehr umfassen. Die Einbeziehung des Kontexts in den Graphen (als Knoten und als Kanten) kann daher zu beeindruckenden prädiktiven und präskriptiven Analysen führen.

Das Buch Graph Algorithms von Mark Needham und Amy Hodler zielt darauf ab, unser Wissen und unsere Fähigkeiten rund um diese wichtigen Arten von Graphenanalysen zu erweitern, einschließlich Algorithmen, Konzepten und praktischen Anwendungen des maschinellen Lernens. Von grundlegenden Konzepten über fundamentale Algorithmen bis hin zu Verarbeitungsplattformen und praktischen Anwendungsfällen haben die Autoren einen lehrreichen und anschaulichen Leitfaden für die wunderbare Welt der Graphen zusammengestellt.

Kirk Borne, PhD

Principal Data Scientist und Executive Advisor

Booz Allen Hamilton

März 2019