Graphentheorie als Durchblickverschaffer in einer vernetzten Welt

Graphentheorie Netzwerkanalyse

Steuerbetrug, Geldwäsche und Terrorfinanzierung aufdecken, Staus vermeiden, Finanzkrisen, Pandemien, Ansteckungsrisiken von Krankheiten und politische Krisen vorhersagen. Alle diese Aufgaben sind tatsächliche und mögliche Einsatzgebiete der Graphentheorie. Für Unternehmen, Behörden und Regierungen gewinnt diese Disziplin zum Erkennen von Mustern in komplexen Netzwerken deutlich an Relevanz.

Vereinfacht erklärt ist die Graphentheorie ein Teilgebiet der Mathematik. Ein Graph besteht aus Knoten und Kanten, die jeweils zwei Knoten verbinden. Dabei können Kanten beispielsweise eine Richtung haben oder gewichtet sein. Ein witziges Einstiegsvideo für Schüler veranschaulicht die Theorie.

Quelle: https://www.youtube.com/watch?v=frG2kBMZQDc

Graphentheorie im täglichen Gebrauch

Soziale Netzwerke wie Facebook, Instagram, Twitter, LinkedIn und Xing sind offensichtliche Beispiele für den Einsatz der Graphentheorie. Bei Facebook sind die User die Knoten, und eine Kante wird zwischen Usern gezogen, falls diese auf der Plattform befreundet sind. Die Knoten können Eigenschaften haben, so genannte Labels. In einem internen Kommunikationsnetzwerk eines Unternehmens könnte das beispielsweise die Karrierestufe sein (Junior, Senior, etc.).

Ziel der Graphentheorie ist es, komplexe Strukturen mit Hilfe eines Netzwerks zu modellieren und bislang unerklärte Phänomene zu erklären. Ein bekanntes Feature von Plattformen wie Facebook und LinkedIn ist, Benutzern Personen vorzuschlagen, die sie möglicherweise kennen. Dahinter steckt ein Algorithmus namens Link-Prediction. Dieser Algorithmus beantwortet die Frage aus der Graphentheorie, welche neuen Kanten wahrscheinlich entstehen. Zur Beantwortung der Frage betrachten Facebook und LinkedIn gemeinsame Nachbarn oder Kollegen sowie das erweiterte Umfeld des Nutzers.

Die wahrscheinlich meist genutzte Suchmaschine Google-Suche basierte in den Anfangszeiten auf dem Page Rank. Die Google-Gründer Larry Page und Sergey Brin nutzen hierfür ebenfalls die Graphentheorie: Sie haben einen Algorithmus implementiert, der die Wichtigkeit einer Webseite basierend auf der Hyperlink-Netzwerk-Struktur vorhersagt. Jede Webseite erhält dabei einen Score, der auf den „In-Links“ basiert, d.h. der Anzahl an Hyperlinks zu dieser Seite. Dabei erhält eine Webseite einen hohen Score, wenn viele In-Links vorhanden sind.

Einsatzgebiet Netzwerkanalyse

Es gibt noch deutlich mehr Beispiele, wie Unternehmen die Graphentheorie in der Praxis einsetzen:

  • Google Maps nutzt die Graphentheorie auch zur Berechnung des kürzesten Weges.
  • HP Labs hat in einem Versuch die E-Mail-Kommunikation von 436 Mitarbeitern untersucht. Ziel war unter anderem herauszufinden, wer im Unternehmen viel Einfluss hat (Alpha User).
  • Ein anderes Anwendungsgebiet ist die Luftfahrt. Mithilfe der Graphentheorie lässt sich der Flugverkehr rund um die Welt untersuchen. Dabei kann unter anderem ermittelt werden, welcher Flughafen das höchste Risiko hat, einen Virus zu verbreiten.
  • Ein im alltäglichen Gebrauch stark genutztes Netzwerk ist das öffentliche Nahverkehrsnetz. Die Planer im Verkehrsbetrieb visualisieren mithilfe von Graphen, wie wer am schnellsten von einem Ort zu einem anderen kommt, sowie welcher Bahnhof besonders während der Rushhour besonders stark belastet ist.

Die Liste der Anwendungsbeispiele lässt sich beliebig fortführen. Einsatzszenarien findet man in nahezu allen Branchen: der Biologie (Protein-protein interactions), der IT und Telekommunikation (Internet Konnektivität, Routing Internet Traffic), der Politik (Kommunikation zwischen dem rechten und linken Flügeln in politischen Blogs) sowie im Finanzsektor (Investitionen an der Börse). Ihnen gemein ist, dass in jedem Szenario Beziehungen und Interaktionen in einem komplexen Netzwerkgebilde veranschaulicht werden. Die Ziele sind, Rückschlüsse für die Zukunft ziehen zu können oder Phänomene, Aktivitäten und Zusammenhänge aufzudecken, die sonst verborgen blieben.

Betrüger nutzen gerne ähnliche Netzwerke

Die Panama Papers (Offshore Leaks) sind im Finanzsektor ein sehr bekanntes Beispiel für die Anwendung der Graphentheorie, um ein Netzwerk an Steuervermeidung offenzulegen. Die veröffentlichten Daten (Offshore Leaks Database von ICIJ) wurden mit unterschiedlichem Fokus analysiert, z.B. mit einem besonderen Schwerpunkt auf Saudi-Arabien und Jordanien oder die portugiesischen Verbindungen in den Panama Papers. Dabei wurden die veröffentlichten Unternehmen (Geschäftsführer und Gesellschafter) sowie die Adresse und Beziehungen zwischen Unternehmen untersucht.

Abseits der Panama Papers schätzen Banken und Strafverfolgungsbehörden die Graphentheorie im Bereich Fraud Detection (Kreditkartenbetrug, Bankbetrug, Versicherungsbetrug und Internetverkaufsbetrug) mittlerweile als ein sehr mächtiges Tool. Die Analyse der Beziehungen liefert oftmals deutlich mehr Informationen als nur das Auflisten der Eigenschaften der Entitäten. Unsere Experten für Künstliche Intelligenz in Spanien haben, ebenfalls basierend auf der Graphentheorie, ein Modell zum Aufdecken von Steuerbetrug für die spanische Steuerbehörde (Agencia Tributaria) entwickelt. Sie nutzen hierfür die Annahme, dass Betrüger sich ähneln und sich ähnlich verhalten (Profiling) sowie voneinander lernen und sich deshalb in ähnlichen Kreise bewegen (Netzwerkanalyse).

Alternativer Link zum Video: http://bit.ly/VIDEO_AntiFraudModel

Die Analyse von Netzwerken wird immer wichtiger

Die Graphentheorie kann viele unterschiedliche Fragestellungen lösen. Es bietet die Möglichkeit jegliche Zustände diskreter Objekte und deren Beziehungen untereinander zu modellieren und zu analysieren. Ob man nun dezentrale Stromnetze (Smart Grid) steuern, Ampeln auf Basis von Fahrzeug- und Verkehrsdaten schalten oder unerlaubte Handlungen aufdecken möchte: Viele Probleme, die sich durch die zunehmende Vernetzung mit herkömmlichen Methoden kaum noch überschauen lassen, können mithilfe von Algorithmen sowie der Analyse von Netzwerken gelöst werden. Es muss ja nicht gleich die Entwicklung einer Simulation der Welt sein.

Foto: Getty Images / peterhowell


Yvonne Awaloff

Yvonne Awaloff ist Beraterin im Bereich Künstliche Intelligenz von Sopra Steria Consulting. Die studierte Bioinformatikerin bloggt hier vor allem über Machine und Deep Learning.


Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.