Publicación:
El Teorema de Perron-Frobenius y su influencia en los algoritmos de Google

Vista sencilla de ítem
dc.contributor.advisorFranco Leis, Daniel
dc.contributor.authorAparicio Durán, Jose Antonio
dc.date.accessioned2024-07-04T07:35:29Z
dc.date.available2024-07-04T07:35:29Z
dc.date.issued2024-06-27
dc.descriptionMáster universitario en Matemáticas Avanzadas. Especialidad en Matemática Aplicada
dc.description.abstractLa 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.es
dc.description.abstractThe 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.en
dc.identifier.citationAparicio Durán, Jose Antonio, 2024, El Teorema de Perron-Frobenius y su influencia en los algoritmos de Google
dc.identifier.urihttps://hdl.handle.net/20.500.14468/22818
dc.language.isoes
dc.publisherUniversidad Nacional de Educación a Distancia (UNED)
dc.relation.centerFacultades y escuelas::E.T.S. de Ingenieros Industriales
dc.relation.degreeMáster universitario en Matemáticas Avanzadas
dc.relation.departmentMatemática Aplicada I
dc.rightsinfo:eu-repo/semantics/openAccess
dc.rights.urihttps://creativecommons.org/licenses/by-nc-nd/4.0/deed.es
dc.subject12 Matemáticas
dc.titleEl Teorema de Perron-Frobenius y su influencia en los algoritmos de Googlees
dc.typetesis de maestríaes
dc.typemaster thesisen
dspace.entity.typePublication
Archivos
Bloque original
Mostrando 1 - 1 de 1
Miniatura
Nombre:
AparicioDuran_JoseAntonio_TFM.pdf
Tamaño:
2.93 MB
Formato:
Adobe Portable Document Format
Descargar
Bloque de licencias
Mostrando 1 - 1 de 1
No hay miniatura disponible
Nombre:
license.txt
Tamaño:
3.62 KB
Formato:
Item-specific license agreed to upon submission
Descripción:
Descargar
Colecciones
Trabajos de fin de máster (TFM)