Computations of Google's PageRank
| Thesis title in Czech: | Výpočet Google PageRank |
|---|---|
| Thesis title in English: | Computations of Google's PageRank |
| Key words: | problémy vlastních čísel|PageRank|řešení lineárních systémů|numerické experimenty |
| English key words: | eigenvalue problems|PageRank|solving linear systems|numerical experiments |
| Academic year of topic announcement: | 2020/2021 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | angličtina |
| Department: | Department of Numerical Mathematics (32-KNM) |
| Supervisor: | doc. RNDr. Petr Tichý, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 09.10.2020 |
| Date of assignment: | 09.10.2020 |
| Confirmed by Study dept. on: | 20.10.2020 |
| Date and time of defence: | 14.06.2022 09:00 |
| Date of electronic submission: | 01.01.2022 |
| Date of submission of printed version: | 16.05.2022 |
| Date of proceeded defence: | 14.06.2022 |
| Opponents: | prof. Ing. Miroslav Tůma, CSc. |
| Guidelines |
| 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. |
| References |
| 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 |
| Preliminary scope of work |
| Ú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. |