Googlen PageRankin matematiikka
Authors
Date
2023Copyright
© The Author(s)
Tämän tutkielman tarkoituksena on esitellä matematiikkaa, johon Googlen hakutulosten järjestämiseen käyttämä PageRank-algoritmi perustuu. Tutkielmassa hyödynnetään lineaarialgebran, graafien ja Markovin ketjujen teorian yhteyksiä, joiden avulla algoritmin matemaattinen muoto saadaan esitettyä.
Hyvä hakukone tarjoaa hakutuloksissaan ensimmäisenä sellaisia sivuja, jotka ovat netinselaajan mielestä hyödyllisiä. Google-hakukone käyttää sivun tärkeyden selvittämiseen omaa PageRank-algoritmiaan, joka laskee jokaiselle nettisivulle tärkeysarvon eli PageRankin. Hakutulokset järjestetään tämän arvon perusteella suuruusjärjestykseen. Sivun PageRank määräytyy sivulle johtavien linkkien määrästä ja viittaavien sivujen tärkeydestä.
Algoritmi perustuu World Wide Webin linkkirakenteen esittämiseen suunnattuna graafina. Graafin informaatiosta muodostetaan matriisi, jonka itseisarvoltaan suurinta ominaisarvoa vastaava ominaisvektori on niin sanottu PageRank-vektori. Algoritmin tarkoituksena on saada selville tämä vektori, koska se pitää sisällään sivujen PageRankit. Ominaisarvon ja sitä vastaavaa vektorin laskeminen suoraan matriisin ominaisarvoyhtälöstä olisi kuitenkin liian työlästä, joten tätä varten työssä esitellään iteratiivinen prosessi nimeltä potenssimenetelmä, jossa mielivaltaisesti valittua aloitusvektoria kerrotaan toistuvasti edellä muodostetulla matriisilla.
Jotta menetelmää voidaan hyödyntää, täytyy ensin varmistua siitä, että sen avulla laskettava vektorijono suppenee. Tämä asettaa edellä muodostetulle matriisille tietyt vaatimukset. Tutkielmassa huomataan, että mikäli matriisi on muistittoman stokastisen prosessin primitiivinen siirtymämatriisi, potenssimenetelmällä muodostettu vektorijono suppenee kohti PageRank-vektoria, joka vastaa itse asiassa kyseisen stokastisen prosessin tasapainotilaa. Jonon suppenemisen ehtoja selvittäessä tutustutaan muun muassa redusoituviin matriiseihin, Perronin ja Frobeniuksen lauseeseen sekä Markovin ketjuihin.
...
![showless](/themes/JYX2//images/showless.png)
![showmore](/themes/JYX2//images/showmore.png)
Metadata
Show full item recordCollections
- Pro gradu -tutkielmat [29015]
License
Related items
Showing items with similar title or keywords.
-
Perronin ja Frobeniuksen lause
Huupponen, Tuukka (2023)Tässä tutkielmassa perehdytään matriisiteoriaan. Tarkastelu keskittyy neliömatriiseihin, niiden ominaisarvoihin ja niitä vastaaviin ominaisvektoreihin. Tarkastelu rajataan kahteen osaan, joista toiseen esitetään ... -
Kompleksiset vektoriavaruudet
Särkijärvi, Tuomas (2020)Tässä matematiikan pro gradu -tutkielmassa perehdytään kompleksisiin vektoriavaruuksiin ja sivutaan myös niiden sovelluskohteita. Tutkielman tavoitteena on esitellä riittävät tiedot, jotta lukija voi muodostaa eheän ... -
Matriisihajotelmia
Koskimäki, Saaga (2023)Tämän tutkielman tarkoituksena on tarkastella matriisin kolmea erilaista hajotelmaa. Matriisihajotelmien avulla matriisi voidaan esittää hyödyllisessä muodossa muita tuloksia varten. Tutkielmassa perehdytään matriisin ... -
On the convergence of unconstrained adaptive Markov chain Monte Carlo algorithms
Vihola, Matti (University of Jyväskylä, 2010) -
The Max-Product Algorithm Viewed as Linear Data-Fusion : A Distributed Detection Scenario
Abdi, Younes; Ristaniemi, Tapani (Institute of Electrical and Electronics Engineers (IEEE), 2020)In this paper, we disclose the statistical behavior of the max-product algorithm configured to solve a maximum a posteriori (MAP) estimation problem in a network of distributed agents. Specifically, we first build a ...