En el presente proyecto de tesis se presenta al algoritmo de PageRank de forma detallada retomando la teoría de cadena de Markov, contemplando algunas definiciones y propiedades útiles para la compresión del algoritmo, bien como el método de las potencias para la obtención de los valores propios y vectores propios dominantes de una matriz estocástica, así como el teorema de Perron-Frobenius que bajo ciertas condiciones nos asegura la existencia del vector buscado (vector PageRank); con el objetivo de proveer un principio teórico para el entendimiento del algoritmo. Enseguida, a fin de entender las diferentes situaciones que el modelo puede enfrentar, una simulación será presentada en este trabajo. En particular estamos interesados en construir de manera aproximada un buscador tipo Google.
En el primer capítulo de esta tesis enunciaremos el cimiento matemático necesario para el entendimiento del algoritmo, explicaremos Cadena de Markov, Norma de vectores, Dependencia e independencia lineal, valores y vectores propios, multiplicidad algebraica y geométrica, matriz diagonizable, teorema de Perron-Frobenius y métodos de las potencias; seguidamente detallaremos definiciones de Web Crawler así como el funcionamiento del mismo, haciendo uso del software OpenWebSpider, luego abordaremos el software PAJEK, que nos permite visualizar nuestro espacio web analizado por el Crawler y finalmente daremos un detalle breve del uso del Matlab, en particular orientado al algebra lineal.
En el segundo capítulo detallaremos el algoritmo de ordenación usado por Google y lo aplicaremos matemáticamente, haciendo un planteamiento del modelo.
En el tercer capítulo, mediante dos casos de estudios y con dos grafos asociados con una red que consta de 5 y 4 páginas, detallaremos el algoritmo de ordenamiento de Google, empleando las definiciones vistas en los capítulos preliminares.
La última parte estará dedicada a la simulación del algoritmo, para ello detallaremos las acciones que realizará el Crawler, seguidamente mediante la integración entre PAJEK y Matlab generemos la matriz de adyacencia, para que finalmente aplicando funciones y comando orientados al algebra lineal en Matlab, simularemos el funcionamiento del motor de búsqueda Google.
Inhaltsverzeichnis
- Kapitel 1: Einleitung
- 1.1: Einführung in die Websuche
- 1.2: Bedeutung des PageRank-Algorithmus
- Kapitel 2: Mathematische Grundlagen
- 2.1: Einführung in die Theorie der Markov-Ketten
- 2.2: Vektor Normen
- 2.3: Lineare Abhängigkeit und Unabhängigkeit
- 2.4: Eigenwerte und Eigenvektoren
- 2.5: Algebraische und geometrische Vielfachheit
- 2.6: Diagonalisierbare Matrizen
- 2.7: Perron-Frobenius-Theorem
- 2.8: Potenzmethode
- Kapitel 3: Web-Crawling und -Analyse
- 3.1: Einführung in Web-Crawler
- 3.2: Funktionsweise von Web-Crawlern
- 3.3: Verwendung von OpenWebSpider
- 3.4: Visualisierung mit PAJEK
- 3.5: Verwendung von MATLAB für lineare Algebra
- Kapitel 4: Der PageRank-Algorithmus
- 4.1: Beschreibung des PageRank-Algorithmus
- 4.2: Mathematische Modellierung des Algorithmus
- Kapitel 5: Fallstudien und Simulation
- 5.1: Fallstudie 1: Netzwerk mit 5 Seiten
- 5.2: Fallstudie 2: Netzwerk mit 4 Seiten
- 5.3: Simulation des PageRank-Algorithmus
- 5.4: Integration von PAJEK und MATLAB
Zielsetzung und Themenschwerpunkte
Die vorliegende Dissertation befasst sich mit der mathematischen und rechnerischen Herangehensweise an den PageRank-Algorithmus, der die Grundlage der Google-Suche bildet. Ziel dieser Arbeit ist es, ein tiefgreifendes Verständnis des PageRank-Algorithmus zu vermitteln, indem die zugrundeliegende Theorie der Markov-Ketten beleuchtet und die praktische Implementierung mithilfe von Simulationen demonstriert wird.
- Mathematische Grundlagen des PageRank-Algorithmus
- Web-Crawling und -Analyse
- Praktische Anwendung des PageRank-Algorithmus
- Simulation des PageRank-Algorithmus mit MATLAB
- Integration von PAJEK und MATLAB für die Analyse von Webdaten
Zusammenfassung der Kapitel
Kapitel 1 bietet eine Einführung in die Websuche und die Bedeutung des PageRank-Algorithmus. Kapitel 2 behandelt die mathematischen Grundlagen des PageRank-Algorithmus, einschließlich der Theorie der Markov-Ketten, Vektor Normen, linearer Abhängigkeit und Unabhängigkeit, Eigenwerte und Eigenvektoren, der Perron-Frobenius-Theorem und der Potenzmethode. Kapitel 3 diskutiert Web-Crawling und -Analyse, wobei die Funktionsweise von Web-Crawlern erläutert wird, und die Verwendung von OpenWebSpider und PAJEK zur Analyse von Webdaten vorgestellt wird. Kapitel 4 beschreibt den PageRank-Algorithmus und seine mathematische Modellierung. Kapitel 5 führt Fallstudien und Simulationen des PageRank-Algorithmus durch, einschließlich der Integration von PAJEK und MATLAB für die Analyse von Webdaten.
Schlüsselwörter
PageRank-Algorithmus, Markov-Ketten, Web-Crawling, PAJEK, MATLAB, Eigenwerte, Eigenvektoren, Potenzmethode, Web-Analyse, Suchmaschinenoptimierung.
- Quote paper
- Julio Martin Rojas Tenazoa (Author), 2016, Aproximacion Matematica y computacional del motor de busqueda Google, Munich, GRIN Verlag, https://www.grin.com/document/437575
