Googlen PageRankin matematiikka

Abstract

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.