Naslov Metode za pretraživanje weba
Naslov (engleski) Web searching methods
Autor Antonio Đurić
Mentor Ivana Šain Glibić (mentor)
Član povjerenstva Ivana Šain Glibić (predsjednik povjerenstva)
Član povjerenstva Zvonimir Bujanović (član povjerenstva)
Član povjerenstva Tina Bosner (član povjerenstva)
Član povjerenstva Aleksandra Čižmešija (član povjerenstva)
Ustanova koja je dodijelila akademski / stručni stupanj Sveučilište u Zagrebu Prirodoslovno-matematički fakultet (Matematički odsjek) Zagreb
Datum i država obrane 2022-09-27, Hrvatska
Znanstveno / umjetničko područje, polje i grana PRIRODNE ZNANOSTI Matematika
Sažetak Ukratko, u ovom radu se bavimo metodama za pretraživanje weba. Obrađene metode za pretraživanje weba su bazirane na pronalasku svojstvenog vektora matrice. U prvom poglavlju obrađena je metoda potencija koja je ključna za sve tri metode za pretraživanje weba. Također, u prvom poglavlju se govori o Perron-Frobenijusovoj teoriji. Glavni rezultat prvog poglavlja je Perron-Frobenijusov teorem koji je potreban za raspravu o jedinstvenosti rješenja metoda za pretraživanje weba. Svako od sljedeća tri poglavlja predstavlja pojedinu metodu za pretraživanje weba. U drugom poglavlju opisujemo HITS metodu. Metoda HITS definira takozvane hubove (eng. hubs) i autoritete (eng. authorities). Definiramo i pojam matrice susjedstva koju, uz pomoć metode potencija, koristimo za dobivanje poretka stranica prilikom pretraživanja weba. U trećem poglavlju promatra se PageRank metoda. Metoda PageRank svakoj stranici pridružuje PageRank vrijednost koja mjeri relevantnost neke stranice. PageRank metoda se bazira na ideji je da linkovi s važnijih stranica nose veću težinu od onih s manje važnih stranica. Također, u poglavlju o PageRank metodi prikazan je Markovljev model weba u kojem vidimo direktnu poveznicu izmedu PageRank-ove Google matrice i prijelazne matrice Markovljevog lanca. U četvrtom poglavlju opisuje se SALSA metoda. SALSA metoda nastoji zadržati prednosti HITS i PageRank metode zajedno te ih kombinirati. SALSA metoda se bazira na izgradnji bipartitnog neusmjerenog grafa iz kojeg se grade dva Markovljeva lanca. Pomoću prijelaznih matrica ta dva Markovljeva lanca i metode potencija dobivamo poredak stranica za traženo pretraživanje weba. U svakom od poglavlja govori se o konvergenciji metode, prednostima i manama metoda te je za svaku metodu naveden manji primjer. U zadnjem poglavlju, na većem primjeru, usporedujemo sve tri metode. Zaključujemo kako je SALSA metoda uspjela popraviti glavne nedostatke HITS metode. Ipak, smatramo da dvojni poredak SALSA metode nije ni približno dovoljna prednost spram PageRank metode koja je bolja u svim ostalim segmentima. Rad završava raspravom o otpornosti metoda na spamming u kojoj se vidi osjetljivost HITS i SALSA metode. Rad završavamo s primjerom u kojem vidimo da i PageRank metoda nije otporna na posebne vrste spamming-a.
Sažetak (engleski) In this work, we are studying web searching methods. The methods we studied are based on finding the eigenvector of a matrix. In chapter one we presented the power method, which is the starting point for all the three presented web searching methods. Chapter one also considers Perron-Frobenius theory and gives the Perron-Frobenius theorem which is the main factor in discussing uniqueness of the solution provided by the web searching methods. The following three chapters present each of the studied methods. Chapter two describes the HITS method which defines so called hubs and authorities. We also defined the adjacency matrix which is used for acquiring page ranking in searching the web, by using the power method. Chapter three portrays the PageRank method. The method assigns a PageRank score for every page which serves as a measurement of relativity. The basis of the PageRank method is the idea that links with higher relativity pages carry more weight than those less relevant. This chapter also provides the Markov web model which shows the direct link between the Google matrix’s PageRank and the transition matrix of a Markov chain. Chapter four introduces the SALSA method which tries to hold advantages of both the HITS method and the PageRank method while combining the two. The SALSA method is based on building the bipartite undirected graph which is used for building two Markov chains. Using the transition matrices of the two Markov chains and the power method, we can get the page ranking for the requested searching of the web. Every chapter provides information about the method’s convergence, strengths, and faults, as well as a simple example that displays how does the method work. The final chapter offers a further example of all the methods combined. We concluded that the SALSA method achieved to fix the main disadvantages of the HITS method. Nevertheless, the dual ranking of the SALSA method is much less enough of an advantage to the PageRank method which exceeds in every other segment. This work concludes in a final discussion of the methods resilience to spamming which shows the HITS method’s and the SALSA method’s resilience to spamming. The final example of this work shows that the PageRank method isn’t resilient to special versions of spamming.
Ključne riječi
Perron-Frobenijusov teorem
HITS metoda
PageRank metoda
Google matrice
prijelazne matrice Markovljevog lanca
SALSA metoda
spamming
Ključne riječi (engleski)
Perron-Frobenius theorem
HITS method
PageRank method
Google matrix
transition matrices of the Markov chain
SALSA method
spamming
Jezik hrvatski
URN:NBN urn:nbn:hr:217:111978
Studijski program Naziv: Računarstvo i matematika Vrsta studija: sveučilišni Stupanj studija: diplomski Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
Vrsta resursa Tekst
Način izrade datoteke Izvorno digitalna
Prava pristupa Otvoreni pristup
Uvjeti korištenja
Datum i vrijeme pohrane 2022-10-26 09:17:25