A carregar...
Publicação
PageRank e pseudo-PageRank : convergência do algoritmo e tratamento da rede com nodos pendentes
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 364.5 KB | Adobe PDF |
Autores
Orientador(es)
Resumo(s)
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].
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.
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.
Descrição
Tese de Mestrado, Matemática, 2025, Universidade de Lisboa, Faculdade de Ciências
Palavras-chave
Teoria dos Grafos Teoria das Matrizes Não-Negativas Teorema de Perron-Frobenius Método da Potência Teoria das Matrizes-M Teses de mestrado - 2025