Ranking von Internetseiten mit Matrizen

Question

Beispiel 3: Ranking von Internetseiten.

Bei einer Suche findet Google gewöhnlich eine riesige Menge von Seiten. Diese sollen in einer nutzerfreundlichen Reihenfolge ausgegeben werden, also nach einer Wertigkeit. Das Grundprinzip ist, dass das Internet selbst ein Ranking erzeugt (welches allerdings nicht die Qualität einer Seite ausdrückt, sondern den Grad ihrer Vernetzung). Der Wert \( x_{i} \) einer Seite \( S_{i} \) wird dabei bestimmt durch die Seiten \( S_{j} \), die einen Link auf \( S_{i} \) haben. Genauer soll eine solche Seite \( S_{j} \) ihren Wert \( x_{j} \) anteilig auf \( S_{i} \) übertragen, d.h. mit der Rate
\( a_{i j}=\left(\text { Anzahl aller von } S_{j} \text { verlinkten Seiten }\right)^{-1} \)

Damit entsteht die Gleichung
\( \sum \limits_{j} a_{i j} x_{j}=x_{i} \)

Das hier benutzte \( \sum \)-Zeichen bedeutet Summation über alle \( n \) Internetseiten \( S_{j} \), wenn für Seiten ohne Link auf \( S_{i} \) einfach \( a_{i j} \) als 0 definiert wird.

Leider kann \( x_{i} \) mit dieser einen Gleichung nicht berechnet werden, weil die Werte \( x_{j} \) ebenso unbekannt sind. Zum Glück gibt es aber für jede Seite \( S_{i} \) eine solche Gleichung, und dieses gewaltige Gleichungssystem fällt unter den anfangs aufgestellten Typ, wenn man in jeder Gleichung das rechts stehende \( x_{i} \) durch Subtraktion nach links hinüberbringt. Damit entsteht ein lineares Gleichungssystem, in dem alle \( b_{i} \) gleich 0 sind; solche Systeme heißen homogen.

Ist das System lösbar? Sicher, jedes homogene System wird durch \( x_{1}=\ldots=x_{n}=0 \) erfüllt das kann allerdings nur Internetgegner befriedigen. Die Frage ist also, ob eine andere, brauchbare Lösung existiert (und berechnet werden kann). Antwort ja, das System muss aber noch leicht modifiziert werden, um eine eindeutige Lösung mit Zahlen \( x_{j}>0 \) zu haben. Diese wird für einen ausgewählten Teil des inzwischen zu gigantischen Gesamtnetzes regelmäfig berechnet.

Ich verstehe das Beispiel aus meinem Skript nicht, daher folgendes Beispiel:

Seien die Internetseiten S1-S5 gegeben und wie folgt verlinkt:

S1->S2; S1->S3

S2->S1; S2->S4

S3->S4

S4->S1

S5->S4

Wie baut man daraus ein Gleichungssystem der Form Bx=0 auf, wobei B ein Element aus lR mit 5x5 ist. Wie bestimme ich nun die Lösungsmenge und leite daraus dann die Rangfolge der Seiten ab?

Vom Duplikat:

In der zum Ranking von Webseiten konstruierten Matrix \( A \in \mathbb{R}^{n \times n} \) haben alle Spaltensummen den Wert 1 , wenn von jeder Seite mindestens ein Link ausgeht - diese Situation sei jetzt gegeben.

a) Seien \( v_{1}, \ldots, v_{n} \) die Zeilen der Matrix \( B:=A-E \). Geben Sie Zahlen \( \lambda_{1}, \ldots, \lambda_{n} \in \mathbb{R} \) an, die nicht alle 0 sind, mit \( \lambda_{1} v_{1}+\ldots+\lambda_{n} v_{n}=0 \). Was können Sie dann über \( \operatorname{rg}(B) \) sagen?

b) Schließen Sie aus a), dass es im \( \mathbb{R}^{n} \) ein \( x \neq 0 \) gibt mit \( A x=x \) (wie für das Ranking verlangt).

Comments

Ich hab mal etwas rum überlegt, verzweifle selber noch daran, auch wenn die eigtl einfach ist.

B=

07100
10010
00010
10000
00070

Spalte 1 bedeutet:  von S1 zu S1=0  Von S2 zu S1=1 von S3 zu S1 =0 von S4 zu S1=1 von S5 zu S1 =0 usw.

Reihe 1 bedeutet: Von S1 zu S1=0 Von S1 zu S2=1 von S1 zu S3=1 von S1 zu S4=0 vonn S1 zu S5=0 usw.

Die ∑ der Links der Seiten wäre jetzt für S1 zum Beispiel 2, weil die von 2 Seiten verlinkt wird und von S4  zum Beispiel 3, weil sie 3 mal verlinkt wurde. (Jeweils die Summe der Spalten) Hieße im Prinzip: S4 wird am meisten verlinkt, somit wäre sie am wichtigsten, doch das wäre zu einfach zu manipulieren, indem man die anderen Seiten einfach öfter verlinkt. Daher hat das keine große Aussagekraft.

Deswegen betrachtet man die ∑ der ausgehenden Links, also die Summe der einzelnen Reihen. (2,2,1,1,1)

Wenn man nun B mit dieser ∑dividiert, erhält man folgende Matrix B':

\( \begin{array}{ccccc}0 & 1 / 2 & 1 / 2 & 0 & 0 \\ 1 / 2 & 0 & 0 & 1 / 2 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0\end{array} \)

Ich habe iwo bei den anderen Kommilitonen mitbekommen, dass die Spalten in der Summe 1 ergeben müssen, das wäre gegeben, wenn man diese nun transponiert, also B^T:

\( \begin{array}{ccccc}0 & 1 / 2 & 0 & 1 & 0 \\ 1 / 2 & 0 & 0 & 0 & 0 \\ 1/2 & 0 & 0 & 0 & 0 \\ 0 & 1/2 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0\end{array} \)

Und nun komme ich nicht mehr weiter. Vielleicht ist es zu einfach, aber ich kriege in meinen Kopf keine Werte für x.

---

Mhm weiß sonst noch wer wie es weitergehen könnte?

---

Ich sitze gerade auch noch dran, immer diese Oldenburger hier :D