Graph Data Science mit Python/NetworkX

Wir werden mit Daten überschwemmt. Ständig wachsende Datenbanken und Tabellenkalkulationen sind voll von verborgenen Geschäftserkenntnissen. Wie können wir Daten analysieren und Schlussfolgerungen ziehen, wenn es so viele davon gibt? Graphen (Netzwerke, keine Balkendiagramme) bieten einen eleganten Ansatz.

Wir verwenden häufig Tabellen, um Informationen generisch darzustellen. Aber Graphen verwenden eine spezielle Datenstruktur: Anstelle einer Tabellenzeile repräsentiert ein Knoten ein Element. Eine Kante verbindet zwei Knoten, um ihre Beziehung anzuzeigen.

Diese Graphdatenstruktur ermöglicht es uns, Daten aus einzigartigen Blickwinkeln zu betrachten, weshalb die Graphdatenwissenschaft in allen Bereichen von der Molekularbiologie bis zu den Sozialwissenschaften eingesetzt wird:

Wie können Entwickler also die Graph Data Science nutzen? Wenden wir uns der am häufigsten verwendeten Data-Science-Programmiersprache zu: Python.

Erste Schritte mit „Graphentheorie“ Graphen in Python

Python-Entwicklern stehen mehrere Grafikdatenbibliotheken zur Verfügung, darunter NetworkX, igraph, SNAP und graph-tool. Abgesehen von den Vor- und Nachteilen haben sie sehr ähnliche Schnittstellen für die Handhabung und Verarbeitung von Python-Graph-Datenstrukturen.

Wir verwenden die beliebte NetworkX-Bibliothek. Es ist einfach zu installieren und zu verwenden und unterstützt den Community-Erkennungsalgorithmus, den wir verwenden werden.

Das Erstellen eines neuen Diagramms mit NetworkX ist einfach:

 import networkx as nx G = nx.Graph()

Aber G ist noch kein großer Graph, da es keine Knoten und Kanten hat.

So fügen Sie einem Diagramm Knoten hinzu

Wir können dem Netzwerk einen Knoten hinzufügen, indem wir den Rückgabewert von Graph() mit .add_node() (oder .add_nodes_from() für mehrere Knoten in einer Liste) verketten. Wir können den Knoten auch beliebige Eigenschaften oder Attribute hinzufügen, indem wir ein Wörterbuch als Parameter übergeben, wie wir mit node 4 und node 5 zeigen:

 G.add_node("node 1") G.add_nodes_from(["node 2", "node 3"]) G.add_nodes_from([("node 4", {"abc": 123}), ("node 5", {"abc": 0})]) print(G.nodes) print(G.nodes["node 4"]["abc"]) # accessed like a dictionary

Dies wird ausgeben:

 ['node 1', 'node 2', 'node 3', 'node 4', 'node 5'] 123

Aber ohne Kanten zwischen Knoten sind sie isoliert, und der Datensatz ist nicht besser als eine einfache Tabelle.

So fügen Sie Kanten zu einem Diagramm hinzu

Ähnlich wie bei der Technik für Knoten können wir .add_edge() mit den Namen von zwei Knoten als Parameter verwenden (oder .add_edges_from() für mehrere Kanten in einer Liste) und optional ein Wörterbuch mit Attributen hinzufügen:

 G.add_edge("node 1", "node 2") G.add_edge("node 1", "node 6") G.add_edges_from([("node 1", "node 3"), ("node 3", "node 4")]) G.add_edges_from([("node 1", "node 5", {"weight" : 3}), ("node 2", "node 4", {"weight" : 5})])

Die NetworkX-Bibliothek unterstützt Diagramme wie diese, bei denen jede Kante ein Gewicht haben kann. Beispielsweise könnte in einem Diagramm eines sozialen Netzwerks, in dem Knoten Benutzer und Kanten Interaktionen sind, die Gewichtung angeben, wie viele Interaktionen zwischen einem bestimmten Benutzerpaar stattfinden – eine hochrelevante Metrik.

NetworkX listet alle Kanten auf, wenn G.edges verwendet wird, enthält jedoch nicht deren Attribute. Wenn wir Kantenattribute wollen, können wir G[node_name] , um alles zu erhalten, was mit einem Knoten verbunden ist, oder G[node_name][connected_node_name] , um die Attribute einer bestimmten Kante zu erhalten:

 print(G.nodes) print(G.edges) print(G["node 1"]) print(G["node 1"]["node 5"])

Dies wird ausgeben:

 ['node 1', 'node 2', 'node 3', 'node 4', 'node 5', 'node 6'] [('node 1', 'node 2'), ('node 1', 'node 6'), ('node 1', 'node 3'), ('node 1', 'node 5'), ('node 2', 'node 4'), ('node 3', 'node 4')] {'node 2': {}, 'node 6': {}, 'node 3': {}, 'node 5': {'weight': 3}} {'weight': 3}

Aber unsere erste Grafik auf diese Weise zu lesen, ist unpraktisch. Zum Glück gibt es eine viel bessere Darstellung.

So generieren Sie Bilder aus Diagrammen (und gewichteten Diagrammen)

Die Visualisierung eines Diagramms ist unerlässlich: Es lässt uns die Beziehungen zwischen den Knoten und die Struktur des Netzwerks schnell und klar erkennen.

Ein kurzer Aufruf von nx.draw(G) :

Lassen Sie uns über unseren nx.draw() gewichtigere Kanten entsprechend dicker machen:

 weights = [1 if G[u][v] == {} else G[u][v]['weight'] for u,v in G.edges()] nx.draw(G, width=weights)

Wir haben eine Standarddicke für schwerelose Kanten bereitgestellt, wie im Ergebnis zu sehen ist:

Unsere Methoden und Graphalgorithmen werden immer komplexer, daher besteht der nächste Schritt darin, einen bekannteren Datensatz zu verwenden.

Graph Data Science mit Daten aus dem Film Star Wars: Episode IV

Um die Interpretation und das Verständnis unserer Ergebnisse zu erleichtern, verwenden wir diesen Datensatz. Knoten stellen wichtige Charaktere dar, und Kanten (die hier nicht gewichtet werden) bedeuten das gemeinsame Erscheinen in einer Szene.

Hinweis: Der Datensatz stammt von Gabasova, E. (2016). Star Wars soziales Netzwerk. DOI: https://doi.org/10.5281/zenodo.1411479.

Zuerst visualisieren wir die Daten mit nx.draw(G_starWars, with_labels = True) :

Charaktere, die normalerweise zusammen erscheinen, wie R2-D2 und C-3PO, erscheinen eng verbunden. Im Gegensatz dazu können wir sehen, dass Darth Vader keine Szenen mit Owen teilt.

Python NetworkX-Visualisierungslayouts

Warum befindet sich jeder Knoten dort, wo er sich im vorherigen Diagramm befindet?

Es ist das Ergebnis des standardmäßigen spring_layout Algorithmus. Es simuliert die Kraft einer Feder, die verbundene Knoten anzieht und getrennte abstößt. Dies hilft, gut verbundene Knoten hervorzuheben, die in der Mitte enden.

NetworkX hat andere Layouts, die andere Kriterien verwenden, um Knoten zu positionieren, wie etwa circular_layout :

 pos = nx.circular_layout(G_starWars) nx.draw(G_starWars, pos=pos, with_labels = True)

Das Ergebnis:

Dieses Layout ist neutral in dem Sinne, dass die Position eines Knotens nicht von seiner Wichtigkeit abhängt – alle Knoten werden gleichermaßen dargestellt. (Das kreisförmige Layout könnte auch dabei helfen, separate verbundene Komponenten zu visualisieren – Untergraphen mit einem Pfad zwischen zwei beliebigen Knoten – aber hier ist der gesamte Graph eine große verbundene Komponente.)

Beide Layouts, die wir gesehen haben, weisen ein gewisses Maß an visueller Unordnung auf, da Kanten andere Kanten frei kreuzen können. Aber Kamada-Kawai, ein weiterer kraftgesteuerter Algorithmus wie spring_layout , positioniert die Knoten so, dass die Energie des Systems minimiert wird.

Dies reduziert Kantenüberschreitungen, hat aber seinen Preis: Es ist langsamer als andere Layouts und daher nicht sehr empfehlenswert für Diagramme mit vielen Knoten.

Dieser hat eine spezielle Draw-Funktion:

 nx.draw_kamada_kawai(G_starWars, with_labels = True)

Das ergibt stattdessen diese Form:

Ohne besonderen Eingriff platziert der Algorithmus Hauptfiguren (wie Luke, Leia und C-3PO) in der Mitte und weniger prominente (wie Camie und General Dodonna) am Rand.

Die Visualisierung des Diagramms mit einem bestimmten Layout kann uns einige interessante qualitative Ergebnisse liefern. Dennoch sind quantitative Ergebnisse ein wesentlicher Bestandteil jeder datenwissenschaftlichen Analyse, daher müssen wir einige Metriken definieren.

Knotenanalyse: Grad und PageRank

Jetzt, da wir unser Netzwerk klar visualisieren können, könnte es für uns von Interesse sein, die Knoten zu charakterisieren. Es gibt mehrere Metriken, die die Eigenschaften der Knoten und in unserem Beispiel der Zeichen beschreiben.

Eine grundlegende Metrik für einen Knoten ist sein Grad: wie viele Kanten er hat. Der Knotengrad eines Star Wars -Charakters misst, mit wie vielen anderen Charakteren er eine Szene teilt.

Die Funktion degree() kann den Grad eines Zeichens oder des gesamten Netzwerks berechnen:

 print(G_starWars.degree["LUKE"]) print(G_starWars.degree)

Die Ausgabe beider Befehle:

 15 [('R2-D2', 9), ('CHEWBACCA', 6), ('C-3PO', 10), ('LUKE', 15), ('DARTH VADER', 4), ('CAMIE', 2), ('BIGGS', 8), ('LEIA', 12), ('BERU', 5), ('OWEN', 4), ('OBI-WAN', 7), ('MOTTI', 3), ('TARKIN', 3), ('HAN', 6), ('DODONNA', 3), ('GOLD LEADER', 5), ('WEDGE', 5), ('RED LEADER', 7), ('RED TEN', 2)]

Das Sortieren von Knoten vom höchsten zum niedrigsten nach Grad kann mit einer einzigen Codezeile erfolgen:

 print(sorted(G_starWars.degree, key=lambda x: x[1], reverse=True))

Die Ausgabe:

 [('LUKE', 15), ('LEIA', 12), ('C-3PO', 10), ('R2-D2', 9), ('BIGGS', 8), ('OBI-WAN', 7), ('RED LEADER', 7), ('CHEWBACCA', 6), ('HAN', 6), ('BERU', 5), ('GOLD LEADER', 5), ('WEDGE', 5), ('DARTH VADER', 4), ('OWEN', 4), ('MOTTI', 3), ('TARKIN', 3), ('DODONNA', 3), ('CAMIE', 2), ('RED TEN', 2)]

Da es sich nur um eine Summe handelt, berücksichtigt der Grad keine Details einzelner Kanten. Verbindet sich eine bestimmte Kante mit einem ansonsten isolierten Knoten oder mit einem Knoten, der mit dem gesamten Netzwerk verbunden ist? Der PageRank-Algorithmus von Google aggregiert diese Informationen, um abzuschätzen, wie „wichtig“ ein Knoten in einem Netzwerk ist.

Die PageRank-Metrik kann als Agent interpretiert werden, der sich zufällig von einem Knoten zum anderen bewegt. Besser verbundene Knoten haben mehr Pfade, die durch sie führen, sodass der Agent sie tendenziell häufiger besucht.

Solche Knoten haben einen höheren PageRank, den wir mit der NetworkX-Bibliothek berechnen können:

 pageranks = nx.pagerank(G_starWars) # A dictionary print(pageranks["LUKE"]) print(sorted(pageranks, key=lambda x: x[1], reverse=True))

Dies druckt Lukes Rang und unsere Charaktere nach Rang sortiert:

 0.12100659993223405 ['OWEN', 'LUKE', 'MOTTI', 'DODONNA', 'GOLD LEADER', 'BIGGS', 'CHEWBACCA', 'LEIA', 'BERU', 'WEDGE', 'RED LEADER', 'RED TEN', 'OBI-WAN', 'DARTH VADER', 'CAMIE', 'TARKIN', 'HAN', 'R2-D2', 'C-3PO']

Owen ist der Charakter mit dem höchsten PageRank und übertrifft Luke, der den höchsten Abschluss hatte. Die Analyse: Obwohl Owen nicht der Charakter ist, der die meisten Szenen mit anderen Charakteren teilt, ist er ein Charakter, der Szenen mit vielen wichtigen Charakteren wie Luke selbst, R2-D2 und C-3PO teilt.

Im Gegensatz dazu ist C-3PO, der Charakter mit dem dritthöchsten Abschluss, derjenige mit dem niedrigsten PageRank. Obwohl C-3PO viele Verbindungen hat, sind viele von ihnen mit unwichtigen Charakteren.

Fazit: Die Verwendung mehrerer Metriken kann einen tieferen Einblick in die verschiedenen Eigenschaften der Knoten eines Diagramms geben.

Community-Erkennungsalgorithmen

Bei der Analyse eines Netzwerks kann es wichtig sein, Gemeinschaften zu trennen: Gruppen von Knoten, die stark miteinander verbunden sind, aber nur minimal mit Knoten außerhalb ihrer Gemeinschaft verbunden sind.

Dafür gibt es mehrere Algorithmen. Die meisten von ihnen finden sich in unüberwachten maschinellen Lernalgorithmen, weil sie den Knoten ein Label zuweisen, ohne dass sie vorher beschriftet werden müssen.

Eine der bekanntesten ist die Label-Propagation . Darin beginnt jeder Knoten mit einem eindeutigen Label in einer Gemeinschaft von Eins. Die Labels der Knoten werden iterativ entsprechend der Mehrheit der Labels der benachbarten Knoten aktualisiert.

Die Labels diffundieren durch das Netzwerk, bis alle Knoten ein Label mit den meisten ihrer Nachbarn teilen. Gruppen von Knoten, die eng miteinander verbunden sind, haben am Ende dieselbe Bezeichnung.

Mit der NetworkX-Bibliothek dauert die Ausführung dieses Algorithmus nur drei Zeilen Python:

 from networkx.algorithms.community.label_propagation import label_propagation_communities communities = label_propagation_communities(G_starWars) print([community for community in communities])

Die Ausgabe:

 [{'R2-D2', 'CAMIE', 'RED TEN', 'RED LEADER', 'OBI-WAN', 'DODONNA', 'LEIA', 'WEDGE', 'HAN', 'OWEN', 'CHEWBACCA', 'GOLD LEADER', 'LUKE', 'BIGGS', 'C-3PO', 'BERU'}, {'DARTH VADER', 'TARKIN', 'MOTTI'}]

In dieser Liste von Sets repräsentiert jedes Set eine Gemeinschaft. Leser, die mit dem Film vertraut sind, werden feststellen, dass es dem Algorithmus gelungen ist, die „Guten“ perfekt von den „Bösen“ zu trennen und die Charaktere sinnvoll zu unterscheiden, ohne ein echtes (Community-)Label oder Metadaten zu verwenden.

Intelligente Erkenntnisse mit Graph Data Science in Python

Wir haben gesehen, dass der Einstieg in Graph-Data-Science-Tools einfacher ist, als es sich anhört. Sobald wir Daten mithilfe der NetworkX-Bibliothek in Python als Diagramm darstellen, können einige kurze Codezeilen aufschlussreich sein. Wir können unseren Datensatz visualisieren, Knoteneigenschaften messen und vergleichen und Knoten sinnvoll über Community-Erkennungsalgorithmen gruppieren.

Die Fähigkeit, mit Python Schlussfolgerungen und Erkenntnisse aus einem Netzwerk zu extrahieren, ermöglicht es Entwicklern, sich in Tools und Methoden zu integrieren, die üblicherweise in Data-Science-Service-Pipelines zu finden sind. Von Suchmaschinen über Flugplanung bis hin zu Elektrotechnik lassen sich diese Methoden problemlos auf eine Vielzahl von Kontexten anwenden.

Empfohlene Lektüre zu Graph Data Science

Community-Erkennungsalgorithmen
Zhao Yang, René Algesheimer und Claudio Tessone. "Eine vergleichende Analyse von Community-Erkennungsalgorithmen in künstlichen Netzwerken." Wissenschaftliche Berichte, 6, Nr. 30750 (2016).

Graph Deep Learning
Thomas Kipp. „Graph Convolutional Networks.“ 30. September 2016.

Anwendungen der Graph Data Science
Albanese, Federico, Leandro Lombardi, Esteban Feuerstein und Pablo Balenzuela. „Vorhersage von wechselnden Personen mithilfe von Text Mining und Graph Machine Learning auf Twitter.“ (24. August 2020): arXiv:2008.10749 [cs.SI].

Cohen, Elior. „PyData Tel Aviv Meetup: Node2vec.“ Youtube. 22. November 2018. Video, 21:09. https://www.youtube.com/watch?v=828rZgV9t1g.