Page Ranking,prezentare Generala

Importanta algoritmului

In general, cercetarile in motoarele de cautare depind de relevanta rezultatelor afisate. Majoritatea utilizatorilor folosesc un cuvand cheie sau o propozitie cheie in cercetarile lor. Utilizatorul nu are abilitatea si rabdarea necesara pentru a scana toate paginile care contin cuvantul cheie. Cu ajutorul algoritmului PageRanking , paginile vor fi afisate in motorul de cautare, in functie de importanta.

Motoarele noi de cautare utilizeaza astfel de metode, pentru a reda cele mai bune optiuni.Cel mai cunoscut algoritm este Page Rank. A fost inventat de Larry Page and Sergey Bin in anul 1998.

Ideea lor a fost ca fiecare pagina poate fi interpretata si judecata in functie de legaturile externe catre alte pagini. De exemplu, daca avem o pagina X si un hyperlink catre pagina Y, vom considera ca pagina Y este importanta pentru topicul de pe pagina X. Daca avem mai multe link-uri care duc catre pagina Y, asta inseama ca pagina Y are cea mai mare importanta.

Deci, caracteristicile importante ale algoritmului sunt stabilite dupa popularitate si au autoritate.Pentru a stabili page rankingul paginii,algoritmul utilizeaza deasemenea si accesarea aleatorie a legaturilor externe.

Aplicatii practice

Utilizat de Google pentru a determina importanta paginilor web

In domeniul de web mining

In retelele de internet ale lumii

Pentru sondaje de opinie

Pentu a stabili parametrii preturilor

In general acest algoritm se utilizeaza in toate domeniile care au la baza analiza concurentei.

Page Ranking, prezentare generala

Algoritmul PageRank (PR) este softul utilizat de Google pentru a calcula relevanta paginilor web.Aceasta se calculeaza in functie de cuvintele cheie introduse. Softul analizeaza numarul de link-uri legate la pagina principala si calitatea lor. Dupa o astfel de analiza se genereaza un set de masuratori intre 0 ( cel care are cea mai mica relevanta) si 10 ( pagina cu cea mai mare relevanta).

Cand vorbim de calitatea unei pagini, vorbim de o masuratoare abstracta la cat de importanta este pagina pentru subiectul de interes.

Pentru algoritm, link-urile sunt considerate a fi precum voturile, iar voturile se considera ca sunt unele mai importante ca altele. PR este un sistem ce numara link-urile votate si in functie de rezultate determina care pagina este mai importanta decat alta. Impreuna cu alte caracteristici care pot influenta rankingul, se va determina daca pagina va avea un ranking bun in timpul cautarii.

PR utilizeaza structura de link-uri ca un indicator pentru valoarea fiecarei pagini. Asadar, Google interpreteaza in modul urmator paginile :

Link-ul de la pagina A la pagina B este interpretat ca un vot de la pagina A pentru pagina B

Se analizeaza si pagina care ofera votul.

Pentru a indeplinii si conditiile impuse de utilizatori ( cuvantul cheie dupa care se fac cautarile), Google combina algoritmul PageRank cu o alta tehnica de «  potrivire a textului » pentru a gasi paginile care sunt relevante cautarilor efectuate.

Formula de calcul a algoritmului PageRanking este urmatoarea :

PR(A) = (1-d) + d (PR(T1)/C(T1) + … + +PR(Tn)/C(Tn))

PR (A) este Pagerankingul paginii A,

PR (Ti) este Pagerankingul paginilor Ti care au legatura catre pagina A,

C (Ti) este numarul de legaturi externe care ies din pagina Ti

d este factorul de amortizare, care poate sa ia valori intre 0 si 1.

Pentru a intelege principiul de functionare al algoritmului, vom urmari exemplul unui PR. Vom lua 2 pagini pe care le scriem sub forma unui graf. Fiecare nod este reprezentat de cate o pagina.

d= 0.85

PR(X)= (1 – d) + d(PR(Y)/1)

PR(Y)= (1 – d) + d(PR(X)/1)

Iar calculele pot continua.Calculele se vor repeta pana e va ajunge la valoarea 1.Atunci se va iesi din bucla.

PageRanking este considerat ca fiind modul de utilizare al unei persoane, unde persoana deschide legaturi externe la intamplare, fara a sti care este continutul siteului. Acest mod aleator de a deschide pagini poarta numele de « Random Surfer Model ». Surferul deschide aleator o pagina web, cu o certitudine probabila de a deriva PageRankingul paginii respective.

Probabilitatea ca utilizatorul unui site sa deschida un link aleatoriu este data exclusiv de numarul de legaturi externe pe care le are pagina respectiva. Aceasta probabilitate este reprezentata de suma probabilitatilor ca internautul sa deschida linkul care aceasta pagina.

Probabilitatea este redusa si modelata cu ajutorul factorului de amortizare d.

Atunci cand se calculeaza pagerankingul unui site, trebuie luat in considerare si faptul ca utilizatorul nu va deschide un numar infinite de lagaturi externe, el se va plictisi si va sari catre o alta pagina fara a tine cont de lagaturile existente.

Rezultate cunoscute si probleme/ Avantaje si dezavantaje

In urma analizelor efectuate, am ajuns la concluzia ca, pentru a creste PageRankingul unei pagini trebuie sa combinam cele doua modele (algoritmul PageRanking si algoritmul Random Surfer Model), utilizandu-le impreuna.

Ca orice algoritm, si algoritmul PageRanking are avantaje si dezavantaje.

Avantajul de baza al acestui algoritm este faptul ca reprezinta o unitate de masura globala si independenta.

Un dezavantaj important pentru cresterea PR-ului, sunt referintele circulare in pagina web, va permite reducerea PR-ului paginii principale.

Putem afirma faptul ca algoritmul reprezinta o masura securizata de calcul, deoarece este foarte dificil pentru proprietarul site-ului sa adauge anumite pagini pentru a creste popularitatea paginii sale.

Algoritmul favorizeaza paginile mai vechi, deoarece paginile noi nu au foarte multe legaturi externe catre alte pagini. Acest lucru poate fi considerat ca fiind un dezavantaj major, deoarece nu va exista egalitatea intre pagini.

Un hint pentru a creste PageRankingul pagii este de a folosi conceptul de «  link-farm « .

Set de date

Algoritmul PageRanking se poate utiliza in mai multe limbaje de programare. De exemplu vom gasi variante pentru Matlab, R, C++, Java,Phyton.

Mai jos veti gasi o bucata de exemplu de cod pentru algoritmul PR.

PageRank.java

import java.io.InputStream;

import java.net.URL;

import java.net.URLConnection;

import java.util.Random;

/**

* <b>PageRank provides simple API to Google PageRank Technology</b>

* Original source: http://www.temesoft.com/google-pagerank-api.jsp

* <br>

* PageRank queries google toolbar webservice and returns a

* google page rank.

*/

public class PageRank {

/**

* List of available google datacenter IPs and addresses

*/

static final public String [] GOOGLE_PR_DATACENTER_IPS = new String[]{

"64.233.183.91",

"64.233.189.44",

"66.249.89.83",

"toolbarqueries.google.com", // this is useful, and change "search" to "tbr"

};

/**

* Must receive a domain in form of: "http://www.domain.com"

* @param domain – (String)

* @return PR rating (int) or -1 if unavailable or internal error happened.

*/

public static int get(String domain) {

int dataCenterIdx = new Random().nextInt(GOOGLE_PR_DATACENTER_IPS.length);

int result = -1;

JenkinsHash jHash = new JenkinsHash();

String googlePrResult = "";

long hash = jHash.hash(("info:" + domain).getBytes());

String url = "http://"+GOOGLE_PR_DATACENTER_IPS[3]+"/tbr?client=navclient-auto&hl=en&"+

"ch=6"+hash+"&ie=UTF-8&oe=UTF-8&features=Rank&q=info:" + domain;

try {

URLConnection con = new URL(url).openConnection();

con.setConnectTimeout(10000);

InputStream is = con.getInputStream();

byte [] buff = new byte[1024];

int read = is.read(buff);

while (read > 0) {

googlePrResult = new String(buff, 0, read);

read = is.read(buff);

}

if (googlePrResult.equals(""))

return 0;

googlePrResult = googlePrResult.split(":")[2].trim();

result = new Long(googlePrResult).intValue();

} catch (Exception e) {

e.printStackTrace();

}

return result;

}

}

Rezultate si interpretare

In urma rularii programului, si a analizei, se observa faptul ca , chiar daca o pagina nu are nicio legatura externa catre o alta pagina, PageRankingul ei nu poate sa fie nul.

Cel mai mic PageRanking posibil pentru o pagina web este de 0,15.

Putem observa ca media PageRankingului pentru o rulare este de aproximativ 1.

Referinte

http://www.google.com/technology/

Lawrence Page, Motwani, « Bringing Order to the Web »

Andrew Clausen, «  Online Reputation System: the Cost of Attack of PageRank »