Arvostusalgoritmit verkostoanalyysissa
Liuttu, Janne (2012)
2012
Teknis-luonnontieteellinen koulutusohjelma
Luonnontieteiden ja ympäristötekniikan tiedekunta - Faculty of Science and Environmental Engineering
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2012-10-03
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tty-201210051310
https://urn.fi/URN:NBN:fi:tty-201210051310
Tiivistelmä
Internetin räjähdysmäinen kasvu on tehnyt entistä suuremmaksi haasteeksi löytää merkitykselliset ja luotettavat sivustot harmaasta massasta. Tähän tarkoitukseen on kehitetty erilaisia arvostusalgoritmeja, joilla pyritään asettamaan eri sivustot objektiiviseen paremmuusjärjestykseen. Merkittävämmät tällaiset algoritmit ovat Pagerank ja HITS, jotka molemmat ovat lähtöisin internetin hakukoneista, ja perustuvat internetin linkkirakenteeseen. Näiden algoritmien hyödyntämismahdollisuudet eivät kuitenkaan rajoitu ainoastaan internetin hakukoneisiin, ja näillä on käytännössä mahdollista tarkastella lähes minkälaista verkostoa tahansa.
Näiden arvostusalgoritmien matemaattinen käsittely perustuu pitkälti graafiteoriaan sekä matriisilaskentaan, graafiteorian tarjoten työkalut verkostojen mallinnukseen ja visualisointiin, ja matriisilaskennan luodessa pohjan arvostusten laskemiselle. Nämä kaksi matematiikan osa-aluetta nivoutuvat siististi yhteen, muodostaen elegantin kokonaisuuden arvostusalgoritmien käsittelylle.
Tässä diplomityössä perehdytään eri arvostusalgoritmeihin, sekä näiden matemaattiseen taustaan. Esimerkkidatana käytetään Tampereen teknillisen yliopiston vuoden 2010 opinto-oppaan kurssien esitietoketjuja, joista muodostuu käsiteltävä verkosto. Ilmiönä esitietoketjut eroavat jonkin verran internetin linkkirakenteesta, mutta tuloksissa havaitaan että algoritmit toimivat hyvin myös tämänkaltaisen verkoston tapauksessa. Pääsääntöisesti eri algoritmit tuottavat saman suuntaisia arvostuksia eri kursseille, mutta eri algoritmit painottavat kukin hieman eri asioita. Näin ollen eri algoritmien toiminnan tunteminen on ensiarvoisen tärkeää, kun pohditaan näiden hyödyntämistä eri ilmiöiden tarkastelussa.
Näiden arvostusalgoritmien matemaattinen käsittely perustuu pitkälti graafiteoriaan sekä matriisilaskentaan, graafiteorian tarjoten työkalut verkostojen mallinnukseen ja visualisointiin, ja matriisilaskennan luodessa pohjan arvostusten laskemiselle. Nämä kaksi matematiikan osa-aluetta nivoutuvat siististi yhteen, muodostaen elegantin kokonaisuuden arvostusalgoritmien käsittelylle.
Tässä diplomityössä perehdytään eri arvostusalgoritmeihin, sekä näiden matemaattiseen taustaan. Esimerkkidatana käytetään Tampereen teknillisen yliopiston vuoden 2010 opinto-oppaan kurssien esitietoketjuja, joista muodostuu käsiteltävä verkosto. Ilmiönä esitietoketjut eroavat jonkin verran internetin linkkirakenteesta, mutta tuloksissa havaitaan että algoritmit toimivat hyvin myös tämänkaltaisen verkoston tapauksessa. Pääsääntöisesti eri algoritmit tuottavat saman suuntaisia arvostuksia eri kursseille, mutta eri algoritmit painottavat kukin hieman eri asioita. Näin ollen eri algoritmien toiminnan tunteminen on ensiarvoisen tärkeää, kun pohditaan näiden hyödyntämistä eri ilmiöiden tarkastelussa.