Ein Graph ist ein Konzept der Mathematik und ein Grundbegriff der mathematischen Graphentheorie. Zugleich werden Graphen intensiv in der Informatik genutzt, z.B. als abstrakte Datenstruktur (wie eine Liste oder ein Dictionary), mit der sich bestimmte Probleme besser bzw. überhaupt erst lösen lassen.
Die mathematische Definition eines Graphen lautet:
Ein Graph G ist ein Triple bestehend aus einem Set von Knoten V(G), einem Set von Kanten E(G), und einer Beziehung, die mit jeder Kante zwei Knoten verbindet, die deren Endpunkte genannt werden. Graphen werden visualisiert, indem man die Knoten als Punkte zeichnet und die Kanten als verbindende Linien. Wir reden hier nur über endliche Graphen, bei denen die Mengen V(G) und E(G) endlich sind. Die Endpunkte einer Kante können identisch sein (= derselbe Knoten), dann handelt es sich um eine Schleife (loop). Es gibt Graphen mit multiplen Kanten, d.h. zwei Kanten können dieselben Endpunkte haben.
Ein simpler Graph hat weder Schleifen noch multiple Kanten. Ein Multigraph dagegen weist sowohl Schleifen als auch multiple Kanten auf.
In einem Digraph oder auch gerichteten Graphen sind die Kanten gerichtet, können also nur in einer Richtung durchlaufen werden.
Ein einfacher ungerichteter Graph:
(Quelle: Wikipedia http://de.wikipedia.org/wiki/Graph_%28Graphentheorie%29)
Ein einfacher gerichteter Graph:
Ein ungerichteter Multigraph:
Ein gerichteter Multigraph:
In der Informatik sind Graphen wichtige Datenstrukturen geworden, die es erlaubten vernetzen Informationen leichter zu modellieren, sie zu analysieren und auch zu visualisieren. Entsprechend können wir zwischen drei großen Gruppen von Verfahren unterscheiden:
Wir verwenden in Python die Bibliothek networkx (pip install networkx).
Wie immer sind die Grundbausteine sehr einfach. Ein Graph oder Netzwerk besteht, wie gesagt, aus aus Knoten (edges) und Kanten (vertices). Im folgenden definieren wir einen einfachen Graphen, der 4 Knoten hat und 3 Kanten:
In [1]:
import networkx as nx
g = nx.Graph()
g.add_node(1)
g.add_node(2)
g.add_node(3)
g.add_node(4)
#oder schneller
g.add_nodes_from([1,2,3,4])
#Hinzufügen von Kanten
g.add_edge(1,2)
g.add_edge(1,3)
g.add_edge(1,4)
#oder schneller
g.add_edges_from([(1,2),(1,3),(1,4)])
Wir können uns die Informationen über einen Graphen schnell ausgeben lassen:
In [2]:
nr_nodes = len(g.nodes())
print("Graph hat " + str(nr_nodes) + " Knoten.")
nr_edges = len(g.edges())
print("Graph hat " + str(nr_edges) + " Kanten.")
Oft ist es noch besser, den Graphen zu visualisieren:
In [3]:
import matplotlib.pyplot as plt
nx.draw(g)
plt.show()
Wenn wir etwas mehr Informationen als nur die Grundstruktur des Graphen sehen wollen, verwenden wir die Methode draw_networkx. Hier werden nun etwa die Labels der Knoten angezeigt.
In [4]:
nx.draw_networkx(g)
plt.show()
Durch die labels können wir die - im Prinzip ganz abstrakte Datenstruktur - für ganz beliebige Informationen verwenden, z.B. Städte und deren Zugverbindung, Namen in Texten und deren gemeinsames Vorkommen, Briefpartner usw.
In [5]:
g = nx.Graph()
g.add_nodes_from(["Goethe", "Schiller", "Humboldt", "Zelter"])
g.add_edges_from([("Goethe","Schiller"),("Goethe","Humboldt"),("Goethe","Zelter")])
nx.draw_networkx(g)
plt.show()
Wir können zumdem die Kanten verwenden, um Informationen über das Netzwerk abzuspeichern. Das macht man, indem man den Kanten ein Gewicht gibt. Wenn die Knoten etwa Namen in einem Briefnetzwerk repräsentieren, können wir die Anzahl der Briefe an den Kanten notieren. Die Visualisierung zeigt die größere Menge der Briefe als größere Nähe an:
In [6]:
g = nx.Graph()
g.add_nodes_from(["Goethe", "Schiller", "Humboldt", "Zelter"])
g.add_edges_from([("Goethe","Schiller", dict(weight=12)),("Goethe","Humboldt", dict(weight=1)),("Goethe","Zelter", dict(weight=3))])
#auch hier gibt es eine convenience function, die die Eingabe vereinfacht:
g.add_weighted_edges_from([("Goethe","Schiller",12),("Goethe","Humboldt", 1),("Goethe","Zelter", 3)])
nx.draw_networkx(g)
plt.show()
Sie können Graphen auch verändern, indem Sie Knoten und Kanten wieder entfernen:
In [7]:
g.remove_edge("Goethe","Zelter")
g.remove_node("Zelter")
nx.draw_networkx(g)
plt.show()
Erzeugen Sie ein Netzwerk, das folgende Städte enthält: München, Hamburg, Frankfurt, Berlin, Paris, London, Rom. Verbinden Sie alle Hauptstädte untereinander durch Kanten, während die deutschen Städte jeweils nur mit Berlin verbunden sind. Lassen Sie sich den Graphen anzeigen, aber auch die Anzahl der Knoten und Kanten ausgeben. Ergänzen Sie noch den Knoten Wien und die entsprechenden Kanten.
In gerichteten Graphen können, wie gesagt, die Kanten nur in eine Richtung durchlaufen werden. Diese Richtung wird in networkx einfach durch die Reihenfolge der Endpunkte angegeben:
In [10]:
import matplotlib.pyplot as plt
dg=nx.DiGraph()
dg.add_edge(1,2)
dg.add_edge(2,3)
dg.add_edge(3,1)
nx.draw_networkx(dg)
plt.show()
In Multigraphen können zwei Knoten durch mehrere Kanten verbunden sein:
In [16]:
mg = nx.MultiGraph()
#ab hier werden die gleichen Methoden verwendet:
mg.add_edge(1,2)
mg.add_edge(1,2)
mg.add_edge(2,3)
mg.add_edge(3,1)
nx.draw_networkx(mg)
plt.show()
1) Erstellen Sie aus der angehängten Datei, die die Ergebnisse einer named entity recognition des Romans Wahlverwandtschaften enthält, ein Netzwerk der Figuren, die im gleichen Absatz vorkommen. Die Figurennamen sind die Knoten; gemeinsam in einem Absatz vorkommende Namen werden durch eine Kante verbunden. Eine Absatzgrenze ist durch die Zeichenkombination $# markiert. Eine Figurenreferenz ist durch das angehängte Unterstrich+PER ( _ PER) markiert.
2) Verwenden Sie die Häufigkeit, mit der die Figuren gemeinsam in einem Absatz vorkommen als Gewicht der Kanten
Die Graphentheorie kennt eine große Menge von Perspektiven, unter denen Graphen, Knoten und Kanten beschrieben werden. Im folgenden führen wir einige sehr grundlegende ein:
Grad (degree) - unter dem "degree" eines Knoten u versteht man in einem ungerichteten Graphen die Anzahl der Kanten, die u als Endpunkt haben. In gerichteten Graphen kann man zwischen ausgehenden und eingehenden Kanten unterscheiden und entsprechend auch zwischen outgoing degree und ingoing degree. Die folgende Grafik zeigt einen Knoten A, der den Grad 3 hat.
Wir können uns stets ausgeben lassen, mit welchen anderen Knoten ein bestimmter Knoten verbunden ist:
In [60]:
import networkx as nx
g = nx.Graph()
g.add_edges_from([("A","B"),("A","C"),("A","D"),("D","E")])
g.neighbors("A")
Out[60]:
oder einfach auch (einschließlich evtl. Gewichte):
In [11]:
g["A"]
Out[11]:
Ein Weg (walk) ist die Verbindung einer Sequenz von Knoten durch ein Reihe von Kanten. (Wenn der Anfangsknoten zugleich der Endknoten ist, spricht man von einem closed walk. Sind die Kanten eines Wegs distinkt, d.h. keine Kante wird wiederholt verwendet, spricht man von einem trail. Sind außerdem die Knoten des Wegs distinkt, spricht man von einem Pfad (path). Ein geschlossener Pfad, also ein Pfad, dessen Anfangspunkt identisch mit dem Endpunkt ist, nennt man einen Zyklus, bzw. Kreis (cycle) (Kreis).
Die zwei Knoten a,b eines Graphen G sind verbunden, wenn es einen walk gibt, der a und b verbindet. Für jeden einzelnen Knoten kann ich mit neighbors() prüfen, ob er überhaupt verbunden ist. Außerdem kann ich prüfen, ob der Graph insgesamt verbunden ist:
In [61]:
nx.is_connected(g)
Out[61]:
In [62]:
import matplotlib.pyplot as plt
g.remove_node("A")
nx.draw_networkx(g)
plt.show()
In [63]:
nx.is_connected(g)
Out[63]:
Wenn zwei Knoten verbunden sind, dann gibt es mindestens einen Pfad, der den kürzesten Weg zwischen den Knoten darstellt; diesen Pad nennt man die Distanz, manchmal auch geodesische Distanz oder auch einfach den kürzesten Pfad. Die folgende Grafik zeigt den kürzesten Pfad von B nach E (über A und D):
In [68]:
#einen Graphen erstellen
import networkx as nx
g = nx.Graph()
g.add_edges_from([("A","B"),("A","C"),("A","D"),("C","D"),("D","E")])
#suchen des kürzesten Pfads von B nach E:
nx.shortest_path(g, "B","E")
Out[68]:
Die Suche nach dem kürzesten Pfad stellt übrigens ein interessantes Problem da. Schauen Sie sich mal den bekannten Algorithmus des niederländischen Informatikers Dijkstra in Wikipedia an.
Da Graphen für sehr unterschiedliche Zwecke verwendet werden, gibt es auch ganz unterschiedliche Auswertungs- und Analyseverfahren. Wir werden uns hier eine Gruppe grundlegender Maße anschauen: die Zentralitätsmaße (Weitere finden Sie in der sehr umfassenden networkx-Dokumentation). Zentralitätsmaße beschreiben einen Knoten unter der Perspektive, ob er eine zentrale Rolle in dem Netzwerk einnimmt. "Zentrale Rolle" ist nicht ganz einfach zu formalisieren, daher gibt es drei verschiedene Maße/Perspektiven:
degree centrality - Intuition: Ein wichtiger Knoten hat zahlreiche Verbindungen zu anderen Knoten.
Berechnung: Anzahl der Verbindungen, die von einem Knoten ausgehen geteilt durch die Anzahl der Kanten im Netzwerk:
degree centrality CD eines Knoten u:
$$
C_D(u) = d_u
$$
wobei da der degree des Knoten a ist.
Da der Rohwert oft nicht sehr nützlich ist, wird er normalisiert, indem er durch die Anzahl der möglichen Verbindungen, die ein Knoten haben kann, geteilt wird. Die Anzahl der möglichen Verbindungen eines Knotens in einem Netzwerk ist: n-1, wobei n die Anzahl aller Knoten in dem Netzwerk ist (ist irgendwie logisch...). Also wird degree centrality für einen Knoten so berechnet:
$$
C_D(u) = \frac {d_u}{(n-1)}
$$
In [3]:
#hier verwenden wir die Funktion von networkx
nx.degree_centrality(g)
Out[3]:
A und D sind mit diesem Maß die wichtigsten Knoten. Wenn ein Knoten den degree centrality - Wert 1.0 hat, weiß man, dass es sich um den Mittelpunkt eines sternförmigen Netzwerks handeln muss.
closeness centrality Intuition: Ein wichtiger Knoten hat einen kurzen Weg zu den anderen Knoten eines Netzwerks.
Das Maß gibt wieder, wie zentral ein Knoten ist, indem die jeweils kürzeste Distanz zu allen anderen Knoten addiert wird:
$$C_s(u) = \sum_{v=1}^{n-1} \delta(u,v) $$
Wobei gilt:
δ ist der kürzeste Pfad zwischen u und v
u ist der analysierte Knoten
v ist ein beliebiger Knoten des Netzwerks
n ist die Anzahl aller Knoten im Netzwerk
auch hier normalisiert man:
$$
C_s(u) = \frac {n-1}{\sum_{v=1}^{n-1} \delta(u,v) }
$$
In [4]:
#Funktion in networkx:
nx.closeness_centrality(g)
Out[4]:
betweenness centrality Intuition: Ein Knoten ist wichtig/zentral, wenn er auf vielen Wegen zwischen anderen Knoten liegt.
Zur Berechnung werden also einmal alle Pfade zwischen zwei Knoten s und t berechnet und dann der Anteil dieser Pfade, auf denen der Knoten u liegt
$$ C_B(u) = \sum_{s,t \in V} \frac {\sigma (s, t|v)}{\sigma (s,t)} $$
wobei gilt:
V ist das Set der Knoten
σ(s,t) ist die Anzahl der kürzesten Pfade zwischen s und t
σ(s,t|v) ist die Anzahl der kürzesten Pfade zwischen s und t, die über v laufen.
In [5]:
nx.betweenness_centrality(g)
Out[5]:
1) Die Bibliothek networkx kennt auch eine große Menge von Graph-Generatoren, mit denen man Graphen erzeugen kann. Verwenden Sie die Funktionen a) hypercube_graph(n) [mit n=3] und b) krackhardt_kite_graph(), um zwei Netzwerke zu erzeugen. Visualisieren Sie das Ergebnis und berechnen Sie einen kürzesten Pfad a) zwischen (0,0,0) und (1,1,1) sowie b) zwischen 1 und 9 an. Überlegen Sie sich, wie für die beiden Graphen die Ergebnisse der drei Zentralitätsmaße aussehen müßten. Berechnen Sie dann für die beiden Graphen jeweils die 3 Zentralitätsmaße (sortieren Sie nach Größe des Maßes).
2) Berechnen Sie die drei Zentralitätsmaße für das Figurennetzwerk der Hausaufgabe und zeigen Sie die jeweils wichtigsten 10 Figuren und ihre Werte an.
In [30]:
import networkx as nx
g = nx.Graph()
g.add_edges_from([("A","B"),("A","C"),("A","D"),("C","D"),("D","E"),("E","F")])
nx.draw_networkx(g)
plt.show()
In [27]:
print(g.nodes())
g.adjacency_list()
Out[27]:
Mit read_adjlist(file) können Sie die Liste wieder einlesen. Die Syntax ist in allen folgenden Befehlen gleich; ersetzen Sie einfach 'read' durch 'write', um die Funktion zum Einlesen der Daten zu erhalten.
In [36]:
nx.write_adjlist(g, "file.txt")
x = nx.read_adjlist("file.txt")
print(x.edges())
Es gibt eine ganze Reihe von unterschiedlichen Formaten, z.B. read_edgelist (+ read_weighted_edgelist),
In [38]:
nx.write_edgelist(g, "file2.txt")
In [40]:
with open("file2.txt", encoding="utf8") as fin:
for l in fin:
print(l, end="")
Auch für komplexe Daten und Strukturen gut geeignet ist das Format GEFX (Graph Exchange XML Format), das z.B. auch von Gephi unterstützt wird.
In [45]:
g = nx.Graph()
g.add_weighted_edges_from([("Goethe","Schiller",12),("Goethe","Humboldt", 1),("Goethe","Zelter", 3)])
nx.write_gexf(g, "file3.txt")
with open("file3.txt", encoding="utf8") as fin:
print(fin.read(-1))
networkx ist keine Bibliothek zum Visualisieren von Graphen, vielmehr verwendet sie matplotlib zur Darstellung und bietet einige Funktionen, um die Objekte, die dargestellt werden sollen, anzusprechen. Wir haben ja schon die ganze Zeit mit den generischen Funktionen nx.draw() und nx.draw_networkx() gearbeitet.
In [1]:
import matplotlib.pyplot as plt
import networkx as nx
g = nx.krackhardt_kite_graph()
#plotting starts here
nx.draw_networkx(g)
plt.show()
Es gibt eine ganze Reihe von verschiedenen Layout-Algorithmen für Graphen. Voreingestellt ist das spring-layout. Aber Sie können auch andere verwenden:
In [3]:
#spectral layout
pos = nx.spectral_layout(g)
nx.draw_networkx(g)
plt.show()
In [4]:
#shell layout
pos = nx.shell_layout(g)
nx.draw_networkx(g)
plt.show()
In [5]:
#pos enthält ein dictionary mit den Positionen der Knoten und damit implizit auch der Kanten.
pos
Out[5]:
Wir können jeden einzelnen Aspekt eines Graphen, also jeden Knoten, jede Kante gezielt manipulieren und Label, Farbe, Größe usw. festlegen. Dabei müssen wir eines beachten: Am Anfang der Layout-Sequenz müssen wir einmal das Layout berechnen lassen und dann diese Information immer als Parameter an die folgenden Grafikoperationen übergeben.
Beginnen wir damit, dass wir den Knoten 9 blau einfärben. Hier ist die Signatur der entsprechenden Funktion:
draw_networkx_nodes(G, pos, nodelist=None, node_size=300, node_color=’r’, node_shape=’o’, alpha=
1.0, cmap=None, vmin=None, vmax=None, ax=None, linewidths=None, label=
None, **kwds)
Wir müssen also den Parameter node_color setzen
In [6]:
nx.draw_networkx_nodes(g, pos, [9], node_color="b")
plt.show()
Ok. Aber hier fehlt noch der Rest des Graphen. Den können wir einfach mit dem generischen Befehl malen:
In [7]:
#jetzt müssen wir auch hier die Positionen übergeben, sonst werden diese noch einmal berechnet
pos = nx.spring_layout(g)
nx.draw_networkx(g, pos)
#Sie müssen die Reihenfolge beachten. Die Zeichenbefehle werden nacheinander ausgeführt.
nx.draw_networkx_nodes(g, pos, [9], node_color="b")
plt.show()
Nun bearbeiten wir die Kanten. Hier die Dokumentation des Befehls:
draw_networkx_edges(G, pos, edgelist=None, width=1.0, edge_color=’k’, style=’solid’, alpha=None,
edge_cmap=None, edge_vmin=None, edge_vmax=None, ax=None, arrows=
True, label=None, **kwds)
In [8]:
nx.draw_networkx(g, pos)
nx.draw_networkx_edges(g, pos, [(7,8),(8,9)], width=3, edge_color="g", style="dashed")
plt.show()
Man kann diese Befehle beliebig kombinieren:
In [9]:
nx.draw_networkx(g, pos, node_color="yellow")
nx.draw_networkx_nodes(g, pos, [9], node_color="orange")
nx.draw_networkx_nodes(g, pos, [8], node_color="b")
nx.draw_networkx_edges(g, pos, [(8,9)], width=3, edge_color="g", style="dashed")
nx.draw_networkx_edges(g, pos, [(7,8)], width=3, edge_color="b")
plt.show()
Außerdem gibt es noch eine Funktion, um die Labels der Knoten festzulegen:
draw_networkx_labels(G, pos, labels=None, font_size=12, font_color=’k’, font_family=’sans-serif’,
font_weight=’normal’, alpha=1.0, ax=None, **kwds)
In [73]:
#wenn Sie alle Labels setzen wollen, können Sie das auch direkt in der Funktion draw_networkx machen
nx.draw_networkx(g, pos, node_color="yellow", with_labels=False)
labels = {0:0,1:1,2:2,3:"Center",4:4,5:5,6:6,7:7,8:8,9:"Outsider",}
nx.draw_networkx_labels(g, pos, labels=labels, font_size=12, font_color='b')
plt.show()
Und zuletzt die Funktion, die es Ihnen erlaubt, die Labels an den Kanten festzulegen:
draw_networkx_edge_labels(G, pos, edge_labels=None, label_pos=0.5, font_size=10,
font_color=’k’, font_family=’sans-serif’, font_weight=’normal’,
alpha=1.0, bbox=None, ax=None, rotate=True, **kwds)
In [74]:
nx.draw_networkx(g, pos, node_color="yellow")
nx.draw_networkx_nodes(g, pos, [9], node_color="blue")
nx.draw_networkx_edges(g, pos, [(8,9)], width=3, edge_color="b", style="dashed")x.draw_networkx_edge_labels(g, pos, edge_labels={(8,9):"outsider"})
plt.show()
Graphen bieten sich offensichtlich als Datenstruktur an, wenn es darum geht vernetzte Informationseinheiten abzubilden. Man muss ich dann entscheiden, welcher Aspekt als Knoten, welcher als Kante abgebildet wird und was als Gewicht modelliert wird. Tatsächlich kann man in networkx alles was hashable ist als Knoten nehmen, da die zugrundeliegende Informationsstruktur ein dictionary ist.
In [75]:
class Author ():
def __init__(self, name, yob, yod, works):
self.name = name
self.yob = yob
self.yod = yod
self.works = works
a = Author("Goethe", 1749, 1832, ["Werther", "Faust"])
b = Author("Schiller", 1759, 1805, ["Die Räuber", "Wallenstein"])
c = Author("Lessing", 1729, 1781, ["Minna von Barnhelm", "Nathan der Weise"])
g = nx.Graph()
g.add_edges_from([(a,b),(a,c),(b,c)])
nx.draw_networkx(g)
plt.show()
Außerdem kann man noch beliebige Attribute an Knoten und Kanten hängen und so auch recht komplexe Informationen ablegen.
Erstellen Sie einen krackhardt_kite_graph. Der Graph beschreibt ein soziales Netzwerk mit 10 Akteuren. Das traditionelle Labeling ist: : Andre=1, Beverley=2, Carol=3, Diane=4, Ed=5, Fernando=6, Garth=7,Heather=8, Ike=9, Jane=10. Labeln Sie die Knoten entsprechend. Berechnen Sie dann den kürzesten Pfad von Carol zu Ike und färben Sie den Pfad gelb ein. Suchen Sie dabei nach einer Lösung, die auch für sehr lange Pfade funktionieren würde.
1) Implementieren Sie den Algorithmus für degree centrality. Verwenden Sie die gleiche Signatur wie networkX für die Funktion.
2) Sie bekommen zwei Dateien mit NER für den Roman Effi Briest von Fontane. Erstellen Sie das Netzwerk nach dem gleichen Muster wie in der letzten Hausaufgabe. Filtern Sie alle Knoten heraus, die weniger als Grad 5 haben. Berechnen Sie die drei Zentralitätsmaße und berechnen Sie den kürzesten Pfad zwischen der wichtigsten Figur (oder eine der wichtigsten) und der unwichtigsten (oder eine der unwichtigsten). Visualisieren Sie das Ergebnis für alle drei Maße. Markieren Sie den kürzesten Weg in roter Farbe und heben Sie die Endpunkte des Pfads blau hervor.
Bernd Klein: Graphs in Python - Networkx.
In [ ]: