PageRank Algorithmus¶
Dieses Dokument wurde erstellt durch Stefan Kühnel stefan.kuehnel@hm.edu.
Inhaltsverzeichnis¶
1. Abstrakt 2. Theoretisches Modell 2.1. Grundlegendes Konzept 2.2. Veranschaulichung durch Kreuzungen 3. Mathematisches Modell 3.1. Die ursprüngliche Summenformel 3.2. Netzwerk als Hyperlink Matrix 3.3. Probleme der Hyperlink Matrix 3.4. Probleme der stochastischen Matrix 3.5. Herleitung der Google Matrix 3.6. Berechnung des PageRanks durch Power Method 4. Implementierung des PageRank Algorithmus 5. Anwendung und Veranschaulichung 5.1. Umwandlung der Hyperlink Matrix in eine stochastische Matrix 5.2. Konvertierung der stochastischen Matrix in die Google Matrix 5.3. Berechnung des stationären Zustandes 6. Literaturverzeichnis 7. Abbildungsverzeichnis 8. Appendix 8.1. Anwendung der iterativen Methode 8.2. Anwendung des Rank-One-Update 8.3. Prüfung von Matrizen auf Primitivität 8.4. Berechnung der Google Matrix
1. Abstrakt¶
Der PageRank Algorithmus ist ein mathematisches Verfahren zur Bewertung und Gewichtung von verlinkten Dokumenten wie beispielsweise Internetseiten. Der Algorithmus wurde im Jahr 1988 von Lawrence Edward Page an der Standford Universität in den Vereinigten Staaten von Amerika entwickelt und von dieser auch zum Patent angemeldet [Ref 1].
Der Algorithmus diente der initialen Version der Google Suche zur Bewertung von Internetseiten des World Wide Web und avancierte das Unternehmen Google LLC. zu einem der erfolgreichsten Unternehmen der Welt. [Ref 2]
Die nachfolgenden Kapitel sollen nun auf die mathematischen Ursprünge des PageRank Algorithmus, effiziente Berechnungsmöglichkeiten und eventuell auftretende Probleme und Lösungsmöglichkeiten eingehen.
2. Theoretisches Modell¶
2.1. Grundlegendes Konzept¶
Ein Netzwerk wie beispielsweise das Internet kann als gerichteter Graph dargestellt werden. Ein Knoten entspricht dabei einer einzelnen Seite und ein Pfeil einem Hyperlink zu einer anderen Seite.
Die nachfolgende Illustration modelliert ein solches beispielhaftes Netzwerk aus einzelnen Seiten als gerichteten Graphen.
Abb. 1: Gerichteter Graph eines Netzwerks bestehend aus acht Seiten
Nun stellten sich die beiden Erfinder des PageRanks jedoch die Frage, wie die Definition einer relevanten Webseite genau aussehen könnte. Also vereinfacht ausgedrückt machten Sie sich Gedanken darüber, wie man die Relevanz einer Seite in einem Netzwerk mathematisch darstellen kann.
Aus dieser Fragestellung entstand das spätere grundlegende Konzept des PageRank Algorithmus, welches durch Google [Ref 3] selbst wie folgt zusammengefasst wird.
PageRank works by counting the number and quality of links to a page to determine a rough estimate of how important the website is. The underlying assumption is that more important websites are likely to receive more links from other websites.
Daraus folgt, dass der PageRank auf der Annahme basiert, dass eine relevante Seite viel mehr eingehende Hyperlinks von dritten Webseiten erhält, als weniger relevante Seiten.
2.2. Veranschaulichung durch Kreuzungen¶
Eine einfache Veranschaulichung des oben genannten Konzeptes bieten Kreuzungen im Straßenverkehr.
Abb. 2: Kartenansicht der Judge Harry Pregerson Interchange
Betrachtet man obigen Kartenausschnitt genauer, so sind in diesem eine Vielzahl an einzelnen Kreuzungen zu erkennen, die jeweils durch einzelne Straßen miteinander verbunden sind.
Möchte man nun die Auswirkung einer Baustelle an einer solchen Kreuzung auf den Straßenverkehr vorhersagen, so lässt sich folgendes feststellen. Die Auswirkungen auf den Straßenverkehr sind umso größer, je relevanter die jeweilige Kreuzung ist und eine Kreuzung ist umso relevanter, je mehr einzelne Straßen zu ihr hinführen.
Eine Baustelle an der orangenen Kreuzung wird deshalb mit hoher Wahrscheinlichkeit zu einem größeren Stau führen, als eine Baustelle an einer kleineren grauen Kreuzung.
3. Mathematisches Modell¶
3.1. Die ursprüngliche Summenformel¶
Gemäß der Zusammenfassung des PageRank Algorithmus von Google basiert der PageRank $PR_{i}$ einer bestimmten Seite $i$ auf der Summe der PageRanks $PR_{j}$ der Seiten $j$, die einen Hyperlink auf die Seite $i$ gesetzt haben.
Wenn eine Seite $j$ allerdings auf mehrere Seiten verweist, so muss der PageRank der Seite $j$ gleichmäßig auf alle Seiten verteilt werden, die einen Verweis der Seite $j$ enthalten. Die ursprüngliche Summenformel kann daher wie folgt definiert werden.
\begin{align} \displaystyle PR_{i}=\sum _{P_{j} \in B_{P_{i}}}{\frac {PR_{j}}{|P_{j}|}} \end{align}Diese Formel greift zur Definierung des PageRank $PR_{i}$ auf den PageRank $PR_{j}$ der Seite $j$ zurück. Der PageRank der Seite $j$ ist jedoch nicht bekannt, weshalb die Formel abgeändert werden muss.
Zur Lösung des Problems wird jeder Seite im Netzwerk ein initialer PageRank von $\displaystyle \frac{1}{n}$ zugewiesen, wobei $n$ der Anzahl der Seiten des Netzwerkes entspricht. Dies führt nun zu folgender angepassten iterativen Definition.
\begin{align} \displaystyle PR_{k+1}(i)=\sum _{P_{j} \in B_{P_{i}}}{\frac {PR_{k}(j)}{|P_{j}|}} \end{align}Diese Iteration wird nun so lange fortgesetzt, bis $PR_{k+1}(i)$ konvergiert und sich nicht mehr ändert. (vgl. Langville, et. al. 2006, S. 32) [Ref 7]
3.2. Netzwerk als Hyperlink Matrix¶
Die obigen Summenformeln können in Form von Matrizen dargestellt werden. Hierzu definiert man einen neuen Vektor $\pi$, wobei das $i$-te Elemente des Vektors dem PageRank $PR_{i}$ der Seite $i$ entspricht. Dieser Vektor kann auch als stationärer Zustand bzw. Eigenvektor zum größten Eigenwert $1$ der Matrix angesehen werden.
Weiterhin entspricht $H$ der Hyperlink Matrix, dessen Element an der Stelle $ij$ genau dann dem Wert $\frac{1}{|P_{i}|}$ entspricht, wenn ein Link von Seite $P_{i}$ zu $P_{j}$ existiert. Die führt zu folgender neuen Formel in Matrixschreibweise.
\begin{align} \displaystyle \pi = \pi H \end{align}Bei der Matrix $H$ handelt es sich um eine $n \times n$ Matrix, wobei $n$ der Anzahl von Seiten entspricht. Diese Gleichung könnte nun auch wieder wie bei der angepassten Summenformel über den iterativen Weg berechnet werden, da die Matrix hauptsächlich aus Nullen besteht und daher dünn besetzt ist. (vgl. Armstrong 2012, S. 16) [Ref 6]
Hinweis: Ein Beispiel zur Anwendung der iterativen Methode zur Berechnung des PageRanks über die Hyperlink Matrix findet sich in Appendix 8.1.
3.3. Probleme der Hyperlink Matrix¶
Das Problem der Matrix $H$ besteht darin, dass sie Nullzeilen enthalten kann. Diese werden in der Fachsprache auch als sogenannte Dangling Nodes bezeichnet, was bedeutet, dass die korrespondierenden Seiten keine ausgehenden Links besitzen. Wenn eine Seite allerdings ausgehende Links besitzt, so entspricht die Zeilensumme dem Wert $1$.
Die Erfinder des PageRank Algorithmus haben das Problem gelöst, indem sie alle Nullzeilen mit Zeilen bestehend aus dem Wert $\frac{1}{n}$ ausgewechselt haben. Sollte nun ein zufälliger Surfer auf eine Dangling Node treffen, so wählt er mit einer Wahrscheinlichkeit von $\frac{1}{n}$ eine neue zufällige Seite im gesamten Netzwerk aus.
Um diese Operation durchzuführen, wurde durch die Entwickler des Algorithmus eine neue Matrix $S$ eingeführt. Dabei entspricht der Vektor $d$ einem Spaltenvektor, wobei das $i$-te Elemente des Vektors folgende Werte annimmt
\begin{align} \displaystyle d_{i} = { \begin{cases} \displaystyle 1,&{\text{falls Seite }}i{\text{ einer Dangling Node entspricht.}} \\ 0,&{\text{sonst}} \end{cases}} \end{align}Anschließend wird die Matrix $H$ durch ein Rank-One-Update wie folgt ersetzt, wobei der Zeilenvektor $e$ dem Einsvektor entspricht. (vgl. Langville, et. al. 2006, S. 37) [Ref 7]
\begin{align} S := H + \frac{1}{n}de^{T} \end{align}Die stochastische Matrix $S$ wird nun als Markov-Kettenmatrix bezeichnet, da die die Zeilensummen jeweils $1$ betragen. Die einzelnen Einträge der Matrix ungleich $0$ entsprechen dabei der Wahrscheinlichkeit, eine von der Seite $i$ verlinkte Seite $j$ zu besuchen.
Hinweis: Ein Beispiel zur Anwendung des Rank-One-Update findet sich in Appendix 8.2.
3.4. Probleme der stochastischen Matrix¶
Auf den ersten Blick mögen die Anpassungen der Matrix $H$ bereits zur Berechnung des PageRank genügen. Betrachtet man jedoch den nachfolgenden Graphen genauer, so stellt man fest, dass die stochastische Matrix noch nicht in einer Form vorliegt, die zur generellen Berechnung des PageRank eingesetzt werden kann.
Abb. 3: Netzwerk bestehend aus einem autarken Subnetz
Nach Überführung des Graphen in eine Übergangsmatrix hat diese die folgende Form.
\begin{align} S = \begin{bmatrix} 0 & \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & \frac{1}{2} & 0 & 0 & \frac{1}{2} & 0 & 0 & 0 \\ 0 & \frac{1}{3} & 0 & 0 & \frac{1}{3} & \frac{1}{3} & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & \frac{1}{2} & 0 & 0 & \frac{1}{2} \\ 0 & 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} & 0 \end{bmatrix} \quad \textrm{ wobei } \quad \pi_{k}^{T} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0.12 \\ 0.24 \\ 0.24 \\ 0.4 \end{bmatrix} \end{align}Dabei fällt auf, dass die ersten vier Seiten des stationären Zustandsvektors $\pi_{k}$ den PageRank $0$ haben. Die Erklärung liegt hierfür im nachfolgend blau markierten Bereich des Graphen.
Abb. 4: Netzwerk bestehend aus einem autarken Subnetz
Wenn ein zufälliger Surfer erst einmal auf die Seite $5$ oder $6$ gestoßen ist, kommt er aus der blau markierten Seitenstruktur nicht mehr heraus und die PageRanks der Seiten links des Subnetzes fließen zum rechten Subnetz ab.
Irreduzibilität von Matrizen:
Der in der Matrix $S$ beobachtbare Vorgang tritt bei reduziblen Matrizen auf. Reduzibel bedeutet in diesem Kontext, dass die Matrix $S$ in die nachfolgend dargestellte Blockdreiecksform $V$ gebracht werden kann. [Ref 5]
\begin{align} V = \begin{bmatrix} * & 0 \\ * & * \end{bmatrix} \end{align}Die $0$ der Matrix $V$ korrespondiert in diesem Fall mit der $4 \times 4$ Blockmatrix in der linken unteren Ecke von $S$.
Damit für den stationären Zustand garantiert werden kann, dass dieser nur positive Werte enthält, ist
eine Irreduzibilität der Matrix $S$ als Eigenschaft Voraussetzung. Das entsprechende Netzwerk muss deshalb
strongly connected sein, damit die dazugehörige Übergangsmatrix irreduzibel ist. [Ref 4]
Primitivität von Matrizen:
Eine weitere Voraussetzung für die Matrix $S$ ist die Primitivität. Sie garantiert, dass der zweite Eigenwert $|\lambda_{2}| < 1$ (vgl. Backaker 2012, S. 6 ff.) [Ref 9] ist, da dieser eine wichtige Rolle bei der Konvergenz des stationären Zustands spielt. [Ref 4]
Hinweis: Ein Beispiel zur Prüfung von Matrizen auf Primitivität findet sich in Appendix 8.3.
3.5. Herleitung der Google Matrix¶
Bis zum aktuellen Zeitpunkt, wird das Bewegungsmuster eines zufälligen Surfers durch die Matrix $S$ definiert. Dabei folgt der zufällige Surfer entweder den ausgehenden Links einer Seite oder wählt, wenn es sich um eine Dangling Node handelt, zufällig eine andere Seite innerhalb des Netzwerks aus.
Befindet sich ein Surfer jedoch zur Zeit auf der Webseite example.com, so kann er in die
Adressleiste seines Browsers jederzeit example.net eingeben und auf diese Seite wechseln,
ohne dass eine Verbindung zwischen den beiden Seiten existiert.
Um nun eine realistischere Darstellung des zufälligen Surfers zu erreichen, haben Page und Brin den sogenannten Dämpfungsfaktor $\alpha$ in den Algorithmus integriert, um das Bewegungsmuster des zufälligen Surfers weitaus realistischer zu gestalten.
Der neu definierte Parameter liegt dabei im Intervall $0<\alpha<1$ und wird in der Praxis meist mit $0.85$ angegeben, was bedeutet, dass ein Surfer mit einer Wahrscheinlichkeit von $85$ % den Verlinkungen auf einer Seite folgen wird. Die restlichen $15$ % entsprechen dann der Wahrscheinlichkeit, dass der Surfer auf eine komplett neue zusammenhanglose Seite im Internet wechseln wird.
Mit Hilfe der obigen Annahmen kann nun eine neue Matrix $G$ definiert werden, die im Fachjargon auch als Google Matrix bezeichnet wird. Sie erfüllt die Voraussetzung der gleichzeitigen Irreduzibilität und Primitivität. [Ref 4]
\begin{align} G := \alpha S + (1-\alpha) \frac{1}{n} e e^{T} \end{align}Diese Matrix sollte jedoch nicht in ihrer jetzigen Form verwendet werden, da es sich dabei nicht mehr um eine dünn besetzte Matrix handelt. Aus diesem Grund wird die Definition der Google Matrix wie folgt abgeändert.
\begin{align} G &= \alpha S + (1-\alpha) \frac{1}{n} e e^{T} \\ &= \alpha \Big(\underbrace{H + \frac{1}{n}de^{T}}_{= S}\Big) + (1 - \alpha)\frac{1}{n}ee^{T} \\ &= \alpha H + \alpha d \frac{1}{n} e^{T} + (1 - \alpha)\frac{1}{n}ee^{T} \\ &= \alpha H + \Big(\alpha d + (1 - \alpha)e\Big)\frac{1}{n}e^{T} \end{align}Hinweis: Ein Beispiel zur Berechnung der Google Matrix findet sich in Appendix 8.4.
3.6. Berechnung des PageRanks durch Power Method¶
Bei der Power Method, auch Vektoriteration genannt, wird ein initialer Startvektor $\pi_{0} = \frac{1}{n}e$ mehrmals mit der Google Matrix multipliziert. Wenn sich der Vektor nach einer gewissen Zeit nicht mehr ändert, so ist der Vektor konvergiert und der stationäre Zustand wurde erreicht.
Dabei gilt es allerdings zu beachten, dass die Google Matrix mindestens 25 Milliarden Einträge besitzt, weshalb die Berechnung so effizient wie möglich ablaufen muss. Aus diesem Grund wird im folgenden Schritt die Google Matrix schrittweise durch die dünn besetzte Hyperlink Matrix ersetzt. (vgl. Armstrong 2012, S. 18) [Ref 6]
\begin{align} \pi_{k+1} = \alpha \pi_{k} H + \frac{1}{n} \Big(\alpha \pi_{k} d + 1 - \alpha\Big)e \end{align}Die meisten Einträge der Matrix $H$ sind $0$, da eine Seite meist nicht auf mehr als $10$ andere Seiten verweist, was die gesamte Berechnung durch die Power Method besonders effizient macht.
Weiterhin wurde der Dämpfungsfaktor $\alpha = 0.85$ gewählt. Durch diese Wahl werden laut den Entwicklern des PageRank nur etwa $50 - 100$ Iterationen benötigt, um eine gute Approximation für den Vektor $\pi_{k+1}$ zu erhalten. [Ref 4]
4. Implementierung des PageRank Algorithmus¶
Nachfolgend wird die erforderliche Klasse zur Berechnung des PageRanks implementiert.
# Die Basisklasse des PageRank Algorithmus
class PageRank:
def __init__(self, config):
assert("dampening_factor" in config), "Bitte übergeben Sie einen Dämpfungsfaktor im Intervall [0, 1]."
assert("hyperlink_matrix" in config), "Bitte übergeben Sie eine quadratische Hyperlink Matrix."
# Prüft, dass der Dämpfungsfaktor im erlaubten Intervall liegt.
assert(0 < config["dampening_factor"] < 1), "Der Dämpfungsfaktor muss im Intervall [0, 1] liegen."
# Prüft, dass die Hyperlink Matrix einer quadratischen Matrix entspricht.
assert(config["hyperlink_matrix"].dimensions()[0] == config["hyperlink_matrix"].dimensions()[1]), "Die Hyperlink Matrix muss quadratisch sein."
# Legt die Hyperlink Matrix fest.
self.hyperlink_matrix = matrix(config["hyperlink_matrix"])
# Legt den Dämpfungsfaktor fest.
self.dampening_factor = config["dampening_factor"]
# Legt die Anzahl der Seiten im Netzwerk fest.
self.number_of_pages = self.number_of_pages()
# Erstellt einen Einsvektor mit genauso vielen Einträgen, wie Seiten im Netzwerk existieren.
self.one_vector = self.one_vector()
# Erstellt einen Dangling-Node Vektor.
self.dangling_node_vector = self.dangling_node_vector()
def one_vector(self):
"""
Definiert einen Einsvektor mit n Einträgen.
"""
n = self.number_of_pages
return vector([1 for el in range(n)])
def dangling_node_vector(self):
"""
Erstellt einen Vektor, der abbildet, in welcher Zeile eine Matrix eine Dangling-Node besitzt.
"""
hyperlink_matrix = self.hyperlink_matrix
dangling_rows = list()
for row in hyperlink_matrix:
row_sum = 0 # Bildet die Summe einer Seite
for row_element in row:
row_sum += row_element
if(row_sum == 1):
dangling_rows.append(0) # Wenn die Summe der Zeile 1 ist, so handelt es sich um keine Dangling-Node
else:
dangling_rows.append(1) # Wenn die Summe der Zeile 0 ist, so handelt es sich um eine Dangling-Node
return vector(dangling_rows)
def number_of_pages(self):
"""
Gibt die Anzahl der Seiten des Netzwerkes zurück.
"""
return self.hyperlink_matrix.dimensions()[0]
def stochastic_matrix(self):
"""
Erstellt eine stochastische Matrix ohne Dangling-Nodes.
"""
n = self.number_of_pages
d = self.dangling_node_vector
e = self.one_vector
H = self. hyperlink_matrix
S = H + (1/n)*d.column()*e.row()
return S.n(digits=3)
def google_matrix(self):
"""
Berechnet eine primitive und irreduzible Google Matrix.
"""
a = self.dampening_factor
n = self.number_of_pages
d = self.dangling_node_vector
e = self.one_vector
H = self.hyperlink_matrix
G = a*H + (a*d.column() + (1 - a)*e.column())*(1/n)*e.row()
return G.n(digits=3)
def calculate(self):
"""
Berechnet den PageRank mit Hilfe der Formel der Power Method.
"""
a = self.dampening_factor
n = self.number_of_pages
d = self.dangling_node_vector
e = self.one_vector
H = self.hyperlink_matrix
# Initialer Vektor
pi = vector([1/n for p in range(1, n + 1)])
# Iterationen
for iterations in range(20):
pi = a*pi*H + (1/n)*(a*pi*d + 1 - a)*e
# Rückgabe des stationären Zustands
return pi.n(digits=3)
5. Anwendung und Veranschaulichung¶
Der nachfolgende Teilbereich wird anschließend auf die Verwendung der einzelnen Klassen, sowie verschiedene unterstützende Veranschaulichungen eingehen.
# Bereitstellung der Basiskonfiguration des PageRanks
config = {
"dampening_factor": 0.9,
"hyperlink_matrix": matrix([
[0, 1/2, 1/2, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[1/3, 1/3, 0, 0, 1/3, 0],
[0, 0, 0, 0, 1/2, 1/2],
[0, 0, 0, 1/2, 0, 1/2],
[0, 0, 0, 1, 0, 0]
])
}
pagerank = PageRank(config)
5.1. Umwandlung der Hyperlink Matrix in eine stochastische Matrix¶
Der nun folgende Codeabschnitt wird die in der Basiskonfiguration übergebene Hyperlink Matrix in eine stochastische Matrix umwandeln, wobei die Zeilensumme jeweils $1$ beträgt.
print(pagerank.stochastic_matrix())
5.2. Konvertierung der stochastischen Matrix in die Google Matrix¶
Der folgende Funktionsaufruf wird die stochastische Matrix in eine primitive und irreduzible Google Matrix umwandeln.
print(pagerank.google_matrix())
print(pagerank.calculate())
6. Literaturverzeichnis¶
| [1] | Patent US6285999: Method for node ranking in a linked database. Veröffentlicht am 4. September 2001, Anmelder: The Board of Trustees of the Leland Stanford Junior University, Erfinder: Lawrence Page, Anmeldenr: US482798A, Veröffentlichungsnr: US6285999B1. |
| [2] | Solomon, Brian (2016): Google Passed Apple As The World's Most Valuable Company (Again). In: Forbes, 12.05.2016. Online verfügbar unter https://www.forbes.com/sites/briansolomon/2016/05/12/google-passed-apple-as-the-worlds-most-valuable-company-again/, zuletzt geprüft am 06.05.2020. |
| [3] | N.N. (2011): Facts about Google and Competition. Hg. v. Google LLC. Online verfügbar unter https://www.google.com/competition/howgooglesearchworks.html, zuletzt aktualisiert am 04.11.2011, zuletzt geprüft am 10.06.2020. |
| [4] | Austin, David (2006): How Google Finds Your Needle in the Web's Haystack. American Mathematical Society. Online verfügbar unter https://www.ams.org/publicoutreach/feature-column/fcarc-pagerank, zuletzt geprüft am 11.06.2020. |
| [5] | Wikipedia (Hg.) (2020): Irreduzible Matrix. Online verfügbar unter https://de.wikipedia.org/w/index.php?title=Irreduzible_Matrix&oldid=195556336, zuletzt aktualisiert am 06.01.2020, zuletzt geprüft am 11.06.2020. |
| [6] | Armstrong, Drew (2012): The Perron-Frobenius theorem. Chapter 9. Online verfügbar unter https://www.math.miami.edu/~armstrong/685fa12/sternberg_perron_frobenius.pdf, zuletzt geprüft am 11.06.2020. |
| [7] | Langville, Amy N.; Meyer, Carl D. (2006): Google's PageRank and beyond. The science of search engine rankings. Princeton, NJ: Princeton Univ. Press. Online verfügbar unter https://pdfs.semanticscholar.org/b591/ca7581cbfc6db92281a398cd23fc73638452.pdf, zuletzt geprüft am 06.06.2020. |
| [8] | Wikipedia (Hg.) (2020): Perron–Frobenius theorem. Online verfügbar unter https://en.wikipedia.org/w/index.php?title=Perron%E2%80%93Frobenius_theorem&oldid=961095623#Caveats, zuletzt aktualisiert am 06.06.2020, zuletzt geprüft am 12.06.2020. |
| [9] | Backaker, Fredrik (2012): The Google Markov Chain: convergence speed and eigenvalues. Online verfügbar unter https://uu.diva-portal.org/smash/get/diva2:536076/FULLTEXT01.pdf, zuletzt geprüft am 12.06.2020. |
7. Abbildungsverzeichnis¶
| [1] | Abb. 1 (Gerichteter Graph eines Netzwerks bestehend aus acht Seiten): Online verfügbar unter https://www.ams.org/featurecolumn/images/december2006/goodnet.jpg, zuletzt geprüft am 11.06.2020. |
| [2] | Abb. 2 (Kartenansicht der Judge Harry Pregerson Interchange): Online verfügbar unter https://w.wiki/TnA, zuletzt geprüft am 11.06.2020. |
| [3] | Abb. 3 (Netzwerk bestehend aus einem autarken Subnetz): Online verfügbar unter https://www.ams.org/featurecolumn/images/december2006/reducible.jpg, zuletzt geprüft am 11.06.2020. |
| [4] | Abb. 4 (Netzwerk bestehend aus einem autarken Subnetz): Online verfügbar unter https://www.ams.org/featurecolumn/images/december2006/reduciblewithbox.2.jpg, zuletzt geprüft am 11.06.2020. |
| [4] | Abb. 4 (Gerichteter Graph eines Netzwerks bestehend aus acht Seiten): Online verfügbar unter https://www.ams.org/featurecolumn/images/december2006/goodnet.jpg, zuletzt geprüft am 11.06.2020. |
8. Appendix¶
8.1. Anwendung der iterativen Methode¶
Das nachfolgende Beispiel soll die Anwendung der iterativen Methode zur Berechnung des PageRanks über die Hyperlink Matrix verdeutlichen.
Gegeben sei folgender Graph eines Netzwerks bestehend aus acht miteinander verknüpften Seiten.
Abb. 4: Gerichteter Graph eines Netzwerks bestehend aus acht Seiten
Die zu diesem Graph gehörende Hyperlink Matrix $H$ lautet daher.
Beachte: Um Platz zu sparen, wurde die transponierte Version für $\pi_{k}$ verwendet.
\begin{align} H = \begin{bmatrix} 0 & \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & \frac{1}{2} & 0 & 0 & \frac{1}{2} & 0 & 0 & 0 \\ 0 & \frac{1}{3} & 0 & 0 & \frac{1}{3} & \frac{1}{3} & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \frac{1}{3} & 0 & 0 & 0 & \frac{1}{3} & 0 & 0 & \frac{1}{3} \\ 0 & 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} & 0 \end{bmatrix} \quad \textrm{ wobei} \quad \pi_{k}^{T} = \begin{bmatrix} 0.0600 \\ 0.0675 \\ 0.0300 \\ 0.0675 \\ 0.0975 \\ 0.203 \\ 0.180 \\ 0.295 \end{bmatrix} \end{align}Die Berechnung des stationären Zustands $\pi_{k}$ erfolgt nun iterativ. Wie in nachfolgender Tabelle ersichtlich konvergiert $\pi_{k}$ nach $k = 61$ Iterationen.
| $\pi_{0}^{T}$ | $\pi_{1}^{T}$ | $\pi_{2}^{T}$ | $\pi_{3}^{T}$ | $\pi_{4}^{T}$ | $\cdots$ | $\pi_{60}^{T}$ | $\pi_{61}^{T}$ |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0.0278 | $\cdots$ | 0.06 | 0.06 |
| 0 | 0.5 | 0.25 | 0.1667 | 0.0833 | $\cdots$ | 0.0675 | 0.0675 |
| 0 | 0.5 | 0 | 0 | 0 | $\cdots$ | 0.03 | 0.03 |
| 0 | 0 | 0.5 | 0.25 | 0.1667 | $\cdots$ | 0.0675 | 0.0675 |
| 0 | 0 | 0.25 | 0.1667 | 0.1111 | $\cdots$ | 0.0975 | 0.0975 |
| 0 | 0 | 0 | 0.25 | 0.1806 | $\cdots$ | 0.2025 | 0.2025 |
| 0 | 0 | 0 | 0.0833 | 0.0972 | $\cdots$ | 0.18 | 0.18 |
| 0 | 0 | 0 | 0.0833 | 0.3333 | $\cdots$ | 0.295 | 0.295 |
Tabelle übernommen von [Ref 4]
Beginnt man nun den iterativen Prozess mit einem anderen initialen Vektor $\pi_{0}^{T}$, so lässt feststellen, dass der stationäre Zustand mit dieser Methode und Matrix von der Wahl des initialen Vektors abhängig ist.
8.2. Anwendung des Rank-One-Update¶
Das nachfolgende Beispiel soll die Anwendung des Rank-One-Update verdeutlichen.
\begin{align} H = \begin{bmatrix} 0 & \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ \frac{1}{3} & \frac{1}{3} & 0 & 0 & \frac{1}{3} & 0 \\ 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} \\ 0 & 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & 0 & 0 & 1 & 0 & 0 \end{bmatrix} \end{align}Die Zeile $h_{2*}$ entspricht hierbei einer Dangling Node. Um diese Zeile nun mit den Werten $\frac{1}{n}$ aufzufüllen, wird das Rank-One-Update durchgeführt.
\begin{align} S = \begin{bmatrix} 0 & \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ \frac{1}{3} & \frac{1}{3} & 0 & 0 & \frac{1}{3} & 0 \\ 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} \\ 0 & 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & 0 & 0 & 1 & 0 & 0 \end{bmatrix} + \frac{1}{6} \begin{bmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 \end{bmatrix} = \begin{bmatrix} 0 & \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 \\ \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} \\ \frac{1}{3} & \frac{1}{3} & 0 & 0 & \frac{1}{3} & 0 \\ 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} \\ 0 & 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & 0 & 0 & 1 & 0 & 0 \end{bmatrix} \end{align}Die Zeile $h_{2*}$, die der Dangling Node entsprochen hat, wurde nun mit den Werten $\frac{1}{6}$ aufgefüllt.
8.3. Prüfung von Matrizen auf Primitivität¶
Um eine Matrix auf Primitivität zu prüfen, kann der Satz von Perron-Frobenius angewendet werden. (vgl. Drew 2012, S. 2) [Ref 6]
Prüfungskriterien:
- Entweder man hebt die Matrix in die Potenz $k$ und prüft, ob alle Einträge der Matrix positiv sind. Ist dies der Fall, handelt es sich um eine primitive Matrix.
- Oder man betrachtet die Hauptdiagonalelemente der Ausgangsmatrix. Sind alle Hauptdiagonalelemente gleich $0$, so ist die Matrix nicht primitiv. [Ref 8]
Beispiel für eine primitive Matrix
Beispiel für eine nicht primitive Matrix
8.4. Berechnung der Google Matrix¶
Das nachfolgende Beispiel soll die Berechnung der Google Matrix verdeutlichen.
\begin{align} S = \begin{bmatrix} 0 & \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 \\ \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} \\ \frac{1}{3} & \frac{1}{3} & 0 & 0 & \frac{1}{3} & 0 \\ 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} \\ 0 & 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & 0 & 0 & 1 & 0 & 0 \end{bmatrix} \end{align}Die Berechnung der Google Matrix läuft nun für $\alpha = 0.9$ wie folgt ab.
\begin{align} G = 0.9 \begin{bmatrix} 0 & \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 \\ \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} \\ \frac{1}{3} & \frac{1}{3} & 0 & 0 & \frac{1}{3} & 0 \\ 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} \\ 0 & 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & 0 & 0 & 1 & 0 & 0 \end{bmatrix} + (1 - 0.9)\frac{1}{6} \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 \end{bmatrix} = \begin{bmatrix} \frac{1}{60} & \frac{7}{15} & \frac{7}{15} & \frac{1}{60} & \frac{1}{60} & \frac{1}{60} \\ \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} \\ \frac{19}{60} & \frac{19}{60} & \frac{1}{60} & \frac{1}{60} & \frac{19}{60} & \frac{1}{60} \\ \frac{1}{60} & \frac{1}{60} & \frac{1}{60} & \frac{1}{60} & \frac{7}{15} & \frac{7}{15} \\ \frac{1}{60} & \frac{1}{60} & \frac{1}{60} & \frac{7}{15} & \frac{1}{60} & \frac{7}{15} \\ \frac{1}{60} & \frac{1}{60} & \frac{1}{60} & \frac{11}{12} & \frac{1}{60} & \frac{1}{60} \end{bmatrix} \end{align}Copyright (c) 2020 Stefan Kühnel. Alle Rechte vorbehalten, soweit nicht ausdrücklich anders vermerkt.