Metode za pretraživanje weba

master's thesis

• Title (english): Web searching methods
• Author: Antonio Đurić
• Mentor: Ivana Šain Glibić (mentor)
• Committee member: Ivana Šain Glibić (predsjednik povjerenstva)
• Committee member: Zvonimir Bujanović (član povjerenstva)
• Committee member: Tina Bosner (član povjerenstva)
• Committee member: Aleksandra Čižmešija (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2022-09-27, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: Perron-Frobenijusov teorem; HITS metoda; PageRank metoda; Google matrice; prijelazne matrice Markovljevog lanca; SALSA metoda; spamming
• Keywords (english): Perron-Frobenius theorem; HITS method; PageRank method; Google matrix; transition matrices of the Markov chain; SALSA method; spamming
• Language: croatian
• URN:NBN: urn:nbn:hr:217:111978
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2022-10-26 09:17:25