Python_2_4.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Grundbegriffe des Arbeitens mit Graphen"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Einige Grundbegriffe der Graphentheorie"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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. <br/>\n",
    "Die mathematische Definition eines Graphen lautet: <br/>\n",
    "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 <b>endliche Graphen</b>, 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 <b>multiplen Kanten</b>, d.h. zwei Kanten können dieselben Endpunkte haben. <br/>\n",
    "Ein <b>simpler Graph</b> hat weder Schleifen noch multiple Kanten. Ein <b>Multigraph</b> dagegen weist sowohl Schleifen als auch multiple Kanten auf.<br/>\n",
    "In einem  <b>Digraph</b> oder auch <b>gerichteten Graphen</b> sind die Kanten gerichtet, können also nur in einer Richtung durchlaufen werden. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ein einfacher ungerichteter Graph:\n",
    "<img src=\"files/images/graphen ungerichtet.png\">  \n",
    "(Quelle: Wikipedia http://de.wikipedia.org/wiki/Graph_%28Graphentheorie%29)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ein einfacher gerichteter Graph:\n",
    "<img src=\"files/images/graphen gerichtet.png\">     "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ein ungerichteter Multigraph:\n",
    "<img src=\"files/images/graphen multi ungerichtet.png\"> "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ein gerichteter Multigraph:\n",
    "<img src=\"files/images/graphen multi gerichtet.png\"  > "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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: \n",
    "<ol><li>Aufbau und Veränderung von Graphen</li>\n",
    "<li>Analyse von Graphen </li>\n",
    "<li>Visualisierung von Graphen</li>\n",
    "</ol>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Aufbau von Graphen"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir verwenden in Python die Bibliothek networkx (pip install networkx).<br/> \n",
    "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:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "g = nx.Graph()\n",
    "g.add_node(1)\n",
    "g.add_node(2)\n",
    "g.add_node(3)\n",
    "g.add_node(4)\n",
    "\n",
    "#oder schneller\n",
    "g.add_nodes_from([1,2,3,4])\n",
    "\n",
    "#Hinzufügen von Kanten\n",
    "g.add_edge(1,2)\n",
    "g.add_edge(1,3)\n",
    "g.add_edge(1,4)\n",
    "\n",
    "#oder schneller\n",
    "g.add_edges_from([(1,2),(1,3),(1,4)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir können uns die Informationen über einen Graphen schnell ausgeben lassen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Graph hat 4 Knoten.\n",
      "Graph hat 3 Kanten.\n"
     ]
    }
   ],
   "source": [
    "nr_nodes = len(g.nodes())\n",
    "print(\"Graph hat \" + str(nr_nodes) + \" Knoten.\")\n",
    "nr_edges = len(g.edges())\n",
    "print(\"Graph hat \" + str(nr_edges) + \" Kanten.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Oft ist es noch besser, den Graphen zu visualisieren:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "nx.draw(g)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "nx.draw_networkx(g)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "g = nx.Graph()\n",
    "g.add_nodes_from([\"Goethe\", \"Schiller\", \"Humboldt\", \"Zelter\"])\n",
    "g.add_edges_from([(\"Goethe\",\"Schiller\"),(\"Goethe\",\"Humboldt\"),(\"Goethe\",\"Zelter\")])\n",
    "nx.draw_networkx(g)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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:   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "g = nx.Graph()\n",
    "g.add_nodes_from([\"Goethe\", \"Schiller\", \"Humboldt\", \"Zelter\"])\n",
    "g.add_edges_from([(\"Goethe\",\"Schiller\", dict(weight=12)),(\"Goethe\",\"Humboldt\", dict(weight=1)),(\"Goethe\",\"Zelter\", dict(weight=3))])\n",
    "#auch hier gibt es eine convenience function, die die Eingabe vereinfacht:\n",
    "g.add_weighted_edges_from([(\"Goethe\",\"Schiller\",12),(\"Goethe\",\"Humboldt\", 1),(\"Goethe\",\"Zelter\", 3)])\n",
    "nx.draw_networkx(g)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sie können Graphen auch verändern, indem Sie Knoten und Kanten wieder entfernen:\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "g.remove_edge(\"Goethe\",\"Zelter\")\n",
    "g.remove_node(\"Zelter\")\n",
    "\n",
    "nx.draw_networkx(g)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Aufgabe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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.\n",
    "Ergänzen Sie noch den Knoten Wien und die entsprechenden Kanten."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Gerichtete Graphen, Multigraphen"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "dg=nx.DiGraph()\n",
    "dg.add_edge(1,2)\n",
    "dg.add_edge(2,3)\n",
    "dg.add_edge(3,1)\n",
    "nx.draw_networkx(dg)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In Multigraphen können zwei Knoten durch mehrere Kanten verbunden sein:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "mg = nx.MultiGraph()\n",
    "#ab hier werden die gleichen Methoden verwendet: \n",
    "mg.add_edge(1,2)\n",
    "mg.add_edge(1,2)\n",
    "\n",
    "mg.add_edge(2,3)\n",
    "mg.add_edge(3,1)\n",
    "nx.draw_networkx(mg)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Aufgabe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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. <br/>\n",
    "2) Verwenden Sie die Häufigkeit, mit der die Figuren gemeinsam in einem Absatz vorkommen als Gewicht der Kanten "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Eigenschaften von Graphen, Kanten und Knoten"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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: <br/>\n",
    "<p><b>Grad (degree)</b> - 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 <b>outgoing degree</b> und <b>ingoing degree</b>. Die folgende Grafik zeigt einen Knoten A, der den Grad 3 hat.\n",
    "<img src=\"files/images/degree.png\" width=50% height=50%>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir können uns  stets ausgeben lassen, mit welchen anderen Knoten ein bestimmter Knoten verbunden ist: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['C', 'B', 'D']"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import networkx as nx\n",
    "g = nx.Graph()\n",
    "g.add_edges_from([(\"A\",\"B\"),(\"A\",\"C\"),(\"A\",\"D\"),(\"D\",\"E\")])\n",
    "g.neighbors(\"A\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "oder einfach auch (einschließlich evtl. Gewichte):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'C': {}, 'B': {}, 'D': {}}"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g[\"A\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p>Ein <b>Weg (walk)</b> ist die Verbindung einer Sequenz von Knoten durch ein Reihe von Kanten. (Wenn der Anfangsknoten zugleich der Endknoten ist, spricht man von einem <b>closed walk</b>. Sind die Kanten eines Wegs distinkt, d.h. keine Kante wird wiederholt verwendet, spricht man von einem <b>trail</b>. Sind außerdem die Knoten des Wegs distinkt, spricht man von einem <b>Pfad (path)</b>. Ein geschlossener Pfad, also ein Pfad, dessen Anfangspunkt identisch mit dem Endpunkt ist, nennt man einen <b>Zyklus, bzw. Kreis (cycle)</b> (Kreis). </p>\n",
    "<p>Die zwei Knoten a,b eines Graphen G sind <b>verbunden</b>, 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:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nx.is_connected(g)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "g.remove_node(\"A\")\n",
    "nx.draw_networkx(g)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nx.is_connected(g)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p>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 <b>Distanz</b>, manchmal auch <b>geodesische Distanz</b> oder auch einfach den <b>kürzesten Pfad</b>. Die folgende Grafik zeigt den kürzesten Pfad von B nach E (über A und D): </p>   \n",
    "<img src=\"files/images/shortest_path.png\" width=50% height=50%>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['B', 'A', 'D', 'E']"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#einen Graphen erstellen\n",
    "import networkx as nx\n",
    "g = nx.Graph()\n",
    "g.add_edges_from([(\"A\",\"B\"),(\"A\",\"C\"),(\"A\",\"D\"),(\"C\",\"D\"),(\"D\",\"E\")])\n",
    "\n",
    "#suchen des kürzesten Pfads von B nach E:\n",
    "nx.shortest_path(g, \"B\",\"E\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die Suche nach dem kürzesten Pfad stellt übrigens ein interessantes Problem da. Schauen Sie sich mal den bekannten <a href=\"http://de.wikipedia.org/wiki/Dijkstra-Algorithmus\">Algorithmus</a> des niederländischen Informatikers Dijkstra in Wikipedia an.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Analyse von Graphen: Zentralitätsmaße"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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:<br/>\n",
    "<ul>\n",
    "<li>degree centrality</li>\n",
    "<li>in_degree_centrality</li>\n",
    "<li>out_degree_centrality</li>\n",
    "</ul>\n",
    "<p><b>degree centrality</b> - Intuition: Ein wichtiger Knoten hat zahlreiche Verbindungen zu anderen Knoten. <br/>\n",
    "Berechnung: Anzahl der Verbindungen, die von einem Knoten ausgehen geteilt durch die Anzahl der Kanten im  Netzwerk:<br/>\n",
    "degree centrality C<sub>D</sub> eines Knoten u:\n",
    "$$\n",
    "C_D(u) = d_u\n",
    "$$\n",
    "wobei d<sub>a</sub> der degree des Knoten a ist.<br/>\n",
    "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: <br/>\n",
    "$$\n",
    "C_D(u) = \\frac {d_u}{(n-1)}\n",
    "$$\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'B': 0.25, 'A': 0.75, 'D': 0.75, 'C': 0.5, 'E': 0.25}"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#hier verwenden wir die Funktion von networkx \n",
    "nx.degree_centrality(g)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<b>closeness centrality</b> Intuition: Ein wichtiger Knoten hat einen kurzen Weg zu den anderen Knoten eines Netzwerks. <br/> Das Maß gibt wieder, wie zentral ein Knoten ist, indem die jeweils kürzeste Distanz zu allen anderen Knoten addiert wird:<br/>\n",
    "$$C_s(u) = \\sum_{v=1}^{n-1} \\delta(u,v)  $$\n",
    "Wobei gilt: <br/>\n",
    "&delta; ist der kürzeste Pfad zwischen u und v<br/>\n",
    "u ist der analysierte Knoten<br/>\n",
    "v ist ein beliebiger Knoten des Netzwerks<br/>\n",
    "n ist die Anzahl aller Knoten im Netzwerk<br/>\n",
    "auch hier normalisiert man:\n",
    "$$\n",
    "C_s(u) = \\frac {n-1}{\\sum_{v=1}^{n-1} \\delta(u,v) }\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'B': 0.5, 'A': 0.8, 'D': 0.8, 'C': 0.6666666666666666, 'E': 0.5}"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Funktion in networkx:\n",
    "nx.closeness_centrality(g)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<b>betweenness centrality</b> Intuition: Ein Knoten ist wichtig/zentral, wenn er auf vielen Wegen zwischen anderen Knoten liegt.  <br/>\n",
    "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  <br/>\n",
    "$$ C_B(u) = \\sum_{s,t \\in V} \\frac {\\sigma (s, t|v)}{\\sigma (s,t)} $$\n",
    "wobei gilt:<br/> \n",
    "V ist das Set der Knoten<br/>\n",
    "&sigma;(s,t) ist die Anzahl der kürzesten Pfade zwischen s und t<br/>\n",
    "&sigma;(s,t|v) ist die Anzahl der kürzesten Pfade zwischen s und t, die über v laufen.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'B': 0.0, 'A': 0.5, 'D': 0.5, 'C': 0.0, 'E': 0.0}"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nx.betweenness_centrality(g)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Aufgabe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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).   \n",
    "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."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Lesen und Schreiben von Graphen"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### adjacency-Listen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "g = nx.Graph()\n",
    "g.add_edges_from([(\"A\",\"B\"),(\"A\",\"C\"),(\"A\",\"D\"),(\"C\",\"D\"),(\"D\",\"E\"),(\"E\",\"F\")])\n",
    "nx.draw_networkx(g)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['D', 'C', 'B', 'A', 'E']\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[['C', 'A', 'E'], ['D', 'A'], ['A'], ['C', 'B', 'D'], ['D']]"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print(g.nodes())\n",
    "g.adjacency_list()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('C', 'D'), ('C', 'A'), ('D', 'A'), ('D', 'E'), ('E', 'F'), ('B', 'A')]\n"
     ]
    }
   ],
   "source": [
    "nx.write_adjlist(g, \"file.txt\")\n",
    "x = nx.read_adjlist(\"file.txt\")\n",
    "print(x.edges())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Es gibt eine ganze Reihe von unterschiedlichen Formaten, z.B. read_edgelist (+ read_weighted_edgelist), "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "nx.write_edgelist(g, \"file2.txt\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "C D {}\n",
      "C A {}\n",
      "D A {}\n",
      "D E {}\n",
      "F E {}\n",
      "B A {}\n"
     ]
    }
   ],
   "source": [
    "with open(\"file2.txt\", encoding=\"utf8\") as fin:\n",
    "    for l in fin:\n",
    "        print(l, end=\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<gexf version=\"1.1\" xmlns=\"http://www.gexf.net/1.1draft\" xmlns:viz=\"http://www.gexf.net/1.1draft/viz\" xmlns:xsi=\"http://www.w3.org/2001/XMLSchema-instance\" xsi:schemaLocation=\"http://www.w3.org/2001/XMLSchema-instance\">\n",
      "  <graph defaultedgetype=\"undirected\" mode=\"static\">\n",
      "    <nodes>\n",
      "      <node id=\"Zelter\" label=\"Zelter\" />\n",
      "      <node id=\"Humboldt\" label=\"Humboldt\" />\n",
      "      <node id=\"Goethe\" label=\"Goethe\" />\n",
      "      <node id=\"Schiller\" label=\"Schiller\" />\n",
      "    </nodes>\n",
      "    <edges>\n",
      "      <edge id=\"0\" source=\"Zelter\" target=\"Goethe\" weight=\"3\" />\n",
      "      <edge id=\"1\" source=\"Humboldt\" target=\"Goethe\" weight=\"1\" />\n",
      "      <edge id=\"2\" source=\"Goethe\" target=\"Schiller\" weight=\"12\" />\n",
      "    </edges>\n",
      "  </graph>\n",
      "</gexf>\n",
      "\n"
     ]
    }
   ],
   "source": [
    "g = nx.Graph()\n",
    "g.add_weighted_edges_from([(\"Goethe\",\"Schiller\",12),(\"Goethe\",\"Humboldt\", 1),(\"Goethe\",\"Zelter\", 3)])\n",
    "nx.write_gexf(g, \"file3.txt\")\n",
    "with open(\"file3.txt\", encoding=\"utf8\") as fin:\n",
    "    print(fin.read(-1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Das Visualisieren von Graphen"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import networkx as nx\n",
    "g = nx.krackhardt_kite_graph()\n",
    "#plotting starts here\n",
    "nx.draw_networkx(g)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Es gibt eine ganze Reihe von verschiedenen Layout-Algorithmen für Graphen. Voreingestellt ist das spring-layout. Aber Sie können auch andere verwenden:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#spectral layout\n",
    "pos = nx.spectral_layout(g)\n",
    "nx.draw_networkx(g)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#shell layout\n",
    "pos = nx.shell_layout(g)\n",
    "nx.draw_networkx(g)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0: array([ 1.,  0.], dtype=float32),\n",
       " 1: array([ 0.809017  ,  0.58778524], dtype=float32),\n",
       " 2: array([ 0.30901697,  0.95105654], dtype=float32),\n",
       " 3: array([-0.30901703,  0.95105648], dtype=float32),\n",
       " 4: array([-0.80901706,  0.58778518], dtype=float32),\n",
       " 5: array([ -1.00000000e+00,  -8.74227766e-08], dtype=float32),\n",
       " 6: array([-0.80901694, -0.58778536], dtype=float32),\n",
       " 7: array([-0.30901709, -0.95105648], dtype=float32),\n",
       " 8: array([ 0.30901712, -0.95105648], dtype=float32),\n",
       " 9: array([ 0.80901724, -0.58778495], dtype=float32)}"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#pos enthält ein dictionary mit den Positionen der Knoten und damit implizit auch der Kanten.\n",
    "pos"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Beginnen wir damit, dass wir den Knoten 9 blau einfärben. Hier ist die Signatur der entsprechenden Funktion:<br/>\n",
    "draw_networkx_nodes(G, pos, nodelist=None, node_size=300, node_color=’r’, node_shape=’o’, alpha=\n",
    "1.0, cmap=None, vmin=None, vmax=None, ax=None, linewidths=None, label=\n",
    "None, **kwds)\n",
    "<br/>Wir müssen also den Parameter node_color setzen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "nx.draw_networkx_nodes(g, pos, [9], node_color=\"b\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ok. Aber hier fehlt noch der Rest des Graphen. Den können wir einfach mit dem generischen Befehl malen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#jetzt müssen wir auch hier die Positionen übergeben, sonst werden diese noch einmal berechnet\n",
    "pos = nx.spring_layout(g)\n",
    "nx.draw_networkx(g, pos)\n",
    "#Sie müssen die Reihenfolge beachten. Die Zeichenbefehle werden nacheinander ausgeführt.\n",
    "nx.draw_networkx_nodes(g, pos, [9], node_color=\"b\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nun bearbeiten wir die Kanten. Hier die Dokumentation des Befehls: <br/>\n",
    "draw_networkx_edges(G, pos, edgelist=None, width=1.0, edge_color=’k’, style=’solid’, alpha=None,\n",
    "edge_cmap=None, edge_vmin=None, edge_vmax=None, ax=None, arrows=\n",
    "True, label=None, **kwds)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "nx.draw_networkx(g, pos)\n",
    "nx.draw_networkx_edges(g, pos, [(7,8),(8,9)], width=3, edge_color=\"g\", style=\"dashed\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Man kann diese Befehle beliebig kombinieren:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "nx.draw_networkx(g, pos, node_color=\"yellow\")\n",
    "nx.draw_networkx_nodes(g, pos, [9], node_color=\"orange\")\n",
    "nx.draw_networkx_nodes(g, pos, [8], node_color=\"b\")\n",
    "nx.draw_networkx_edges(g, pos, [(8,9)], width=3, edge_color=\"g\", style=\"dashed\")\n",
    "nx.draw_networkx_edges(g, pos, [(7,8)], width=3, edge_color=\"b\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Außerdem gibt es noch eine Funktion, um die Labels der Knoten festzulegen:<br/>\n",
    "draw_networkx_labels(G, pos, labels=None, font_size=12, font_color=’k’, font_family=’sans-serif’,\n",
    "font_weight=’normal’, alpha=1.0, ax=None, **kwds)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#wenn Sie alle Labels setzen wollen, können Sie das auch direkt in der Funktion draw_networkx machen\n",
    "nx.draw_networkx(g, pos, node_color=\"yellow\", with_labels=False)\n",
    "labels = {0:0,1:1,2:2,3:\"Center\",4:4,5:5,6:6,7:7,8:8,9:\"Outsider\",}\n",
    "nx.draw_networkx_labels(g, pos, labels=labels, font_size=12, font_color='b')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Und zuletzt die Funktion, die es Ihnen erlaubt, die Labels an den Kanten festzulegen:<br/>\n",
    "draw_networkx_edge_labels(G, pos, edge_labels=None, label_pos=0.5, font_size=10,\n",
    "font_color=’k’, font_family=’sans-serif’, font_weight=’normal’,\n",
    "alpha=1.0, bbox=None, ax=None, rotate=True, **kwds)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "nx.draw_networkx(g, pos, node_color=\"yellow\")\n",
    "nx.draw_networkx_nodes(g, pos, [9], node_color=\"blue\")\n",
    "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\"})\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Graphen als Datenstruktur"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Author ():\n",
    "    def __init__(self, name, yob, yod, works):\n",
    "        self.name = name\n",
    "        self.yob = yob\n",
    "        self.yod = yod\n",
    "        self.works = works\n",
    "\n",
    "a = Author(\"Goethe\", 1749, 1832, [\"Werther\", \"Faust\"])\n",
    "b = Author(\"Schiller\", 1759, 1805, [\"Die Räuber\", \"Wallenstein\"])\n",
    "c = Author(\"Lessing\", 1729, 1781, [\"Minna von Barnhelm\", \"Nathan der Weise\"])\n",
    "\n",
    "g = nx.Graph()\n",
    "g.add_edges_from([(a,b),(a,c),(b,c)])\n",
    "nx.draw_networkx(g)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Außerdem kann man noch beliebige Attribute an Knoten und Kanten hängen und so auch recht komplexe Informationen ablegen."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Aufgabe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Hausaufgaben"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1) Implementieren Sie den Algorithmus für degree centrality. Verwenden Sie die gleiche Signatur wie networkX für die Funktion. <br/>\n",
    "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."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Zusätzliche Literatur"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bernd Klein: <a href=\"http://www.python-course.eu/graphs_python.php\">Graphs in Python</a> -  <a href=\"http://www.python-course.eu/networkx.php\">Networkx</a>."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.4.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}