Aproximacion Matematica y computacional del motor de busqueda Google (PDF)

Tesis (Diplomatura) del año 2016 en eltema Ingeniería - Ingeniería informática, Nota: 15.94, , Idioma: Español, Resumen: 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.