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.
Índice General
I. INTRODUCCION
II. ANTECEDENTES
III. OBJETIVOS
A. OBJETIVO GENERAL
B. OBJETIVOS ESPECIFICOS
IV. JUSTIFICACION
CAPÍTULO I
MARCO TEÓRICO
1.1. FUNDAMENTOS MATEMATICOS
1.1.1. CADENA DE MARKOV
1.1.1.1. MATRIZ ESTACIONARIA
1.1.1.2. MATRIZ ESTACIONARIA EN VARIOS PASOS
1.1.1.3. CADENAS IRREDUCTIBLES
1.1.2. NORMA DE VECTORES
1.1.2.1. NORMALIZACION DE UN VECTOR
1.1.2.2. NORMA DE FROBENIUS
1.1.3. DEPENDENCIA E INDEPENDENCIA LINEAL
1.1.4. VALOR PROPIO Y VECTOR PROPIO
1.1.4.1. CALCULO DE VALORES PROPIOS
1.1.4.2. MULTIPLICIDAD ALGEBRAICA Y GEOMETRICA
1.1.4.3. CALCULO DE VECTORES PROPIOS
1.1.4.4. PROPIEDADES DE LOS VALORES PROPIOS [16] y [17]
1.1.4.5. PROPIEDADES DE LOS VECTORES PROPIOS [18]
1.1.5. MATRIZ DIAGONIZABLE
1.5.1.1. PROPIEDADES DE UNA MATRIZ DIAGONIZABLE [10] y [15]
1.1.6. TEOREMA DE PERRON-FROBENIUS
1.1.7. METODO DE LAS POTENCIAS
1.2. WEB CRAWLER
1.2.1. DEFINICION
1.2.2. BREVE HISTORIA DE LOS WEB CRAWLER
1.2.3. FUNCIONAMIENTO DE LOS WEBS CRAWLER
1.2.4. USO DE LOS WEB CRAWLERS
1.3. INTRODUCCION AL ENTORNO DE OPENWEBSPIDER(JS)V.0.2.3
1.3.1. REQUERIMIENTOS
1.3.2. CONFIGURACION
1.3.3. CONFIGURACION DE LA BASE DE DATOS
1.3.4. RASTEAR URLS
1.4. INTRODUCCION AL ENTORNO DE PAJEK
1.4.1. DEFINICIÓN
1.4.2. INICIANDO PAJEK
1.4.3. GENERANDO GRAFOS EN PAJEK
1.4.4. CENTRALIDAD
1.5. INTRODUCCION AL MATLAB
1.5.1. DEFICION
1.5.2. ENTORNO
1.5.3. OPERADORES BASICOS
1.5.4. DECLARACIÓN DE VARIABLES
1.5.5. MATRICES Y VECTORES
1.5.6. OPERACIONES ESPECIFICAS CON MATRICES
1.5.7. VALOR Y VECTOR PROPIO
1.5.8. PROGRAMACION EN MATLAB
1.6. BUSCADORES
1.6.1. DEFINICION
1.7. GOOGLE
1.7.1. BREVE HISTORIA DE GOOGLE [38].
1.7.2. MEDICION DE LA IMPORTANCIA DE UN DOCUMENTO WEB [36] y [39]
CAPÍTULO II
EL ALGOTIRMO DE ORDENACION DE GOOGLE
2.1. PLANTEAMIENTO DEL MODELO
2.2. EL ALGORITMO PAGERANK Y EL TEOREMA DE PERRON-FROBENIUS
2.3. CALCULO DEL VECTOR PAGERANK
CAPÍTULO III
PLANTEAMIENTO DE LOS CASOS DE ESTUDIO
3.1. CASO I: CALCULO DEL VECTOR DE IMPORTANCIAS
3.2. CASO II: CALCULO DEL PAGERANK CON EL METODO DE LAS POTENCIAS
CAPÍTULO IV
SIMULACIÓN
4.1. INICIAR EL RASTREO DE LA PAGINAS
4.2. CONSTRUIR EL ARCHIVO .NET DE PAJEK
4.3. CONSTRUIR EL GRAFO DE CONEXIONES EN PAJEK
4.4. CONSTRUCCIÓN DE LA MATRIZ DE ADYACENCIA
4.5. ASIGNACION DEL PAGERANK DE CADA NODO(VERTICE)
CAPÍTULO V
CONCLUSIONES Y RECOMENDACIONES
5.1. CONCLUSIONES
5.2. RECOMENDACIONES
BIBLIOGRAFÍA
Objetivos y Temas de Investigación
El objetivo principal de esta tesis es desarrollar una aproximación matemática y computacional del funcionamiento del buscador Google, centrándose especialmente en el algoritmo PageRank y su relación con la teoría de cadenas de Markov y el álgebra lineal para la ordenación de resultados web.
- Fundamentos matemáticos: Cadenas de Markov, valores y vectores propios.
- Funcionamiento de motores de búsqueda: Web Crawlers y arquitecturas de indexación.
- Simulación práctica: Integración de herramientas como OpenWebSpider, PAJEK y MATLAB.
- Modelización: Aplicación del teorema de Perron-Frobenius en el algoritmo de ordenación.
Auszug aus dem Buch
1.1.1. CADENA DE MARKOV
En esta sección se exponen algunos conceptos esenciales sobre cadenas de Markov¹ considerados necesarios para el desarrollo de la tesis. Se comenzará definiendo algunos conceptos esenciales para luego tratar brevemente las Cadenas de Markov propiamente dichas. Las definiciones y las propiedades aquí citados se encuentran en [1], [2] y [3]
Definición. Es un proceso estocástico a tiempo discreto {xn: n = 0,1,2 ...} con espacios de estados discretos S = {0,1, ...}, que sin pérdida de generalidad supondremos que consta de los primeros enteros a partir del 0 y que satisface la propiedad de Markov.
P(xn+1 = xn+1 | x0 = x0 ... xn = xn) = P(xn+1 = xn+1 | xn = xn) (1.1)
Esto es para cualquiera estado x0, x1 hasta xn+1 y para cualquier valor entero de n a partir de 0, la probabilidad que xn+1 tome el valor de xn+1, dado que el proceso ha pasado por los estados x0, x1 hasta xn, es simplemente la probabilidad del mismo evento dado xn = xn.
La propiedad de Markov significa que dado que se conoce la trayectoria del proceso hasta el tiempo n, la distribución de la variable xn+1 depende únicamente del ultimo valor observado, esto es xn y no de los valores anteriores (figura 1)
Resumen de Capítulos
MARCO TEÓRICO: Proporciona la base matemática necesaria, incluyendo cadenas de Markov, normas de vectores, autovalores, vectores propios y el funcionamiento de herramientas como Web Crawlers, PAJEK y MATLAB.
EL ALGOTIRMO DE ORDENACION DE GOOGLE: Presenta la modelización matemática del funcionamiento de búsqueda y la aplicación del teorema de Perron-Frobenius para definir la importancia de los nodos en la web.
PLANTEAMIENTO DE LOS CASOS DE ESTUDIO: Desarrolla la aplicación práctica del algoritmo PageRank en redes pequeñas para ilustrar el cálculo de importancia de páginas mediante matrices.
SIMULACIÓN: Detalla el proceso de rastreo real de un sitio web, la construcción de matrices de adyacencia y la simulación del cálculo de PageRank utilizando herramientas computacionales.
CONCLUSIONES Y RECOMENDACIONES: Sintetiza los resultados obtenidos sobre la eficacia del modelo y sugiere la integración de estas herramientas en la formación académica de la facultad.
Palabras Clave
Crawlers, PAJEK, Cadenas de Markov, Matriz estocástica, vector propio, método de las potencias, Google, PageRank, MATLAB, álgebra lineal, ordenación, simulación, teoría de grafos, matriz de adyacencia, nodos.
Preguntas Frecuentes
¿Cuál es el propósito fundamental de esta tesis?
El propósito es aproximar matemática y computacionalmente el funcionamiento del motor de búsqueda Google, explicando cómo utiliza el algoritmo PageRank para ordenar resultados basándose en la relevancia de las páginas.
¿Qué campos del conocimiento abarca el marco teórico?
Abarca principalmente el álgebra lineal, la teoría de procesos estocásticos (específicamente cadenas de Markov), el funcionamiento técnico de los Web Crawlers y el uso de software especializado para análisis de redes.
¿Qué importancia tiene el Teorema de Perron-Frobenius en el estudio?
Es crucial, ya que bajo ciertas condiciones garantiza la existencia y unicidad del vector de importancia (PageRank), permitiendo justificar matemáticamente la ordenación de los resultados de búsqueda.
¿Qué papel desempeñan las herramientas PAJEK y MATLAB?
PAJEK se utiliza para visualizar grafos de conexiones web y calcular centralidad, mientras que MATLAB se emplea para realizar los cálculos de álgebra lineal necesarios para determinar el vector PageRank mediante el método de las potencias.
¿Cómo se define la importancia de una página en el modelo propuesto?
Se define mediante un sistema de ecuaciones donde la importancia de una página es proporcional a la suma de las importancias de las páginas que la enlazan, modelado como un problema de autovector dominante.
¿Qué caracteriza a las palabras clave seleccionadas?
Los términos destacan la intersección entre el modelado matemático (vectores propios, Markov) y su aplicación técnica en la arquitectura de buscadores (Crawlers, PageRank).
¿Por qué se eligió el software OpenWebSpider para la simulación?
Se eligió por su capacidad para rastrear sitios web de forma automatizada y almacenar las relaciones entre páginas en una base de datos MySQL, facilitando así la obtención de la matriz de adyacencia necesaria.
¿Qué limitación importante sobre la irreducibilidad de la matriz se menciona?
Se observa que en casos reales la matriz de enlaces de la web puede ser reducible. Por ello, se explica cómo Brin y Page ajustaron el modelo para garantizar una matriz irreducible y estocástica que permita siempre converger a una solución.
- 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
