UPDATE: social network visualization (1)

30. Dezember 2008 – 22:55

Wer ist mit wem thematisch verwandt? Wer schreibt stets mit wem an gleichen Artikeln? Fragen die in einer unternehmerischen Wiki Umgebung durchaus nicht unwichtig sind.

Um in einem MediaWiki solche Relationen herauszufiltern muss man nur auf die ‘revisions’ zurückgreifen. Jede Änderung an einem Artikel wird als eine neue Version abgelegt. In den Metadaten sind Uhrzeit, Benutzer, Art und Umfang festgehalten. Autorenpaare, die oft gemeinsam an einem Artikel editieren sind sicherlich thematisch verbundener als solche, die nie zusammen an einem Artikel (Thema) arbeiten.

update: Modell

Ein Author ist mit einem anderen Author thematisch verwandt, wenn beide gemeinsam einen Artikel verfasst oder Artikel des Anderen editiert haben. Um so häufiger die Autoren verschiedene Artikel miteinander editieren um so enger sind sie miteinander thematisch verwandt, denn um so häufiger sie an verschiedenen Artikeln arbeiten desto höher ist die Wahrscheinlichkeit, dass sich beide in diesen Themen gut auskennen (sie ergänzen sich gegenseitig). Wenn sie jedoch zwar häufig aber nur an einem oder wenigen verschiedenen Artikeln schreiben, sagt es nichts darüber aus ob sie sich in ähnlichen oder gleichen Themen auskennen.

Eine Kante des Graphen verbinde jedes Knoten-Paar (x,y) von Autoren, die zumindest einen Artikel zusammen editiert haben. Die Kantenstärke stelle die Häufigkeit des Auftretens der Relation an verschiedenen Artikeln dar. Je häufiger das Relationentupel auftritt, umso dicker die Kanten.

Autor A erstellt einen Artikel S worauf dann Autor B diesen editiert, verbessert oder vervollständigt. B erstellt zusammen mit C auch einen Artikel M. Damit steht A in Relation zu B, B in Relation zu C, A und C untereinander jedoch nicht. B ist also Co-Autor von A und C von B. Autor A und Autor C “kennen” sich aber nicht.

update: Datengenerierung

Die Eingabedaten für GraphViz werden aus der Tabelle ‘revision’ in der Datenbank mit Hilfe der Funktion ‘doRelationsQuery()’ ausgelesen. Hierzu werden zu jeder (Artikel-)Seite die Benutzer und deren ID aufgelistet, die darin editiert haben.

Ferner wird abgefragt ob es sich um eine geringfügige Änderung (minor edit) handelt oder nicht. Geringfügige Änderungen werden nicht betrachtet, da eine geringfügige Änderung in den meisten Fällen nur eine Formatierung korrigiert und somit keine Relation des Editors mit dem Autor beinhaltet.

Aus dem Ergebnis der Query wird ein Mehrdimensionales Array erzeugt, so dass zu jeder Seite (Hauptindex des Arrays) jeweils ein Unterarray mit den Usern zugeordnet wird. Es werden also vorerst n-Tupel von Usern gesammelt, die gemeinsam an Artikeln gearbeitet haben. Um Relationen korrekt auszuwerten müssen nun alle n-Tupel auf 2er Tupel aufgebrochen werden. Nur so ist es möglich das mehrfache Vorkommen gleicher Tupel zu zählen.

Falls ein Tupel mehrfach vorkommt, bedeutet dies, dass diese User mehrfach an verschiedenen Artikeln editiert haben. In diesem Fall erhöht sich die Nähe der beiden Autoren zueinander. Die Häufigkeit des Auftretens des Tupels wird dann als Maß für die Kantenstärke in der Darstellung der Relationen verwendet.

Frameworks zur Darstellung

Um die Relationen darzustellen habe ich auf das (GraphML ähnliche) Datenformat vom Relation Browser hingearbeitet, welcher aber nur Relationen von einem bestimmten User anzeigt, d.h. Alle mit dem initierenden User NICHT verbundenen Knoten werden nicht angezeigt. Sie können nur mittels eines Untermenüs sichtbar gemacht werden (Screenrip A [SWF]).

Es stellt sich also die Frage, ob generell alle Relationen dargestellt werden, oder spezifisch nur auf einen Benutzer zugeschnittene.

Graph Gear ließe sich mit einer sehr ähnlich aufgebauten Datenbasis aufbauen. Hier wären sogar beide Darstellungsmöglichkeiten machbar. Allerdings ist Graph Gear meiner Meinung nach ein unzureichendes Visualisierungstool, da die Darstellung viel zu verspielt ist, die Knoten sehr aggressiv positioniert werden und die Labels fast nie lesbar angeordnet werden (Screenrip B [SWF]).

Alternativ ließe sich wieder GraphViz verwenden. GraphViz ist jedoch weder interaktiv noch ist die Darstellung schön (Screenrip C [SWF]).

Weitere “Frameworks”, die auf ähnlichen Datenformaten (GraphML oder XGMML) verwendbar wären existieren nicht. Andere benötigen stets eine strikte Hierarchieeinteilung (XML Baum), die sich nur wesentlich schwieriger erzeugen ließe.

update: Download

relations.php

update: Installation

die GraphViz MediaWiki Extension installieren
die Render Engine von GraphViz auf neato umstellen, dazu in der Installationsanleitung die Zeile $wgGraphVizSettings->dotCommand = "/<graphvizpath>/dot"; gegen $wgGraphVizSettings->dotCommand = "/<graphvizpath>/neato"; tauschen
die relations.php in das extensions Verzeichnis der Wiki Installation kopieren
in der Localsettings.php require_once("$IP/extensions/relations.php" );hinzufügen

Wenn man vermeiden möchte, dass die Umstellung auf neato im gesamten Wiki vollzogen wird, kann man auch die von mir modifizierte graphViz.php anstatt die originale verwenden. Sie unterstützt im Gegensatz zur originalen Version Parameter, die beim parsen ausgelesen werden. Der Parameter ‘renderer’ übermittelt den gewünschte Rendering-Alg.
<graphviz renderer="neato"></graphviz>

Falls die modifizierte Version verwendet wird, bedarf es noch einer weiteren Änderung. Der Graphviz Pfad darf nur noch auf den Ordner referenzieren, nicht mehr auf den Renderer selbst. Also das ‘dot’ im Pfad entfernen!
$wgGraphVizSettings->dotCommand = "/<graphvizpath>/";

Falls kein Parameter angegeben wird, wird automatisch ‘dot’ verwendet. Erlaubt sind die Parameter renderer={dot,neato,dotty}

update: Verwendung

auf einer beliebigen Seite den Tag <relations/> einfügen.

Vielen Dank an nikosch aus dem php.de Forum

ViskoDa