Netzwerke visualisieren mit NodeXL

Netzwerke visualisieren mit NodeXL

Kennen Sie Microsoft Research? In diesem Netzwerk entwickeln und forschen mehr als
800 Wissenschaftler in allen Teilen dieser Welt an den Computer-Technologien von Morgen. Beispiele sind die Entwicklung neuartiger Spracherkennungssysteme, Verfeinerung von Usability oder Algorithmen zur Verbesserung der Sicherheit von Computern.

Ein Werkzeug, welches entwickelt wurde, ist NodeXL, eine kostenlos verfügbare Anwendung für Excel 2007 zur Visualisierung von Netzwerken und den Beziehungen zwischen einzelnen Knotenpunkten.

Ein paar Grundlagen zur Graphentheorie und Netzwerkanalyse

Die Graphentheorie ist ein mathematisches Teilgebiet, welches sich mit der Analyse von Graphen beschäftigt. Die Untersuchung dieser wird als „Netzwerktheorie“ bezeichnet. In diesem Abschnitt gehen wir nur kurz auf dieses weite Feld ein. Weiterführende
Links finden Sie am Ende des Artikels.

Als „Graph“ wird, mathematisch gesehen, eine Menge von Punkten bezeichnet (im Fach-
jargon auch als „Ecken“ oder „Knoten“ benannt), die gegebenenfalls über Linien verbunden sind, den sogenannten „Kanten“. Die Graphentheorie unterscheidet zwischen verschie-
denen Typen von Graphen. So haben bei „gerichteten Graphen“, wie hier folgend abgebil-
det, die Kanten Pfeile, während „ungerichtete Graphen“ nur einfache Verbindungen aufwei-
sen. Außerdem gibt es „endliche Graphen“, welche eine endliche Anzahl von Kanten und Knoten aufweisen sowie im Gegensatz dazu „unendliche Graphen“.

Eine Frage, die sich nun trotz aller schöner Mathematik stellt, wäre: wo kommen Graphen in der Praxis zum Einsatz?

Ein Beispiel dürfte vielen sicherlich bekannt sein: das „Problem des Handlungsreisenden“. Hierbei geht es darum die Reihenfolge eines Besuchs verschiedener Orte so zu wählen, dass der Reisende nicht zweimal am selben Ort vorbei muss und dabei die sparsamste Strecke wählt. Ein Optimierungsproblem also. Die einzelnen Stationen lassen sich hierbei als Knoten definieren, die Weg zu den Stationen als Kanten. Einige namhafte Wissen-
schaftler haben, aufbauend auf die Graphentheorie entsprechende Modelle entwickelt,
um Lösungen bzw. Teillösungen zu implementieren.

Ein weiteres Beispiel zur Graphentheorie ist das „Königsberger Brückenproblem“.
Hier ging es zu klären, ob es möglich ist, die sieben in folgender Abbildung schematisch angeordneten Brücken zu überqueren ohne ein zweites Mal eine Brücke zu überqueren. Wenn ja, dann stellte sich noch die Frage, ob ein Rundgang möglich wäre.

Leonhardt Euler konnte 1736 anhand der Graphentheorie beweisen, dass dieses Problem leider nicht lösbar ist. Probieren Sie es ruhig mal aus.

Wie bereits zuvor erwähnt beschäftigt sich die Netzwerktheorie anhand statistischer Verfahren mit der Analyse der Strukturen und Beziehungen in Netzwerken. Das können soziale Netzwerke, medizinische Phänomene oder auch das „Internet“ sein. In einem sozialen Netzwerk könnten wir also die Personen als Knoten und die Beziehungen dieser Personen untereinander als Graphen darstellen. Aus der Menge der Konten und Kanten lassen sich spezifische Parameter errechnen, wie beispielsweise Dichte, Zentralität oder auch solche wie „Cliquenbildung“ oder „Machtpositionen“. Folgende Grafik stellt beispiel-
haft ein Netzwerk sehr vereinfacht dar.

Gerade größere Netzwerke benötigen zur schnellen und effektiven Analyse leistungsfähige Algorithmen und Computerprogramme. Es sind einige ausgefeilte Softwareanwendungen auf dem Markt, die solchen Netzwerkanalysen durchführen, nach Kriterien filtern oder gruppieren können. Viele dieser Anwendungen benötigen, zusätzlich zum Wissen um die Verfahren, einen hohen Einarbeitungsaufwand. Die hier vorgestellte Anwendung erhebt sicherlich nicht den Anspruch auf vollständige Abdeckung aller Verfahren, stützt sich aber auf Microsoft Excel, welches wiederum in punkto Bedienung vielen bekannt sein dürfte. Und die Anwendung ist kostenlos.

Wir werden im Folgenden die Anwendung NodeXL vorstellen und ein kleines Beispiel durch-
führen. Wobei festzustellen ist, dass wir an dieser Stelle nicht die volle Funktionalität des Programms beschreiben können, zumal wir auch keine Profis im Bereich der Netzwerk-
analyse sind. Aber vielleicht lassen Sie sich von unseren Experimenten anstecken und entdecken Ihrerseits weitere nützliche Anwendungsbereiche.

NodeXL – Systemvoraussetzungen und Installation

NodeXL benötigt Excel 2007, um verwendet werden zu können. Zudem müssen Sie möglicherweise das .Net Framework auf die Version 3.5 aktualisieren. Eine vorherige Version von NodeXL mit einer kleineren Versionsnummer als 1.0.54 – ehemaliger Name von NodeXL war .NetMap – sollte zuvor deinstalliert werden. NodeXL ist eine englische Anwendung, eine deutsche Version ist uns leider nicht bekannt.

Laden Sie NodeXL von der Projektseite herunter und führen Sie im Anschluss das Setup-Programm aus sowie folgen Sie den dortigen Anweisungen. Die Installationsroutine richtet eine Verknüpfung im Programmmenü von Windows ein, die leider auf meinem Rechner – Windows Server 2008, Office 2007 – nicht funktioniert. Dies mag wohl mit den Rechten des aktuellen Benutzers zu tun haben. Die Verknüpfung ist zur Verwendung des Programms jedoch nicht notwendig.

NodeXL – Starten der Anwendung

Öffnen Sie Microsoft Excel 2007, schließen Sie alle eventuell geöffneten Arbeitsmappen und wählen Sie den Menüeintrag „Neu“ in der Office Schaltfläche.

Wählen Sie nun die Vorlage „NodeXLGraph.xltx“ und bestätigen Sie Ihre Auswahl mit „Ok“. Es öffnet sich nun eine neue Arbeitsmappe sowie am rechten Bildschirmrand ein Ausgabe-
fenster für Ihre Graphen.

Diese Arbeitsmappe beinhaltet einige bereits vorformatierte Tabellen, auf welche wir später zurückkommen werden.

Dieses Fenster dient zur Ausgabe der Graphen. Außerdem lassen sich hier detaillierte
Filter setzen oder die Farben und Größen der Knoten und Kanten anpassen.

Sobald Sie auf eine Zelle einer Tabelle der neuen Arbeitsmappe klicken, zeigt Ihnen
Excel 2007 den Reiter „NodeXL“ in der Multifunktionsleiste an.

NodeXL – Einfaches Beispiel

Wir haben für Sie eine Importdatei vorbereitet, wo die Personen A bis F untereinander bekannt sind. Laden Sie die Datei hier herunter und öffnen Sie diese Datei in Excel. Wählen Sie anschließend im Reiter „NodeXL“ den Menüpunkt „Import“ und dort den Untermenüpunkt „From Open Edge Workbook“. Wählen Sie folgende Einstellungen
für den Dialog:

Schauen Sie sich nach dem Import den Inhalt der Tabelle „Edges“ an. Sie werden feststellen, dass als „Vertex1“ alle Personen aufgeführt werden und in „Vertex2“ die Beziehungen ersterer zu den weiteren Personen. Klicken Sie nun einmal im Ausgabe-
fenster auf „Show Graph“. Das Netzwerk wird erstellt und sieht wie folgt aus.

Zugegeben, das sieht noch nicht besonders ansprechend aus. In der Multifunktionsleiste sind jedoch weitere Menüpunkte zu finden, die uns ermöglichen werden, die Grafik ansprechender zu gestalten. Wählen Sie hierfür den Menüpunkt „Schemes“ und im erscheinenden Dialog folgende Einstellungen:

Statt der kleinen Punkte erhalten Sie nun deutlich größere. Ein 3D-Effekt wäre sicherlich noch schöner anzuschauen. Wechseln Sie hierzu in die Tabelle „Vertices“, also die Knoten. In der Spalte „Shape“ können Sie z.B. die Darstellung „Sphere(3)“ wählen. Nach Aktua-
lisierung der Ausgabe präsentieren sich die Knoten als Kugeln. Die Tabelle bietet Ihnen zudem weitere Einstellmöglichkeiten. So können Sie z.B. eine Person hervorheben, indem Sie die Zelle in der Spalte zu „Color“ bei der Person A mit rechts anklicken und im Kontextmenü den Punkt „Select Color„ anwählen und eine andere Farbe einstellen.

Sie können übrigens auch im Graphen selbst einzelne oder mehrere Elemente rechts anklicken und erhalten entsprechende Optionen.

Die Anwendung kennt einige Algorithmen zur Darstellung der Graphen.
Hier das Ergebnis, welches der „Circle“ Algorithmus liefert.

NodeXL bietet weitere Funktionen zum automatischen Berechnen verschiedener Kenngrößen. Diese können Sie über den Menüpunkt „Graph Metrics“ durchführen.
Rufen Sie den Dialog auf und führen Sie alle Berechnungen durch.

Die Anwendung füllt im Anschluss einige Parameter in den einzelnen Tabellen und erstellt die neue Tabelle „Overall Metrics“, welche allgemeine Informationen zum Graphen enthält. In unserem Beispiel handelt es sich um einen ungerichteten Graphen mit 6 Knoten und 9 Kanten. Der Wert „Graph Density“ ist immer ein Wert zwischen 0 und 1 und misst den Grad der „Nachbarschaft“. In unserem Fall berechnet sich der Wert wie folgt: Graph Density = Anzahl der Kanten / Maximale Anzahl von Kanten = 9 / 15 = 0,6. Schauen wir uns nun weitere berechnete Parameter in der Tabelle „Vertices“ mal genauer an:

Der Wert „Degree“ repräsentiert die Anzahl der Verbindungen einer Person zu einer anderen, für Person A sind dies also 5 Verbindungen. Der Wert in Spalte B „Betweenness Centrality” trifft i.d.R eine Aussage über die Popularität einer Person, anhand des Wertes zu „Closeness Centrality“ lässt sich eine Aussage darüber treffen, wie nah eine Person zu einer anderen ist. Falls Informationen durch das Netzwerk fließen, sind Personen mit einem kleineren Wert zu „Closeness Centrality“ geeigneter diese Information weiterzuverbreiten. In unserem Beispiel wären dies Person A oder B, da diese Kontakte zu allen weiteren Personen besitzen. Manchmal kann eine Verbindung zu einer populären Person wichtiger sein als eine zu einem Einzelgänger. Der Wert zu „Eigenvector Centrality” berücksichtigt nicht nur wie viele ausgehende Verbindungen vorhanden sind, sondern auch wie viele eingehende Verbindungen zu einer Person bestehen. Der letzte Wert in der Spalte C zu „Clustering Coefficient“ lässt Rückschlüsse zu Gruppenbildungen zu.

NodeXL – Beispiel anhand eines Twitter Importes

NodeXL bietet beispielsweise auch die Möglichkeit Kontaktdaten aus Twitter zu importieren. Twitter ist ein Microblogging-Dienst bei welchem die Nachrichten 140 Zeichen nicht überschreiten dürfen. Indem man weiteren dort angemeldeten Personen folgt, kann man dessen Nachrichten auf der persönlichen Seite abrufen und vice-versa. An dieser Stelle ein kleiner Hinweis in eigener Sache: Das kostenlose Tool „Twitter4Excel“ implementiert eine kleine Excel VBA Anwendung, um über Excel Nachrichten an Twitter zu versenden. Es kann hier heruntergeladen werden.

Excel-Ticker und wir als Autoren sind in diesem Portal vertreten. Folgend einige grafische Auswertungen, die wir mit NodeXL erstellt haben. Jeder Punkt repräsentiert einen Twitter Account.

Obige Darstellung hebt unsere drei Twitter Accounts hervor und stellt diese ins Ver-
hältnis zu unseren Followern bzw. den Personen, denen wir folgen. Wobei ich hier einige Schwergewichte (also Personen mit vielen Followern) ausgeblendet habe.

Hier oben eine weitere Darstellung, wobei über dynamische Filter der Grad der
Beziehung „Degree“ verändert bzw. eingeschränkt wurde.

Und zuletzt eine Darstellung, wie sie die Berechnung der „Cluster“ ergeben hat.
Man sieht im unteren rechten Bereich unsere Accounts.

Weiterführende Links

Folgend einige Links zum Thema, den Entwicklern und Entwicklerinnen des Tools und natürlich zur Homepage des Projektes:

» Beispieldatei zum Import

» Projektseite zu NodeXL bei Microsoft Research, Englisch
» Projektseite zu NodeXL bei CodePlex, Englisch
» Powerpoint-Präsentation zu NodeXL von Marc Smith, Englisch

» Artikel zur Graphentheorie bei Wikipedia, Deutsch
» Erweiterter Artikel zur Graphentheorie bei Wikipedia, Englisch
» Artikel zur Netzwerktheorie bei Wikipedia, Deutsch
» Soziale Netzwerkforschung als Methode der Sozialwissenschaft, PDF in Deutsch