Publicação
PageRank e pseudo-PageRank : convergência do algoritmo e tratamento da rede com nodos pendentes
| datacite.subject.fos | Ciências Naturais::Matemáticas | pt_PT |
| dc.contributor.advisor | Albuquerque, Carlos Manuel Ribeiro | |
| dc.contributor.author | Matos, Adriana Cristina Farinha | |
| dc.date.accessioned | 2025-05-21T15:43:12Z | |
| dc.date.available | 2025-05-21T15:43:12Z | |
| dc.date.issued | 2025 | |
| dc.date.submitted | 2025 | |
| dc.description | Tese de Mestrado, Matemática, 2025, Universidade de Lisboa, Faculdade de Ciências | pt_PT |
| dc.description.abstract | Nesta dissertação, analisa-se detalhadamente a Matemática que está na base do método de ordenação de páginas da Web por relevância utilizado inicialmente pela Google, designado por PageRank e apresentado em [1] por S. Brin e L. Page. O método PageRank baseia-se fortemente em resultados da Teoria dos Grafos e da Teoria das Matrizes Não-Negativas, especialmente no Teorema de Perron-Frobenius, que inspira a solução ao problema inicial da falta de conexão forte da rede. Outros problemas são identificados e tratados também de forma minuciosa. A apresentação do problema do cálculo do vetor de PageRank envolve a exposição do teorema da convergência do método da potência e de duas provas de como este método pode ser aplicado para a obtenção do vetor de ranking, sendo a primeira a que encontramos em [12] e a segunda em [14]. É ainda exposto o algoritmo construído a partir do método da potência e apresentado o ponto de vista alternativo de D. F. Gleich [14], que depende da apresentação de um teorema fundamental da Teoria das Matrizes-M. A apresentação do problema da presença dos nodos pendentes na rede é feita com a exposição do conceito de problema de pseudo-PageRank, da adaptação do algoritmo anterior a este contexto e de várias formas possíveis de transformação deste problema num de PageRank, com base no artigo [14] e noutros artigos, tais como [21] e [25]. É ainda feita uma interpretação da solução apresentada por Brin e Page em [1]. | pt_PT |
| dc.description.abstract | In this dissertation, we analyze in detail the Mathemathics underlying the method of ordering webpages by relevance initially used by Google, called PageRank and presented in [1] by S. Brin and L. Page. The PageRank method relies heavily on results from the Graph Theory and the Theory of Nonnegative Matrices, especially the Perron-Frobenius Theorem, which inspires the solution to the initial problem of the lack of a strongly connected web graph. Other problems are identified and also thoroughly treated. The presentation of the problem of calculating the PageRank vector involves the exposition of the power method convergence theorem and two proofs of how this method can be applied to obtain the ranking vector, the first being found in [12] and the second in [14]. It is also exposed the algorithm built from the power method and presented the alternative point of view by D. F. Gleich [14], which depends on the presentation of a fundamental theorem of the Theory of M-Matrices. The presentation of the problem caused by the presence of dangling nodes in the web is done by exposing the concept of the pseudo-PageRank problem, the adaptation of the previous algorithm to this context and several possible ways of transforming this problem into a PageRank problem, based on article [14] as well as others, such as [21] and [25]. An interpretation of the solution presented by Brin and Page in [1] is also made. | pt_PT |
| dc.identifier.tid | 203947452 | pt |
| dc.identifier.uri | http://hdl.handle.net/10400.5/100884 | |
| dc.language.iso | por | pt_PT |
| dc.subject | Teoria dos Grafos | pt_PT |
| dc.subject | Teoria das Matrizes Não-Negativas | pt_PT |
| dc.subject | Teorema de Perron-Frobenius | pt_PT |
| dc.subject | Método da Potência | pt_PT |
| dc.subject | Teoria das Matrizes-M | pt_PT |
| dc.subject | Teses de mestrado - 2025 | pt_PT |
| dc.title | PageRank e pseudo-PageRank : convergência do algoritmo e tratamento da rede com nodos pendentes | pt_PT |
| dc.type | master thesis | |
| dspace.entity.type | Publication | |
| rcaap.rights | openAccess | pt_PT |
| rcaap.type | masterThesis | pt_PT |
| thesis.degree.name | Mestrado em Matemática | pt_PT |