About us | Lectures | Papers | Seminar | Examples | Programs | Download | Links | Contact


Težine vrhova kao unutarnje svojstvo usmjerenog grafa - Google Pagerank

Vrijeme: 11.4.2005, 16:15
Predavaonica: 108
Predavač: Dr. Goran Igaly
Naziv: Težine vrhova kao unutarnje svojstvo usmjerenog grafa - Google Pagerank
Opis:

Težine vrhova kao unutarnje svojstvo usmjerenog grafa - Google Pagerank

U potrazi za informacijom, mnogi se ljudi danas oslanjaju na Internet, a tražeći informacije na Internetu, većina se oslanja na najpopularniju svjetsku tražilicu - Google. Budući da Google (sustav od nekoliko desetaka tisuća računala) trenutno (ožujak 2005) u svojoj bazi ima indeksirano preko 8 milijardi web stranica, a prosječni korisnik prilikom potrage obraća pozornost na prvih desetak (eventualno dvadesetak) prikazanih rezultata, od izuzetne važnosti za masovnu prihvaćenost tražilice jest činjenica nalazi li se tražena stranica među tih prvih nekoliko rezultata.
Google za određivanje poretka pronađenih stranica koristi funkciju Pagerank koja svakoj web stranici pridružuje njenu težinu, a upravo ta težina je najvažniji (ali ne i jedini) čimbenik u određivanju poretka u prikazu rezultata pretraživanja.
Stvarna implementacija funkcije Pagerank je tajna i s vremenom se mijenja. Međutim, ono što je poznato jest njezin osnovni koncept, a to je određivanje težina vrhova kao jednoparametarskog unutarnjeg svojstva usmjerenog grafa. Odnosno, putem objavljenog dijela funkcije Pagerank, svaki usmjereni graf, do na jedan slobodni parametar (faktor prigušenja), na jedinstveni način određuje težine svojih vrhova. Pri tome web stranice predstavljaju vrhove, a poveznice (linkovi) lukove u tom grafu.
Djelovanje funkcije Pagerank će biti ilustrirano na primjerima malih grafova. Tako će, na primjer, djelovanje ove funkcije biti prikazano na svim neizomorfnim povezanim usmjerenim grafovima s tri vrha, te na nekoliko tipičnih konfiguracija koje se javljaju kao posljedica određenog načina postavljanja poveznica (linkova) na webu.
Kao ilustracija moguće manipulacije funkcijom Pagerank ("googlebombing") bit će izložen primjer "miserable failure" (upišite u Google da vidite o čemu je riječ) u kojemu je, ciljanom aktivnošću grupe ljudi, željena stranica (koja uopće ne sadrži traženi pojam) dovedena na prvo mjesto u prikazu rezultata pretraživanja. Na kraju predavanja bit će dana procjena stvarne opasnosti narušavanja vjerodostojnosti rezultata pretraživanja uzrokovana sličnim akcijama čiji je cilj utjecanje na djelovanje funkcije Pagerank.

<< Povratak na popis seminara