Publicación: El Teorema de Perron-Frobenius y su influencia en los algoritmos de Google
Cargando...
Fecha
2024-06-27
Autores
Editor/a
Director/a
Tutor/a
Coordinador/a
Prologuista
Revisor/a
Ilustrador/a
Derechos de acceso
info:eu-repo/semantics/openAccess
Título de la revista
ISSN de la revista
Título del volumen
Editor
Universidad Nacional de Educación a Distancia (UNED)
Resumen
La importancia que ha tenido para el desarrollo de Internet es indiscu- tible. Sin embargo, es curioso pensar que el algoritmo PageRank, que hay detrás del buscador, tiene su fundamento matemático en un Teorema desarrollado a principios del siglo XX por el matemático Oskar Perron, inicialmente para matrices positivas y posteriormente extendido a matrices no negativas por el matemático Georg Frobe- nius. Dicho teorema permite garantizar que para una matriz no negativa e irreducible haya un autovalor positivo de módulo máximo que lleva asociado un autovector po- sitivo. Garantizar la existencia y unicidad de dicho autovector es lo que hace que el algoritmo de Google funcione, y haya permitido el desarrollo de aplicaciones que van más allá de un motor de búsqueda en Internet, como el estudio de la dinámica de po- blaciones, epidemiología, estudio de proteínas o análisis iterativo de matrices, entre otros.
Este trabajo no solo presenta los conceptos necesarios para comprender el Teo- rema de Perron-Frobenius, sino que también explica en detalle una de las múltiples demostraciones disponibles en la literatura, basada en el Teorema del punto fijo de Brouwer y con un enfoque geométrico. También se introducen las cadenas de Mar- kov, fundamentales para el desarrollo del algoritmo PageRank, y se propone un algo- ritmo para el cálculo del EdgeRank de las aristas de un grafo. Por último se muestra un ejemplo de implementación en Python de los algoritmos PageRank y EdgeRank.
The importance that has had for the development of the Internet is unde- niable. However, it is interesting to think that the PageRank algorithm, which is be- hind the search engine, has its mathematical foundation in a theorem developed in the early 20th century by the mathematician Oskar Perron, initially for positive matrices and later extended to non-negative matrices by the mathematician Georg Frobenius. This theorem guarantees that for a non-negative and irreducible matrix, there exists a positive eigenvalue of maximum modulus associated with a positive eigenvector. Ensuring the existence and uniqueness of this eigenvector is what makes Google al- gorithm work and has allowed the development of applications that go beyond an Internet search engine, such as the study of population dynamics, epidemiology, pro- tein research, or iterative matrix analysis, among others. This work not only presents the necessary concepts to understand the Perron- Frobenius Theorem, but also explains in detail one of the multiple proofs available in the literature, based on Brouwer’s fixed-point theorem and with a geometric ap- proach. Markov chains, which are fundamental for the development of the PageRank algorithm, are also introduced, and an algorithm for calculating the EdgeRank of the edges of a graph is proposed. Finally, an example implementation of the PageRank and EdgeRank algorithms in Python is shown.
The importance that has had for the development of the Internet is unde- niable. However, it is interesting to think that the PageRank algorithm, which is be- hind the search engine, has its mathematical foundation in a theorem developed in the early 20th century by the mathematician Oskar Perron, initially for positive matrices and later extended to non-negative matrices by the mathematician Georg Frobenius. This theorem guarantees that for a non-negative and irreducible matrix, there exists a positive eigenvalue of maximum modulus associated with a positive eigenvector. Ensuring the existence and uniqueness of this eigenvector is what makes Google al- gorithm work and has allowed the development of applications that go beyond an Internet search engine, such as the study of population dynamics, epidemiology, pro- tein research, or iterative matrix analysis, among others. This work not only presents the necessary concepts to understand the Perron- Frobenius Theorem, but also explains in detail one of the multiple proofs available in the literature, based on Brouwer’s fixed-point theorem and with a geometric ap- proach. Markov chains, which are fundamental for the development of the PageRank algorithm, are also introduced, and an algorithm for calculating the EdgeRank of the edges of a graph is proposed. Finally, an example implementation of the PageRank and EdgeRank algorithms in Python is shown.
Descripción
Máster universitario en Matemáticas Avanzadas. Especialidad en Matemática Aplicada
Categorías UNESCO
Palabras clave
Citación
Aparicio Durán, Jose Antonio, 2024, El Teorema de Perron-Frobenius y su influencia en los algoritmos de Google
Centro
Facultades y escuelas::E.T.S. de Ingenieros Industriales
Departamento
Matemática Aplicada I