PageRank mittels PHP berechnen
Hinter PageRank steht ein verfahren, um verlinkte Dokumente (z.B. Webseiten) anhand der Linkstruktur zu bewerten und zu gewichten. Entwickelt wurde der Algorithmus von Larry Page und Sergei Brin, den Gründern von Google, und der Algorithmus brachte den großen Erfolg für Google. Erstmals konnte man anhand von Verweisen zwischen Webseiten analysieren, welche Webseiten (und deren Unterseiten) häufig verlinkt sind und damit potentiell wichtig sind.
Um diese Linkstruktur zwischen Webseiten zu erfassen, liest ein Crawler das HTML der Webseite aus und analysiert, welche Hyperlinks vorhanden sind inklusive deren Linkziele. Dabei müssen natürlich auch Follow- bzw. NoFollow-Angaben (Fachbeitrag zu diesem Thema) berücksichtigt werden.
In diesem Artikel möchte ich euch zeigen, wie ihr in PHP vergleichsweise den PageRank für einen kleinen Linkgraphen berechnen könnt. So lässt sich beispielsweise die wichtigen Seiten einer (kleineren) Website herausfinden.
Der PageRank Algorithmus
Hinter dem Algorithmus steckt folgende Formel:
Für die genauen mathematischen Details möchte ich auf den entsprechenden Wikipedia-Artikel verweisen: PageRank
Anschaulich funktioniert wie PageRank wie folgt (Bildquelle):
Für jeden Knoten (z.B. Webseite) in meinem Graphen habe ich eingehende und ausgehende Verbindungen, diese entsprechen meine eingehenden Links und meine ausgehenden Links.
Ein Knoten wird als wichtig erachtet, wenn dieser viele eingehende Verbindungen hat, sprich, wenn viele Webseiten auf den Knoten verlinken. Dabei zählen Verbindungen unterschiedlich viel: Verlinkt eine Website mit hohem PageRank, so ist dies positiver als wenn viele unwichtige Webseiten auf ein Ziel verlinken würden. Sprich, der PageRank ist ein rekursives Verfahren, der PageRank einer Seite ist umso höher, je mehr Seiten mit hohem PageRank auf die Seite verweisen.
In der Praxis wird der PageRank in mehreren Runden berechnet. Zu Beginn bekommt jeder Knoten den gleichen PageRank. Danach wird der PageRank für jede Seite aktualisiert mit den ursprünglichen, gleichen PageRanks aller Seiten. Da sich der PageRank der Seiten geändert hat, ändert sich auch wie viel PageRank sie an andere Seiten weitergeben. Also wird der PageRank mit den aktualisierten Werten erneut berechnet. Dies wird entweder für eine gewisse Anzahl an Runden durchgeführt, oder bis es nur noch minimale Änderungen in den PageRank Werten gibt.
PageRank in PHP Berechnen
Die Berechnung von PageRank ist leider nicht ganz einfach. Aber zum Glück gibt es bereits Programmcode, der PageRank für einen Graphen für uns berechnen kann: paslandau/pagerank
Die Installation und Nutzung ist leider nicht ganz einfach. Zuerst empfiehlt es sich, Composer zu installieren. Composer ist der Standard-Packetmanager für PHP und macht das Installieren von Abhängigkeiten recht einfach.
Nachdem ihr Composer installiert habt, erstellt ihr eine neuen Ordner eine composer.json Datei mit folgendem Inhalt:
|
1 2 3 4 5 6 7 8 9 10 |
{ "repositories": [ { "type": "composer", "url": "http://packages.myseosolution.de/"} ], "minimum-stability": "dev", "require": { "paslandau/pagerank": "dev-master" }, "config": { "secure-http": false } } |
Ist diese Datei erstellt, steuert ihr mit der Kommandozeile in den entsprechenden Ordner und führt den Befehl
|
1 |
composer install |
aus. Dieser lädt die notwendigen Programmdateien herunter.
Anschließend könnt ihr den PageRank für eine Beispielseite wie folgt berechnen:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
<?php require 'vendor/autoload.php'; use paslandau\PageRank\Node; use paslandau\PageRank\Graph; use paslandau\PageRank\Edge; use paslandau\PageRank\Calculation\PageRank; // Unterseiten $home = new Node("Home"); $anfahrt = new Node("Anfahrt"); $team = new Node("Team"); $services = new Node("Services"); $kontakt = new Node("Kontakt"); $produkte = new Node("Produkte"); $produkt1 = new Node("Produkt 1"); $produkt2 = new Node("Produkt 2"); $produkt3 = new Node("Produkt 3"); $produkt4 = new Node("Produkt 4"); // Links zwischen den Seiten $graph = new Graph(); $graph->addEdge(new Edge($home, $produkte)); $graph->addEdge(new Edge($home, $anfahrt)); $graph->addEdge(new Edge($home, $team)); $graph->addEdge(new Edge($home, $services)); $graph->addEdge(new Edge($home, $kontakt)); $graph->addEdge(new Edge($produkte, $kontakt)); $graph->addEdge(new Edge($produkte, $produkt1)); $graph->addEdge(new Edge($produkte, $produkt2)); $graph->addEdge(new Edge($produkte, $produkt3)); $graph->addEdge(new Edge($produkte, $produkt4)); $graph->addEdge(new Edge($services, $anfahrt)); $graph->addEdge(new Edge($services, $kontakt)); $graph->addEdge(new Edge($services, $produkte)); $graph->addEdge(new Edge($services, $produkt1)); $graph->addEdge(new Edge($services, $produkt2)); // Berechnung des PageRanks $pageRank = new PageRank(); $result = $pageRank->calculatePagerank($graph); //Ausgabe $pagerankNodes = $result->getNodes(); foreach($pagerankNodes as $node){ echo $node->getName()." hat einen PageRank von ".$node->getPr()."<br>"; } |
Die Ausgabe von dem Script sieht wie folgt aus:
|
1 2 3 4 5 6 7 8 9 10 |
Home hat einen PageRank von 0.015 Produkte hat einen PageRank von 0.0205335 Anfahrt hat einen PageRank von 0.0205335 Team hat einen PageRank von 0.01755 Services hat einen PageRank von 0.01755 Kontakt hat einen PageRank von 0.024024195 Produkt 1 hat einen PageRank von 0.021474195 Produkt 2 hat einen PageRank von 0.021474195 Produkt 3 hat einen PageRank von 0.018490695 Produkt 4 hat einen PageRank von 0.018490695 |
Im ersten Teil des Scripts erstellt ihr zuerst Knoten (Nodes) für alle Seiten einer Website. Anschließend fügt ihr Verbindungen (Edges) hinzu, z.B. die Verlinkungen zwischen euren Seiten. Im Anschluss wird der PageRank berechnet und die Seiten mit dem höchsten PageRank werden
Autor: Nils Reimers