Análisis del algoritmo PageRank: fundamento algebraico del orden de las búsquedas en Google

Amado Lapeña, Laura (2021). Análisis del algoritmo PageRank: fundamento algebraico del orden de las búsquedas en Google. Proyecto Fin de Carrera / Trabajo Fin de Grado, E.T.S.I. y Sistemas de Telecomunicación (UPM), Madrid.

Description

Title: Análisis del algoritmo PageRank: fundamento algebraico del orden de las búsquedas en Google
Author/s:
  • Amado Lapeña, Laura
Contributor/s:
  • Velasco Cebrián, María Pilar
Item Type: Final Project
Degree: Grado en Ingeniería de Sistemas de Telecomunicación
Date: July 2021
Subjects:
Freetext Keywords: Algoritmos; Páginas web; Motores de búsqueda
Faculty: E.T.S.I. y Sistemas de Telecomunicación (UPM)
Department: Matemática Aplicada a las Tecnologías de la Información y las Comunicaciones
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img] Archive (ZIP) - Users in campus UPM only
Download (604kB)
[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (2MB) | Preview

Abstract

Tras el título “Análisis del algoritmo PageRank: Fundamento algebraico del orden de las búsquedas en Google”, se encuentra el proyecto fin de grado con el que se pretende concluir los estudios del grado en Ingeniería de Sistemas de Telecomunicación en la Escuela Técnica Superior de Ingeniería y Sistemas de Telecomunicación. El algoritmo PageRank es utilizado en Google para clasificar los sitios web en los resultados de sus motores de búsqueda. PageRank permite medir la importancia de las páginas web. Aunque debe tenerse en cuenta que no es el único algoritmo utilizado por Google, es el primer algoritmo utilizado por la compañía, y a su vez, el más conocido. La base de este algoritmo consiste en un gran grafo dirigido, donde cada página web censada es un nodo. La relación entre los diferentes nodos sigue un camino aleatorio, conocido en inglés como “random walk”, de tal modo que entre los nodos se establecen diferentes relaciones de probabilidad. La información se recopila en matrices con ciertas propiedades, conocidas como matrices de transición de Márkov o matrices de un proceso de cadena de Márkov. Para conseguir ordenar los nodos del grafo es imprescindible encontrar la distribución estacionaria de esta cadena de Márkov. Además, ineludiblemente se debe realizar un estudio sobre los autovalores y autovectores de la matriz, o incluso el uso de alternativas como el teorema de punto fijo, debido a que estas matrices pueden presentar diferentes anomalías. La pretensión de este proyecto es describir qué es y cómo funciona el algoritmo PageRank mediante un profundo estudio y análisis de éste, con el fin de conocer la relación que guarda con Google y el álgebra lineal. Adicionalmente, se realizará una implementación de prototipo a pequeña escala del algoritmo PageRank mediante lenguaje de Matlab, con el objetivo de poder visualizar su funcionamiento. Para ello, se ha planteado realizar esta implementación de prototipo a través de la herramienta Matlab, ya que se utiliza en muchas de las asignaturas que se cursan a lo largo de todo el grado. Abstract: Behind the title "Analysis of the PageRank algorithm: algebraic foundation of the order of the searches in Google", there is the final project of the degree with which it is intended to conclude the studies of the degree in Telecommunications Systems Engineering at the Higher Technician College of Engineering and Telecommunication Systems. The PageRank algorithm is used by Google to classify websites in the results of their search engines. PageRank allows to measure the importance of web pages. Although it should be noted that it is not the only algorithm used by Google, but it is the first algorithm used by the company, and in turn, the best known. The basis of this algorithm consists of a large directed graph, where each census web page is a node. The relationship between the different nodes follows a random path, known as “random walk”, every node establishes relationships with different probability. The information is collected in matrices with certain properties, known as Márkov transition matrices or matrices of a Márkov chain process. To have the nodes of the graph ordered, it is essential to find the stationary distribution of this Márkov chain. In addition, a study on the eigenvalues and eigenvectors of the matrix, or even the use of alternatives such as the fixed point theorem, must inevitably be carried out, because these matrices can present different anomalies. The aim of this project is to describe what the PageRank algorithm is and how it works through a deep study and analysis of it, in order to know the relationship that it has with Google and linear algebra. Additionally, a small-scale prototype implementation of the PageRank algorithm will be carried out using Matlab language to visualize its operation. To do this, it has been proposed to carry out this prototype implementation through the Matlab tool, since it is used in many of the subjects that are taught throughout the degree.

More information

Item ID: 69141
DC Identifier: https://oa.upm.es/69141/
OAI Identifier: oai:oa.upm.es:69141
Deposited by: Biblioteca Universitaria Campus Sur
Deposited on: 29 Nov 2021 14:42
Last Modified: 29 Jan 2022 23:30
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM