Computations of Google's PageRank

• Název práce v češtině: Výpočet Google PageRank
• Název v anglickém jazyce: Computations of Google's PageRank
• Klíčová slova: problémy vlastních čísel|PageRank|řešení lineárních systémů|numerické experimenty
• Klíčová slova anglicky: eigenvalue problems|PageRank|solving linear systems|numerical experiments
• Akademický rok vypsání: 2020/2021
• Typ práce: bakalářská práce
• Jazyk práce: angličtina
• Ústav: Katedra numerické matematiky (32-KNM)
• Vedoucí / školitel: doc. RNDr. Petr Tichý, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 09.10.2020
• Datum zadání: 09.10.2020
• Datum potvrzení stud. oddělením: 20.10.2020
• Datum a čas obhajoby: 14.06.2022 09:00
• Datum odevzdání elektronické podoby: 01.01.2022
• Datum odevzdání tištěné podoby: 16.05.2022
• Datum proběhlé obhajoby: 14.06.2022
• Oponenti: prof. Ing. Miroslav Tůma, CSc.

Zásady pro vypracování

Cílem práce je seznámit se s problematikou Google PageRanku a testovat numerické metody na jeho výpočet. Kromě klasické mocninné metody lze například použít i Arnoldiho metodu či metody pro řešení soustav lineárních rovnic s nesymetrickou maticí. Numerické experimenty budou prováděny v Matlabu.

Seznam odborné literatury

J. Brandts, M. Křížek, Lineární algebra ukrytá v internetovém vyhledávači Google, Pokroky matematiky, fyziky a astronomie, Vol. 52 (2007), No. 3, 195–204.
D. F. Gleich, PageRank beyond the web. SIAM Rev. 57 (2015), no. 3, 321–363.
M. Hejlová, Google PageRank: Relevance webových stránek a problém vlastních čísel, bakalářká práce, TU Liberec, 2015.
A. N. Langville, C. D. Meyer: Google’s PageRank and beyond. The science of search engine rankings, Princeton University Press, Princeton, 2006.
C. Moler, The World’s Largest Matrix Computation, MathWorks web, 2002, https://www.mathworks.com/company/newsletters/articles/the-world-s-largest-matrix-computation.html

Předběžná náplň práce

Úspěch firmy Google je spjat s vyhledávačem, který řadí výsledky vyhledávání podle jejich důležitosti a tím předkládá uživateli nejvíce relevantní informaci jako první. Za schopností ohodnotit důležitost stránky se skrývá matematický model Larryho Page a Sergeye Brina. Web je reprezentován Google maticí, do které se obtiskne jednak hyperlinková struktura webu a jednak pravděpodobnost, s jakou uživatel přejde na další stránku. Vektor důležitosti jednotlivých stránek (PageRank) pak lze spočíst jako vlastní vektor příslušný největšímu vlastnímu číslu Google matice. K výpočtu je používána mocninná metoda. Matematický model webu je navíc sestaven tak, aby mocninná metoda vždy konvergovala a lze předpovídat i rychlost její konvergence.

Cílem práce je seznámit se s problematikou Google PageRanku a testovat numerické metody na jeho výpočet. Kromě klasické mocninné metody lze například použít i Arnoldiho metodu či metody pro řešení soustav lineárních rovnic s nesymetrickou maticí. Testovací data (Google matice) jsou volně dostupná na internetu (například Hollins, Web-Stanford, Stanford-Berkeley matice). Testování numerických metod bude prováděno v Matlabu.