Einige der Leser kennen es sicherlich: die Behauptung, dass man, folgt man in der Wikipedia immer dem ersten nicht-kursiven und nicht in Klammern stehendem Link, immer bei der Philosophie landen wird. Drüben bei den Wissenslogs wurde das Thema bereits vor kurzer Zeit besprochen. Dabei wurde die Beobachtung gemacht, dass – zumindest in der deutschen Wikipedia – die meisten Pfade, die zur Philosophie führen, vorher den Artikel “Wissenschaft” berühren. Der ursprüngliche Hinweis war vermutlich spöttisch gemeint und sollte wohl darauf hinweisen, dass Philosophie derart allgemein ist, dass sich mit ihr alles erklären lässt. Dabei ist die eigentliche Aussage viel positiver: am Ende ist alles Wissenschaft!


Gut, bis hierhin erzähle ich sicherlich nichts neues. Aber ich bin nicht umsonst Informatiker und dies hier ist ein Informatik-Blog; was liegt also näher, einmal mit Mitteln der Informatik zu untersuchen, ob diese Behauptung überhaupt korrekt ist (und dabei die Chance zu nutzen, einige Methoden der Informatik zu erklären)? Für die englische Wikipedia gibt es hierzu bereits ein nettes Programm, mit welchem die Beziehungen der Artikel untereinander visualisiert werden können.

i-9b37c423294741beffdf56248c062a45-Xefer.png

Programm zur Visualisierung der Artikelbeziehungen

Aber erstens beschränkt sich das auf die englische Wikipedia (mein Fehler: tut es nicht) und zweitens bleibt man hier auf relativ kleine Mengen von Datensätzen beschränkt (außerdem fehlt eine Auswertung). Also habe ich mich hingesetzt und ein eigenes Programm geschrieben, mit welchem ich die Behauptung überprüfen kann.

Zu Beginn noch einmal kurz die Problemstellung. Die Behauptung ist die folgende: klickt man in einem beliebigen Wikipedia-Artikel auf den ersten Link, der nicht in Klammern steht oder kursiv ist und wiederholt die Prozedur beim so aufgerufenen Artikel, so landet man irgendwann bei der Philosophie. Wie bereits erwähnt, führt der Weg in der deutschen Wikipedia dabei meist über “Wissenschaft” – und da dies ein Wissenschafts-Blog ist, ändere ich die Behauptung entsprechend ab und prüfe nicht auf “Philosophie”, sondern auf “Wissenschaft”.

Nach einigem Klicken von Hand fällt dabei auf, dass die Behauptung so schon einmal nicht ganz stimmen kann: ab und zu landet man in Kreisen, das heißt, man besucht immer wieder die gleichen Artikel. Es ergeben sich sich somit zwei mögliche Artikel-Strukturen (den Fall, dass ein Artikel keine weiteren Links hat, klammere ich einmal aus, da er selten auftritt). Das erste Beispiel zeigt einen regulären Pfad, das zweite einen Kreis mit der Größe 2 hat (da 2 Artikel daran beteiligt sind); beide Beispiele kommen so real in der Wikipedia vor:

i-9af70d08481663b00e27dc23e91dc08a-Ketten.png

Das Problem muss also ein wenig abgeändert werden; ich bearbeite daher die folgende Frage: wie groß ist das Verhältnis von Artikeln, die schließlich zur Wissenschaft führen, gegenüber den Artikeln, die einen Kreis bilden.

Zur Lösung eines solchen Problems wird man sich in der Regel einen sogenannten Webcrawler programmieren. Das ist ein Programm, welches Websites nach bestimmten Informationen durchsucht und dabei auch den Links innerhalb einer Site folgt. Die Vernetzung der Sites (in unserem Fall: Wikipedia-Artikel) untereinander bildet einen sogenannten Graphen. Ein Graph besteht aus verschiedenen Knoten (Sites, Artikel), die über Kanten (Links) miteinander verbunden sind. Die untenstehende Abbildung zeigt ein kleines Beispiel hierfür (die Kästchen sind Knoten, die Linien sind Kanten). Ein üblicher Webcrawler würde ausgehend von einem Knoten alle weiteren Knoten, die über Kanten miteinander verbunden sind, absuchen.

i-6e7118e046e80ed9e8cb9b12803f971f-Graph.png

Unser Wiki-Crawler muss nur, ausgehend von einem Knoten (also einer Site) oder Seed (von englisch “Samen”), dem ersten gültigen Link auf der Site folgen, und zwar so lange, bis der Wissenschafts-Artikel oder ein Kreis gefunden wird (dieses Verfahren entspricht im Übrigen einer sogenannten Tiefensuche, welche aber sicherlich noch ihren eigenen Artikel erhalten wird). Wurde auf diese Art ein Ziel erreicht, kann für den so bestimmten Pfad (also den Seed-Artikel und alle Artikel auf dem Weg zum Ziel) die Entfernung zur Wissenschaft oder eben die Information, dass sie nicht erreichbar ist, gespeichert werden. Danach geht es mit dem nächsten Seed weiter, bis alle Artikel der Wikipedia durchsucht wurden – oder der Speicher des Computers voll ist. Man muss dabei übrigens nur von solchen Seeds ausgehen, die noch nicht bereits auf einem Weg gefunden wurden. Für den oben aufgezeichneten Graphen könnte also folgender Pfad gefunden werden (die Kästchen enthalten die Entfernung zum Ziel):

i-5ac2f8aab0524e37c641824417f71bdc-Graph2.png

Die Bestimmung weiteren Seeds kann hier übrigens recht clever gelöst werden; hat man nämlich nicht alle vorhandenen Sites zur Verfügung (wie es bei mir und der Wikipedia der Fall war), behilft man sich mit folgendem Vorgehen: von jeder durchsuchten Site wird nicht nur der erste Link genommen und weiterverfolgt, sondern es werden auch sämtliche weiteren Links der Site zumindest herausgesucht und gespeichert; danach wird der erste Link weiterverfolgt. Terminiert die aktuelle Suche, sprich, wurde das Ziel oder ein Kreis gefunden, so kann aus den gespeicherten Sites ein neuer Seed herausgesucht werden und das Verfahren beginnt von vorn. Das Heraussuchen von weiteren möglichen Wegen und Speicherung zur späteren Verwendung nennt man Breitensuche. Für unseren Webcrawler kommt demzufolge eine Kombination aus Tiefen– und Breitensuche zur Anwendung.

Und was kommt nun am Ende heraus, wenn man das beschriebene Verfahren auf die Wikipedia loslässt? Auf Grund von Bandbreiteneinschränkungen musste ich mich bei meiner Untersuchung auf 10.000 betrachtete Artikel beschränken, aber ich denke, dass sie dennoch eine recht gute Grundlage zur Beantwortung der initial gestellten Frage liefern.

Trägt man in einem Diagramm die Pfadlänge gegen die Anzahl der Pfade (also Wege von einem beliebigen Artikel zum Wissenschafts-Artikel) mit dieser Länge auf, so ergibt sich das folgende Bild mit der darunterliegenden Datentabelle:

i-0846ac5b4363eb3ee853bb86cefd111b-FoundPaths.png
   Pfadlänge    Anzahl der Pfade
1 43
2 200
3 297
4 363
5 467
6 454
7 474
8 464
9 622
10 713
11 600
12 309
13 208
14 256
15 389
16 145
17 114
18 116
19 118
20 126
21 62
22 24
23 11
24 6
25 2
26 3
27 2
28 1

Für die Anzahl der Kreise lässt sich ebenso eine Datentabelle angeben. Ein Diagramm lohnt sich hier nicht, da es überraschenderweise nur wenig verschiedene Kreis-Größen gibt; es fällt vor allem auf, dass die Mehrzahl der Kreise die Größe 2 hat, sprich, zwei Artikel gegenseitig aufeinander verweisen. Die Kreis-Größe 1 ist technisch bedingt: einige Artikel verweisen als erstes (und meist auch einziges) auf sich selbst. Die folgenden Daten konnte ich bestimmen:

   Kreis-Größe    Anzahl Kreise
1 62
2 1689
3 54
7 428
15 613

Insgesamt ergeben sich damit bei 10.000 untersuchten Artikeln 6589 Artikel, die einen Pfad zum Wissenschaftsartikel besitzen und 2846 Artikel, die in einem Kreis enden.*
Daraus ergibt sich ein Verhältnis von ungefähr 2,3 zu Gunsten der gültigen Pfade oder einfach gesagt: für jeden Artikel, der am Ende in einen Kreis führt, existieren 2.3 Artikel, die einen Pfad zum Wissenschaftsartikel besitzen. Die Behauptung, dass am Ende alles zur Wissenschaft (und damit zur Philosophie) führt, lässt sich damit zwar nicht guten Gewissens bestätigen, aber immerhin kann man sagen, dass ungefähr 70% aller Artikel in der Wikipedia über ihren ersten Link im Text einen Bezug zur Wissenschaft haben. Das Gespann “Philosophie – Wissenschaft” bildet übrigens einen Kreis der Größe 5 – Wissenschaft verweist also am Ende sogar auf sich selbst.

Wenn das mal nicht für die Wissenschaft spricht!


*Für alle die, die nachgerechnet haben: ja, die Summe aus Pfaden und Kreisen ergibt nicht ganz 10.000. Das hat technische Gründe, da einige verlinkte Artikel nicht korrekt geladen werden konnten.

Kommentare (7)

  1. #1 the vegetarian diaries
    Juli 3, 2011

    sehr schöner artikel,
    da hat man doch einen tollen artikel auf den man bei der nächsten diskussion verweisen kann!

    lg

  2. #2 lost control
    Juli 3, 2011

    Durchaus interessanter Ansatz bzgl. Artikelhierarchie… da könnte man etliches mehr anstellen.

    ad Bandbreite: ich bilde mir ein irgendwann mal über irgendeine Wikipedia-Analyse drübergestolpert zu sein von der mir hängengeblieben ist, daß es – iirc – xml-dumps vom content gibt, dh. man könnte seine Analysen direkt drauflosjagen, ohne Bandbreitenbedenken.
    *scratches head* wenn ich jetzt nur noch wüßte, was das ca. war, dann könnte ich eventuell noch nen link finden…?

  3. #3 Marcus Frenkel
    Juli 3, 2011

    @lost control
    Es gibt auch einen kompletten Dump sämtlicher Wikipedia-Artikel. Für 3GB kann man den haben. 😉
    Ich werde mir das auch irgendwann ziehen und auf der Wiki noch ein paar Analysen laufen lassen…wenn denn jemand schöne Ideen hat, was man noch so rausziehen kann.
    Immer her damit!

  4. #4 bronte
    Juli 3, 2011

    “den Fall, dass ein Artikel keine weiteren Links hat, klammere ich einmal aus, da er selten auftritt.”
    Hast du auch die Zahl der Artikel bestimmt, von denen aus man in einer solchen Sackgasse landet? Denn Grundsätzlich sollte es ja (wegen der endlichen Anzahl der Artikel) nur die beiden Möglichkeiten “Kreis” und “Sackgasse” geben.
    Von den Kreisen ist nach deinen Ergebnissen Wissenschaft->Wissen->Wahrheit->Wirklichkeit->Philosophie->Wissenschaft derjenige, in dem man von den meisten Artikeln aus landet.
    Es wäre daher vielleicht auch interessant, welches die häufigste Sackgasse ist (oder welches der zweit-, dritt-, etc. häufigste Kreis ist).

  5. #5 Marcus Frenkel
    Juli 4, 2011

    Nein, wie gesagt: den Sackgassen-Fall habe ich einmal ausgeklammert. Der Grund ist hier (mal wieder) technischer Natur: es ist nämlich gar nicht so trivial, herauszubekommen, ob man in einer Sackgasse ist, zumindest dann, wenn man den kompletten Quelltext einer Site benutzt; mit jeder Site kommen nämlich unzählige Links, bei denen man erst einmal schauen muss, wo sie hingehören. Solche “Sonderlinks” sind z.B. die Literaturangaben, “Siehe auch”-Links, die Kategorien, Begriffserklärungen und so weiter.
    Das rauszufiltern ist am Ende möglich und auch nicht so sehr viel Arbeit; bei der aktuellen Version wollte ich sie mir nur einfach nicht machen. 😉

    Aber sicher, die Anzahl der Sackgassen wäre auch interessant und auch, wieviele verschiedene Kreise es gibt (die Zahlen oben geben ja nur an, wie viele Artikel in einen Kreis führen, aber nicht, in welchen – da können mehrfach die gleichen vorkommen).

    Ich habe es mir auf jeden Fall einmal notiert.

  6. #6 Stephan B.
    Juli 7, 2011

    Ich habe mal den Link zu Xefer ausprobiert. Da kann man doch verschiedene Sprachen, und damit verschiedene Wikipedias auswählen. Und Deutsch steht auch zur Auswahl.

  7. #7 Marcus Frenkel
    Juli 7, 2011

    Danke, das Feld hatte ich übersehen. Habe es korrigiert.