Linkbasiertes Ranking: Seiten nach Verweisen ordnen

Linkbasiertes Ranking (englisch link analysis) ordnet Webseiten danach, wie viele wichtige Seiten auf sie verweisen. Ein Verweis zählt dabei wie eine Empfehlung, und eine Empfehlung von einer wichtigen Seite wiegt mehr.

Der Text einer Seite allein reicht nicht, um die beste zu finden: Jeder kann „Nudeln“ hundertmal auf eine Seite schreiben. Verweise von anderen sind schwerer zu fälschen.

Eine Seite, auf die viele andere verweisen, wirkt wichtig. Noch wichtiger wirkt sie, wenn diese anderen Seiten selbst wichtig sind. Die Idee ist also rekursiv: Wichtig ist, wer von Wichtigen verlinkt wird.

Jede Seite gibt ihren Rang zu gleichen Teilen an die Seiten weiter, auf die sie verweist. Hat sie zwei Links, geht an jeden die Hälfte.

Stellen Sie sich jemanden vor, der immer wieder einen zufälligen Link anklickt. Der Rang einer Seite ist die Wahrscheinlichkeit, dass diese Person gerade dort ist. Seiten mit vielen Zugängen sind öfter besucht.

Mit 15 Prozent Wahrscheinlichkeit gibt die Person auf und springt auf eine beliebige Seite. Das ist die Dämpfung 0,85. Sie verhindert, dass der Rang in einer Sackgasse hängen bleibt.

Zu Beginn bekommt jede Seite denselben Rang, bei vier Seiten also 0,25. In jeder Runde gilt für eine Seite: neuer Rang gleich 0,15 durch N, plus 0,85 mal die Summe der Anteile.

Der Anteil einer Quelle ist ihr Rang geteilt durch die Zahl ihrer Links. Für „start“ ist das 0,15 durch 4 plus 0,85 mal (0,25 plus 0,125 plus 0,25), also 0,56875.

docker exec jupyter python3 -c "print(round(0.15/4 + 0.85*(0.25 + 0.25/2 + 0.25), 5))"

links = {
    "start": ["mensa", "bib"],
    "mensa": ["start"],
    "bib": ["start", "mensa"],
    "sekretariat": ["start"],
}
daempfung = 0.85
rang = {}
for seite in links:
    rang[seite] = 1 / len(links)
for runde in range(1, 4):
    neu = {}
    for seite in links:
        summe = 0
        for quelle in links:
            if seite in links[quelle]:
                summe = summe + rang[quelle] / len(links[quelle])
        neu[seite] = (1 - daempfung) / len(links) + daempfung * summe
    rang = neu
    print("Runde", runde, "start:", round(rang["start"], 4), "bib:", round(rang["bib"], 4))
# Erhöhen Sie range(1, 4) auf range(1, 21). Wann ändern sich die Zahlen kaum noch?

Die Tabelle zeigt: Die Ränge schwanken zuerst und beruhigen sich dann. Nach etwa 20 Runden ändern sie sich nur noch in der dritten Stelle. Man sagt, die Rechnung konvergiert, und hört dort auf.

Die Summe aller Ränge bleibt dabei immer 1. Eine Seite ohne Links nach außen würde Rang verlieren. Echte Verfahren verteilen ihn gleichmäßig; unsere Daten haben keine solche Seite.

rang = {"start": 0.4292, "mensa": 0.3134, "bib": 0.2199, "sekretariat": 0.0375}
summe = 0
for seite in rang:
    summe = summe + rang[seite]
print(round(summe, 4))
beste = "start"
for seite in rang:
    if rang[seite] > rang[beste]:
        beste = seite
print("Höchster Rang:", beste)
# Wie ändert sich die Summe, wenn Sie einen Rang um 0.1 erhöhen?

docker exec jupyter python3 -c "print(round(0.15/4 + 0.85*0.25/2, 5))"