Aproximación matemática y computacional del motor de búsqueda Google

Abstract

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.

In the present dissertation project, the PageRank algorithm is presented in detail, retaking the Markov chain theory, considering some definitions and useful properties for the compression of the algorithm, as well as the method of the powers to obtain the eigenvalues and Dominant vectors of a stochastic matrix, as well as the Perron-Frobenius theorem that under certain conditions assures us the existence of the searched vector (PageRank vector); With the aim of providing a theoretical principle for the understanding of the algorithm. Then, in order to understand the different situations that the model may face, a simulation will be presented in this paper. In particular, we are interested in constructing an approximate Google-type search engine. In the first chapter of this thesis we will enunciate the mathematical foundation necessary for the understanding of the algorithm, we will explain Markov Chain, Vector norm, Dependence and linear independence, eigenvalues and eigenvectors, algebraic and geometric multiplicity, diagonizable matrix, Perron-Frobenius theorem And methods of the powers; Then we will detail Web Crawler definitions as well as its operation, making use of the OpenWebSpider software, then we will approach the software PAJEK, which allows us to visualize our web space analyzed by the Crawler and finally we will give a brief detail of the use of Matlab, in Particularly oriented to linear algebra. In the second chapter we will detail the sort algorithm used by Google and apply it mathematically, making a model approach. In the third chapter, through two case studies and two graphs associated with a network consisting of 5 and 4 pages, we will detail the Google ranking algorithm, using the definitions seen in the preliminary chapters. The last part will be dedicated to the simulation of the algorithm, for this we will detail the actions that will perform the Crawler, then through the integration between PAJEK and Matlab we generate the adjacency matrix, so finally applying functions and commands oriented to linear algebra in Matlab, We will simulate the operation of the Google search engine.

No presente projeto de teses é apresentado o algoritmo de Pagerank de forma detalhado retomando a teoria de Markov, contemplando algumas definições e propriedades úteis para a compresão de algoritmo, bem como o método das potências para a obtenção de valores próprios e vectores próprios dominantes de uma matriz estocástica, assim como o teorema de Perron-Frobenius que sob as circunstâncias assegura a existência do vetor buscado (PageRank do vetor); Com o objetivo de fornecer um princípio teórico para o entendimento de algoritmo. Enseguida, para fim de entender as diferentes situações que o modelo pode enfrentar, uma simulação será apresentado neste trabalho. Em particular estamos interessados em construir de forma aproximada um buscador tipo Google. Em primeiro capítulo de esta teses enunciaremos o cimento matemático necessário para o entendimento do algoritmo, vamos a explicar Cadeias de Markov, Norma de vetores, a dependência ea independência linear, os valores e os vetores próprios, a multiplicidade algebraica e geometrica, a matriz diagonalizável, o teorema de Perron-Frobenius e método de potências; Seguidamente detalaremos definições de Web Crawler assim como o funcionamento do mesmo, fazendo uso do software OpenWebSpider, depois abordaremos o software PAJEK, o que nos permite visualizar nosso espaço web analizado por o Crawler e finalmente daremos um breve resumo do uso do Matlab, em particular orientado al algebra linear. No segundo capítulo detalharemos o algoritmo de ordenação usado por Google e aplicá-lo matematicamente, fazendo um planejamento do modelo. No terceiro capítulo, por meio de casos de estudos e de análises associadas a uma rede que consta de cinco e quatro paginas, detalharemos o algoritmo de ordenamento do Google, usando as definições vistas nos capítulos preliminares. A última parte será dedicada a uma simulação do algoritmo, detalharemos as ações que realizaram o Crawler, em seguida através da integração entre PAJEK e Matlab generemos a matriz de adjacência finalmente aplicando funções e comandos orientados a álgebra linear em Matlab, simularemos o funcionamento do motor de busca Google.