|
ÀÁÐÀÊÀÄÀÁÐÀ (Òîæå ñàìîå íî â ÷èòàåìîì âèäå)
Bor'ba so spamom pri pomo6i algoritma TrustrankKratkoe izlojenie soderjania
Sozdateli stranic, v kotorix soderjitsa spam, pribegaut k razli4nim texnologiam dla dostijenia visokix rezul'tatov v vida4e. Est' special'nie eksperti, kotorie umeut identificirovat' spam, no danniy process dostato4no trudoemkiy i dorogostoa6iy. V svazi s etim predlagaetsa poluavtomati4eskaa texnologia viavlenia spama. Sna4ala otbiraetsa neskol'ko slu4aynix stranic, kotorie budut oceneni ekspertom. Identificirovav vru4nuu neskol'ko slu4ayno vibrannix stranic, v dal'ney6em ispol'zuetsa ssilo4naa struktura Interneta dla opredelenia drugix stranic, kotorie, skoree vsego, okajutsa «xoro6imi» i pravil'nimi stranicami. V dannoy rabote obsujdautsa vozmojnie sposobi slu4aynogo otbora i obnarujenia «xoro6ix» stranic. Predstavlautsa rezul'tati eksperimentov, provodimix v Internete i ocenka effektivnosti raboti texnologii. Rezul'tati pokazali, 4to su6estvuut effektivnie sposobi fil'tracii spama. 1. VVEDENIE Termin "internet-spam" ispol'zuut dla obozna4enia stranic, soderja6ix mnogo4islennie ssilki, special'no sozdannie dla vvedenia poiskovix sistem v zablujdenie. Naprimer, pornografi4eskiy sayt mojet sposobstvovat' rasprostraneniu spama v Internete, dobavlaa tisa4i klu4evix slov na doma6nuu stranicu, pri4em tekst za4astuu special'no delaetsa nevidimim dla pol'zovateley. Poiskovaa sistema indeksiruet dopolnitel'nie klu4evie slova i predostavlaet pornografi4eskuu stranicu v ka4estve otveta na zaprosi, soderja6ie eti slova. Tak kak dobavlennie klu4evie slova ne avlautsa nepristoynoy leksikoy, pol'zovateli popadaut na stranici takogo sayta. E6e odna texnika rasprostranenia spama – sozdanie bol'6ogo koli4estva poddel'nix veb-stranic, ukazivau6ix na edinstvennuu celevuu stranicu. V svazi s tem, 4to mnogie poiskovie sistemi u4itivaut koli4estvo vxoda6ix ssilok pri ranjirovanii stranic, celevaa stranica, skoree vsego, poavitsa ran'6e vsex v rezul'tatax poiska.
Vopros, avlaetsa li stranica ili gruppa stranic spamom (eto kasaetsa i elektronnoy po4ti), dostato4no sub&ektivniy. Naprimer, voz'mem neskol'ko saytov, neodnokratno ssilau6ixsa na stranici drug druga. Takie ssilki mogut prosto svidetel'stvovat' o sxodnoy tematike saytov, ili bit' sozdani special'no dla povi6enia ranjirovania stranic. Za4astuu dostato4no problemati4no opredelit', kakoy iz dvux scenariev bil ispol'zovan.
V celom, pol'zovateli legko raspoznaut avnie i neprikritie proavlenia spama. Naprimer, bol'6instvo soglasitsa, 4to esli osnovnaa 4ast' teksta na stranice nevidima pol'zovatelu i ne sootvetstvuet tematike, to, o4evidno, stranica bila dobavlena s namereniem vvesti poiskovuu sistemu v avnoe zablujdenie. To4no tak je delo obstoit, esli na stranice vstre4aetsa ogromnoe koli4estvo URL, ssilau6ixsa na takie xosti kak:
- buy-canon-rebel-300d-lens-case.camerasx.com;
- buy-nikon-d100-d70-lens-case.camerasx.com;
- …
osobenno, esli oni otnosatsa k odnomu IP adresu. Legko sdelat' vivod, 4to stranica special'no bila sozdana, 4tobi zaputat' poiskovie sistemi. (URL-spam osnovan na tom fakte, 4to mnogie poiskovie sistemi udelaut osoboe vnimanie slovam v imenax xostov i pridaut etim slovam bol'6iy ves, esli oni vstre4autsa v tekste). Esli bol'6instvo pol'zovateley mogut raspoznat' avniy spam, to dla poiskovoy sistemi eto ne tak prosto. Krupney6ie poiskovie portali imeut v 6tate sotrudnikov, kotorie specializiruutsa na otslejivanii internet-spama. Kogda obnarujivaetsa stranica, soderja6aa spam, poiskovaa sistema prekra6aet obxod stranici, kontent ne indeksiruetsa. Takoy process otslejivania spama medlenniy i dorogostoa6iy, no on daet rezul'tati. Pri otsutstvii bor'bi so spamom ka4estvo rezul'tatov poiska budet stremitel'no uxud6at'sa. Cel' provedennogo issledovania – pomo4' ekspertam, zanimau6imsa otslejivaniem spama. Osnovnaa zada4a – nau4it'sa identificirovat' stranici i sayti, kotorie avlautsa spamom, i naoborot, kotorie soderjat relevantniy tematike kontent. Metodi, predstavlennie v dannoy rabote, mogut imet' dva nazna4enia:
- kak pomo6' pri t6atel'nom izu4enii stranic na predmet spama;
- kak sposob bor'bi s rezul'tatami spama.
Process algoritmi4eskoy identifikacii spama slojen, poetomu sxemi, predstavlennie v dannoy rabote ne budut operirovat' bez vme6atel'stva specialista.
Predlagaemiy algoritm rabotaet sleduu6im obrazom: slu4aynoy viborkoy izbirautsa stranici, kotorie doljni bit' issledovani na nali4ie spama. Ekspert issleduet «slu4aynie stranici», i soob6aet algoritmu, prisutstvuet li na nix spam. Vposledstvii algoritm identificiruet drugie stranici, kotorie, skoree vsego, okajutsa «xoro6imi», pri u4ete ix svazi s «xoro6imi slu4aynimi» stranicami. V etoy rabote:
- Formalizuetsa problema veb-spama i algoritma otslejivania spama.
- Opredelautsa pokazateli ocenki effektivnosti raboti algoritmov otslejivania spama.
- Predstavlautsa sxemi dla slu4aynogo otbora stranic, kotorie budut oceneni vru4nuu.
- Predlagaetsa algoritm TrustRank dla opredelenia veroatnosti «xoro6ix» stranic.
- Obsujdautsa rezul'tati provedennoy raboti (roboti poiskovoy sistemi Alta Vista obo6li 31 mln saytov, 2 tis. saytov bili izu4eni vru4nuu). Predlagaetsa lubopitnaa statistika 4astoti vstre4aemosti opredelennix vidov kontenta.
2. PREDVARITEL'NAA INFORMACIA
2.1. internet-model'
Predstavlaem model' seti v vide grafa ς = (ν,ε),sostoa6ego iz mnojestva ν stranic N i mnojestva ε napravlennix ssilok, soedinau6ix stranici. Na praktike internet-stranica p mojet soderjat' mnogo4islennie HMTL giperssilki na nekuu druguu stranicu q. V etom slu4ae mi predstavlaem eti mnogo4islennie ssilki kak edinstvennuu ssilku (p,q) º ε. Mi takje udalaem vnutrennie ssilki. Na ris.1 predstavlen o4en' prostoy Internet graf, sostoa6iy iz 4 stranic i 4 ssilok.
Ris.1 Prostoy Internet graf
Kajdaa stranica soderjit vxoda6ie i isxoda6ie ssilki. Koli4estvo vxoda6ix ssilok na stranicu p predstavlaet soboy polustepen' zaxoda i(p). Koli4estvo isxoda6ix ssilok – polustepen' isxoda w(p). Naprimer, polustepen' zaxoda stranici 3 na ris.1 ravna edinice, a polustepen' isxoda – dvum. Stranici, kotorie ne soderjat vxoda6ie ssilki, nazivautsa stranicami bez ssilok. Stranici, kotorie ne soderjat isxoda6ix ssilok, nazivautsa ne ssilau6imisa stranicami. Stranici, kotorie ne soderjat ni vxoda6ix, ni isxoda6ix ssilok, nazivautsa izolirovannimi. Stranica 1 na ris.1 avlaetsa stranicey bez ssilok, a stranica 4 – ne ssilau6eysa.
Rassmotrim 2 matrici internet-grafov, kotorie v dal'ney6em budut imet' vajnoe zna4enie. Odna iz matric – matrica perexoda T:
Matrica perexoda, sootvetstvuu6aa grafu na ris.1:
Rassmotri takje obratnuu matricu perexoda U:
Neobxodimo obratit' vnimanie, 4to U≠TT . Naprimer, na ris.1 obratnaa matrica perexoda vigladit tak:
2.2. PageRank – algoritm ras4eta avtoritetnosti stranici, a takje sam pokazatel' v 4islennom virajenii. Tak kak predlagaemie algoritmi osnovani na PageRank, v dannom razdele predlagaetsa ego korotkiy obzor. Page Rank stranici budet dostato4no visokim, esli neobxodimoe koli4estvo vajnix stranic ukazivaut na etu stranicu. Page Rank osnovivaetsa na vzaimnom vlianii stranic. Stranica ne tol'ko sama okazivaet vlianie na druguu stranicu, no i ispitivaet vlianie na sebe. Pokazateli Page Rank r(p) stranici p opredelautsa tak:
gde α – koefficient raspada1. Ravnosil'no matri4noe uravnenie:
Takim obrazom, ocenka nekotoroy stranici p predstavlaet summu dvux komponentov. Odna 4ast' ocenki otnositsa k stranicam, kotorie ukazivaut na stranicu p. Drugaa (stati4eskaa) 4ast' ocenki podxodit dla vsex veb-stranic.
Page Rank mojet vi4islat'sa iteracionno, naprimer, s pomo6'u metoda Jacobi. V strogo matemati4eskom smisle iteracia doljna perexodit' v konvergenciu. Na praktike prinato ispol'zovat' 4etko zafiksirovannoe 4islo iteraciy.
Standartniy algoritm PageRank prisvaivaet stati4eskuu ocenku kajdoy stranice, versia Page Rank so sme6eniem funkcioniruet po-drugomu. V matri4nom uravnenii
vektor d mojet bit' ispol'zovan dla prisvoenia nulevoy stati4eskoy ocenki radu stranic. Ocenka takix special'nix stranic rasprostranaetsa vo vrema iteracii na ukazivaemie stranici.
3. OCENKA STEPENI DOVERIA
3.1. Funkcii prognozirovania i doveria
V razdele 1 uje bilo skazano, 4to raspoznavanie spama – zada4a, trebuu6aa vme6atel'stva 4eloveka i ego sub&ektivnoy ocenki. Su6estvuet ponatie proverki stranici na spam s pomo6'u dvoi4noy funkcii prognozirovania (O) vsex stranic p º ν:
Na ris.2 predstavleni 7 internet-stranic. «Xoro6ie» stranici predstavleni na belom fone, «ploxie» – na 4ernom. Vizivaa funkciu prognozirovania dla stranic 1-4, budet vidano zna4enie 1.
Ris.2 Xoro6ie i ploxie uzli seti
Procedura prognozirovania dorogostoa6aa i dostato4no dlitel'naa. Poetomu primenenie podobnoy funkcii dla vsex stranic ne priemlemo. Pri provedenii analiza vajno prodemonstrirovat' izbiratel'nost', poetomu logi4nee obratit'sa k ekspertu dla analiza nekotorix internet-stranic. Pri analize «xoro6ix» stranic mi polagalis' na empiri4eskoe nabludenie:
«Xoro6ie» stranici redko ukazivaut na «ploxie». Danniy vivod osnovan na intuicii: «Ploxie» stranici sozdautsa s nameren'em vvesti poiskovie sistemi v zablujdenie, oni daleki ot celi predostavlenia poleznoy informacii. Takim obrazom, u ludey, sozdau6ix «xoro6ie» stranici, net ni maley6ego osnovania ssilat'sa na «ploxie» stranici. Odnako sozdateley «xoro6ix» stranic toje inogda vvodat v zablujdenie. Poetomu v Internete mojno vstretit' ssilki s «xoro6ix» stranic na «ploxie» (na ris.2 takaa ssilka pokazana mejdu stranicami 4 i 5 i pome4ena zvezdo4koy). Rassmotrim primer. Voz'mem xoro6uu, no nemoderiruemuu gostevuu knigu. Spameri mogut razmestit' ssilku na svoi spam-stranici, kak 4ast' «nevinnix» soob6eniy, razme6aemix v etoy «gostevoy».
Inogda spamerskie sayti predstavlaut iz seba t.n. «Honeypot» («gor6o4ek meda»): sayti predstavlaut soboy nabor stranic, kotorie soderjat poleznuu informaciu (naprimer, kopii dokumentacii Unix), v to je vrema na stranicax soderjatsa skritie ssilki na spam-stranici. «Honeypot», privlekaa pol'zovateley ssilat'sa na nix, uveli4ivaet ranjirovanie stranic, soderja6ix spam. Neobxodimo pod4erknut', 4to, v svou o4ered', zaspamlennie stranici 4asto ssilautsa na «xoro6ie» stranici. Naprimer, sozdateli zaspamlennix stranic ukazivaut na «xoro6ie» i vajnie stranici, s cel'u sozdania «Honeypot», libo v nadejde, 4to bol'6oe koli4estvo isxoda6ix ssilok budut sposobstvovat' povi6eniu nekotorix vidov ranjirovania. Dla ocenki stranic, ne pribegaa k pokazatelu O, neobxodimo ocenit', kakova veroatnost' togo, 4to dannaa stranica R avlaetsa «xoro6ey». Virajaas' nau4nim azikom, opredelaetsa funkcia doveria T imeu6aa diapazon zna4eniy ot 0 (ploxaa stranica) do 1 (xoro6aa stranica) V ideale, dla luboy stranici r, T(r) doljno pokazivat' veroatnost' togo, 4to stranica r – «xoro6aa».
Ideal'niy pokazatel' funkcii doveria
T(p) = Pr[O(p) = 1]
Dopustim, imeetsa 100 stranic, pokazatel' doveria kotorix sostavlaet 0.7. Predpolojim, 4to ocenka stranic osu6estvlaetsa s ispol'zovaniem funkcii prognozirovania. Togda, esli T srabotaet nujnim obrazom, dla 70 stranic pokazatel' prognozirovania sostavit 1, a dla ostav6ixsa 30 – 0.
Esli T ne mojet to4no opredelit' veroatnost' togo, 4to stranica «xoro6aa», to dannaa funkcia vse ravno okajetsa neobxodimoy pri delenii stranic na «xoro6ie» i «ploxie», polagaas' pri etom na priblizitel'nie dannie. Naprimer, dani dve stranici, p i q. Pokazatel' doveria stranici r nije pokazatela doveria stranici q. Iz etogo sleduet, 4to veroatnost' togo, 4to stranica r «xoro6aa» nije veroatnosti togo, 4to stranica q «xoro6aa». Funkcia doveria T okajetsa poleznoy, po krayney mere, pri raspredelenii rezul'tatov poiska, kogda predpo4tenie otdaetsa stranicam, kotorie, veroatnee vsego, avlautsa «xoro6imi». Odnim iz predpo4titel'nix svoystv funkcii doveria avlaetsa «svoystvo uporado4ennosti doveria»
Odin iz sposobov ponizit' trebovania k pokazatelu doveria – vvesti porogovuu veli4inu δ.
Porogoviy pokazatel' funkcii doveria
Esli stranica p polu4aet ocenku vi6e pokazatela δ eto svidetel'stvuet o tom, 4to stranica «xoro6aa». V protivnom slu4ae, o stranice p ni4ego nel'za budet skazat'. Funkcia T predostavlaet informaciu, v sootvetstvii s kotoroy mojno opredelit', 4to stranici, naxoda6iesa v nekotorom podmnojestve i imeu6ie visokiy pokazatel' doveria avlautsa xoro6imi.
Obratite vnimanie, 4to funkcia T s porogovim pokazatelem ne vsegda vliaet na sortirovku stranic po principu «xoro6ie»-«ploxie».
3.2. Pokazateli ocenki
V dannom razdele predstavleni 3 pokazatela, kotorie pomogaut ocenivat' xarakteristiki funkcii T. Dopustim, imeetsa χ slu4aynix internet-stranic, dla kotorix mojno privle4' funkcii T i O i ocenit', kak rabotaut te ili inie svoystva dla dannogo mnojestva. (v razdele 6 budet rasskazano, po kakomu principu vibirautsa stranici, a poka mi s4itaem, 4to χ – mnojestvo slu4aynix veb-stranic).
Perviy pokazatel' tesno svazan s zadannim pokazatelem doveria. Vvoditsa dvoi4naa funkcia I(T, O, p, q), s pomo6'u kotoroy opredelaetsa, 4to «ploxie» stranici polu4ili pokazatel' doveria ravniy ili vi6e «xoro6ix» stranic
Zatem iz viborki χ stranic sostavlautsa mnojestva  par stranic (p,q), p ≠ q, zatem vi4islaetsa, s kakimi parami stranic funkcia doveria ne dopuskaet o6ibok:
 Pairwise Ordredness (uporado4ennost' pari)
Esli pairord raven 1, to v funkcii doveria o6ibok ne bilo, esli pairord raven 0, to v funkcii doveria nepravil'naa dla vsex par.
Dva sleduu6ix pokazatela otnosatsa k porogovomu pokazatelu urovna doveria. Vvodatsa pokazateli precision (to4nosti) i recall (vosproizvedenia) dla porogovoy veli4ini δ. Pokazatel' Precision vi4islaetsa kak otno6enie xoro6ix stranic, prinadleja6ix χ, ko vsem stranicam, prinadleja6im χ, pokazatel' doveria kotorix ukazan.
Podobnim obrazom, mi opredelaem pokazatel' Recall kak otno6enie koli4estva xoro6ix stranic s ukazannim pokazatelem doveria k ob6emu koli4estvu xoro6ix stranic, prinadleja6ix χ.
4. Vi4islenie doveria
V razdele 4.3 budet postroen algoritm TrustRank. Prejde neobxodimo proizvesti podgotovitel'nuu rabotu. Itak, pristupim k viavleniu funkcii doveria. Na4nem s samogo prostogo. Pri uslovii, 4to kol-vo L ograni4eno dla vi4islenia funkcii O, na4nem neposredstvenno s viborki mnojestva S slu4aynix stranic L i vizovem funkciu prognozirovania dla zadannix elementov. (V razdele 5 budet rasskazano, kak optimal'no vibrat' slu4aynie stranici). Obozna4im podmnojestva «xoro6ix» i «ploxix» stranic S+ i S- sootvetstvenno. Tak kak ostav6iesa stranici ne proverautsa ekspertami, im prisvaivaetsa pokazatel' doveria, ravniy ½ iz-za otsutstvia informacii.
Vvoditsa ponatie pustaa funkcia doveria T0 dla lubix p º ν:
Naprimer, prisvoim L zna4enie 3 i primenim na6 metod k primeru na ris.2 Slu4ayno vibrannoe mnojestvo S mojet imet' zna4enia {1, 3, 6}. Pust' o i t0 budut obozna4at' vektori prognozirovania i pokazateley doveria dla kajdoy stranici sootvetstvenno. Togda:
Dla ocenki povedenia pustoy funkcii doveria predpolojim, 4to na6a viborka X sostoit iz 7 stranic, i i mi rassmatrivaem vse vozmojnie 42 (7*6) pari. Togda pokazatel' uporado4ennosti pari sostavit 17/21. Dla poroga δ =½ pokazatel' precision sostavit 1, a pokazatel' recall – ½.
4.1. Rasprostranenie funkcii doveria
Dla dal'ney6ego pods4eta pokazatela doveria vospol'zuemsa nesvaznost'u «xoro6ix» stranic.
Slu4aynim obrazom vibiraem mnojestvo S iz L stranic, kotorie budut podverjeni prognozirovaniu. Predpolagaa, 4to «xoro6ie» stranici ukazivaut na drugie isklu4itel'no «xoro6ie» stranici, ocenka 1 prisvaivaetsa vsem stranicam, kotorie dostupni v S+ mnojestve v M ili menee perexodov.
Sootvetstvuu6aa funkcia doveria TMopredelaetsa tak:
| M |
pairord |
prec |
rec |
| 1 |
19/21 |
1 |
3/4 |
| 2 |
1 |
1 |
1 |
| 3 |
17/21 |
4/5 |
1 |
Tablica1: povedenie M-6agovoy funkcii doveria TM, pri M º {1, 2, 3} .
M-6agovaa funkcia doveria 
Gde q  M p svidetel'stvuet o su6estvovanii puti maksimal'noy dlini M so stranici q na stranicu p. Takoy put' ne doljen soderjat' «ploxix» stranic.
Ispol'zua primer na ris.2 i slu4aynuu sovokupnost' S = {1, 3, 6}, mojno predstavit' ocenku doveria dla M s raznimi zna4eniami:
M=1: t1 = [1, 1, 1, ½, ½, 0, ½]
M=2: t2 = [1, 1, 1, 1, ½, 0, ½]
M=3: t3 = [1, 1, 1, 1, 1, 0, ½]
V tablice1 pokazano, 4to pri M = 1 i M = 2 zna4enia pairord i recall vozrastaut, a zna4enie precision ravno 1. Odnako vse sovsem ne tak obstoit pri M = 3. Stranica 5 polu4aet ocenku 1 blagodara ssilke s «xoro6ey» stranici 4 na «ploxuu» stranicu 5 (na ris. 2 otme4eno zvezdo4koy). Kak pokazal predidu6iy primer, problema zaklu4aetsa v tom, 4to pri pokazatele doveria M-step net absolutnoy uverennosti v tom, 4to stranici iz sovokupnosti «xoro6ix» stranic na samom dele avlautsa «xoro6imi».
4.2. Zatuxanie pokazatela doveria
Nabludenia svidetel'stvuut o tom, 4to mi ponijaem pokazatel' doveria, po mere togo, kak vse dal'6e i dal'6e udalaemsa ot «xoro6ix» slu4aynix stranic. Su6estvuet mnogo sposobov po dostijeniu snijenia pokazatela doveria. Rassmotrim dve vozmojnie sxemi.
Na ris.3 predlojen odin iz sposobov, kotoriy nazivaetsa trust dampening (padenie doveria). Tak kak stranica 2 naxoditsa na rasstoanii odnoy ssilki ot «xoro6ey» slu4aynoy stranici 1, to ey mojno prisvoit' zanijennuu ocenku doveria β, gde β < 1. Tak kak stranica 3 sleduet za stranicey 2, kotoroy prisvoen pokazatel' β, to ey prisvaivaetsa zanijennaa ocenka, ravnaa β*β. Neobxodimo vibrat' sposob, kak prisvaivat' pokazatel' doveria stranicam, kotorie soderjat mnogo4islennie vxoda6ie ssilki. Naprimer, na ris.3 str.1 takje ssilaetsa na str. 3. V etom slu4ae, imeet smisl prisvoit' str.3 maksimal'noe zna4enie pokazatela doveria, v dannom slu4ae β, ili srednee zna4enie, v dannom slu4ae: (β+β*β)/2  Ris.3 Trust dampening  Ris.4 Trust splitting
Vtoroy sposob dla snijenia pokazatela doveria, kotoriy nazivaetsa trust splitting (razdelenie doveria) osnovan na sleduu6em nabludenii: ostorojnost', s kotoroy pol'zovateli dobavlaut ssilki na svoi stranici, obratno proporcional'na koli4estvu ssilok na stranice. Drugimi slovami, esli «xoro6aa» stranica soderjit vsego neskol'ko isxoda6ix ssilok, to, skoree vsego, stranici, na kotorie vedut eti ssilki, «xoro6ie». Odnako esli «xoro6aa» stranica soderjit sotni isxoda6ix ssilok, to velika veroatnost' togo, 4to stranici, na kotorie vedut eti ssilki, okajutsa «ploximi». Dannoe nabludenie privodit nas k «razdeleniu doveria», tak kak dannoe nabludenie rasprostranaetsa i na drugie stranici: esli stranica r imeet pokazatel' doveria T(r) i ukazivaet na !(r) stranic, to ocenka dla kajdoy iz !(r) stranic budet ravna otno6eniu T(p)/!(p). V etom slu4ae, real'naa ocenka stranici budet predstavlat' soboy summu ocenok, rass4itannix s pomo6'u vxoda6ix ssilok. Nagladno, 4em bol'6e doveria polu4aet stranica s drugix stranic, tem bol'6e veroatnost' togo, 4to dannaa stranica «xoro6aa».
Ris.4 sxemati4no predstavlaet metod trust splitting. «Xoro6aa» slu4aynaa stranica 1 soderjit 2 isxoda6ie ssilki, takim obrazom, ona raspredelaet polovinu ocenki, ravnoy 1, mejdu stranicami, na kotorie ona ukazivaet. To4no tak je, «xoro6aa» slu4aynaa stranica 2 soderjit tri isxoda6ix ssilki, sootvetstvenno, kajdaa stranica, na kotoruu ukazivaet stranica 2, polu4aet odnu tret' ot ee ocenki. Togda ocenka stranici 3 budet skladivat'sa sleduu6im obrazom: 1/2 + 1/3 = 5/6. Neobxodimo otmetit', 4to vozmojno sovme6enie dvux sposobov snijenia pokazatela doveria. Na ris.4, naprimer, str.3 mojet bit' prisvoena ocenka, kotoraa rass4itivaetsa sleduu6im obrazom: β*(1/2 + 1/3) . V dal'ney6em budet dokazano, 4to pri vi4islenii ocenki doveria celesoobrazno polagat'sa na algoritm Page Rank.
4.3 Algoritm TrustRank
Funkcia TrustRank, izobrajennaa na ris. 5, neobxodima pri pods4ete ocenki doveria dla internet-grafa. Algoritm raboti ob&asnaetsa s pomo6'u ris.2.
Algoritm TrustRank predstavlaet soboy graf (perexodnaa matrica T i N internet-stranic). Ispol'zuutsa parametri, kotorie kontroliruut rabotu algoritma (L, MB, αB sm. nije).  Ris.5 Algoritm TrustRank
6ag1: algoritm vizivaet funkciu SelectSeed, kotoraa vozvra6aet vektor s. Sostavlau6ie vektora s(p) opredelaut «predpo4tenie» stranici p kak slu4aynoy stranici (podrobnosti mojno nayti v razdele 5). Kak pokazano v razdele 5.1, odna versia SelectSeed vozvra6aet sleduu6iy vektor k primeru na Ris.2: s = [0,08, 0,13, 0,08, 0,10, 0,09, 0,06. 0,02].
6ag 2: funkcia Rank(x,s) osu6estvlaet preobrazovania vektora x v x", s elementami x"(i) v poradke ubivania zna4enia s(x’(i)). Naprimer, σ = [2, 4, 5, 1, 3, 6, 7].
V sootvetstvii s privedennim primerom, stranica 2 samaa predpo4titel'naa slu4ayno vibrannaa stranica, sleduu6aa 4 i t.d. 6ag 3: aktiviziruetsa funkcia Oracle dla L, naibolee predpo4titel'nix stranic. Sostavlau6ie stati4eskogo vektora raspredelenia d, sootvetstvuu6ie xoro6im stranicam, ustanavlivautsa ravnimi 1.
6ag 4: normalizuetsa vektor d, tak, 4tobi summa ego sostavlau6ix rovnalas' 1. Dopuskaa, 4to L=3, mnojestvo slu4aynix stranic {2, 4, 5}. 2 i 4 avlautsa xoro6imi slu4ayno vibrannimi stranicami, mi polu4aem sleduu6iy vektor raspredelenia stati4eskix ocenok dla na6ego primera, d = [0, ½, 0, ½, 0, 0, 0].
6ag 5: zaklu4itel'niy etap, pods4itivaetsa TrustRank s ispol'zovaniem sme6ennix vi4isleniy PageRank, gde d zamenaet ravnomernoe raspredelenie. Zamet'te, 4to 6ag 5 predstavlaet opredelennuu model', kogda doverie snijaetsa i razdelaetsa: v kajdoy iteracii pokazatel' doveria ver6ini raspredelaetsa mejdu sosedstvuu6imi i snijaetsa po pri4ine koefficienta zatuxania αV.
Dopuskaa, 4to αV = 0,85, MV = 20, algoritm pokazivaet sleduu6iy rezul'tat:
t* = [0, 0,18, 0,12, 0,15, 0,13, 0.,05, 0,05]
Obratite vnimanie, 4to sposob iteracionnogo opredelenia pokazatela doveria vliaet na to, 4to xoro6ie, slu4ayno vibrannie stranici (2 i 4), ne imeut bol'6e pokazatela, ravnogo 1.Odnako, u nix po-prejnemu samie visokie pokazateli. Takje sleduet otmetit', 4to stranica 4 imeet bolee nizkiy pokazatel', 4em stranica 2. Eto svazanno so strukturoy ssilok v dannom primere: ssilki na stranicu 2 sdelani so stranici s visokim pokazatelem (stranica 3), a na stranicu 4 net. Takim obrazom, algoritm TrustRank «korrektiruet» pervona4al'nie pokazateli, predstavlennie funkciey prognozirovania Oracle, predstavlaa bol'6e dokazatel'stv togo, 4to po sravneniu so stranicey 4, stranica 2 – xoro6aa. Esli polu4itsa, mojno normalizovat' summarniy vektor, razdeliv vse pokazateli na samiy visokiy (delaa pokazatel' stranici 2 ravnim 1), to dannoe deystvie ne privneset kardinal'nix izmeneniy v poradok stranic. Iz dannogo primera vidno, 4to algoritm TrustRank prisvaivaet xoro6im stranicam bolee visokiy pokazatel'. V 4astnosti, tri iz 4etirex xoro6ix stranic (2, 3 i 4) polu4ili visokiy pokazatel', a dve iz trex ploxix stranic (stranici 6 i 7) polu4ili nizkiy pokazatel'. Odnako, pokazateli stranic 1 i 5 bili opredeleni algoritmom ne adekvatno. Stranica 1 ne bila sredi slu4ayno vibrannix i ne imela dostato4nogo koli4estva ssilok s saytov s visokimi pokazatelami, no ee pokazatel' ostalsa ravnim 0. So vsemi xoro6imi stranicami, ne imeu6imi ssilok, proisxodit toje samoe, esli tol'ko oni ne slu4ayno vibrannie. Ploxaa stranica 5 polu4ila visokiy pokazatel', t.k. na etoy stranice ukazana odna iz redkix good-to-bad ssilok. Kak budet vidno iz razdela 6, nesmotra na podobnie o6ibki, na real'nom veb-grafe algoritm TrustRank pravil'no opredelaet bol'6instvo podxoda6ix stranic.
5. Vibor slu4aynix stranic
Zada4a funkcii SelectSeed opredelit' predpo4titel'nie stranici, kotorie voydut v slu4ayno vibrannie. Jelatel'no nayti stranici, kotorie budut naibolee prigodnimi dla opredelenia dopolnitel'nix podxoda6ix stranic. V to je vrema jelatel'no ne uveli4ivat' koli4estvo slu4ayno vibrannix stranic s cel'u ograni4enia ispol'zovania funkcii Oracle. V dannom razdele budut rassmotreni dve strategii dla funkcii SelectSeed, kak dopolnenie k ranee upomanutoy strategii slu4aynogo vibora. 5.1. Inversniy (obratniy) PageRank
T.k. pokazatel' doveria vo mnogom opredelaetsa xoro6imi slu4aynimi stranicami, odnim iz podxodov mojet bit' vibor stranic, s pomo6'u kotorix budet vozmojno polu4it' drugie. V osobennosti, vibor slu4aynix stranic, prinimaa vo vnimanie isxoda6ie ssilki. Naprimer, na Ris.2, gde sootvetstvuu6ee mnojestvo slu4aynix stranic L=2, t.k. S = {2, 5}, u stranic 2 i 5 samoe bol'6oe 4islo isxoda6ix ssilok.  Ris. 6: Algoritm inversnogo PageRank
V dal'ney6em, mojno uveli4it' pokrivau6uu sposobnost'. Nabor slu4aynix stranic mogut sostavit' te stranici, kotorie ukazali bol'6ee koli4estvo stranic, v svou o4ered', ukazav6ix na drugie stranici i t.d. Interesno, 4to danniy podxod blizok sxeme, po kotoroy rabotaet PageRank, raznica v tom, 4to v na6em slu4ae vajnost' stranici zavisit ot ee isxoda6ix ssilok, a ne ot vxoda6ix. Takim obrazom, 4tobi rass4itat' predpo4titel'nost' stranici, proizvedem vi4islenia PageRank na grafe ς׳ = (ν,ε׳), gde 
Algoritm nazivaetsa inversnim, t.k. mi invertirovali ssilki. Na ris.6 pokazan algoritm vi4isleniy inversnogo PageRank. Zamet'te, 4to koefficient zatuxania αI i 4islo iteraciy (perexodov) MI mogut otli4at'sa ot αB i MB, ispol'zovannix v algoritme TrustRank. Vi4islenia identi4ni sdelannim po tradicionnomu algoritmu PageRank (Razdel 2.2), za isklu4eniem inversnoy perexodnoy matrici U, ispol'zovannoy vmesto obi4noy perexodnoy matrici T.
Dla na6ego primera na ris.2, algoritm inversnogo PageRank (αI = 0,85, MI = 20) daet sleduu6ie pokazateli (uje prodemonstrirovannie v Razdele 4.3):
s = [0,08, 0,13, 0,08, 0,10, 0,09, 0,06, 0,02]
Dla 4islovogo zna4enia L = 3, slu4ayniy nabor S = {2, 4, 5}. Sootvetstvenno, podxoda6ee slu4aynoe mnojestvo S+ = {2, 4}, t.o. stranici 2 i 4 avlautsa otpravnoy to4koy dla ras4eta raspredelenia.
Vajno pomnit', 4to inversniy PageRank avlaetsa evristi4eskim (xoro6o funkcioniruu6im, 4to mojno uvidet' v Razdele 6). Vo-pervix, inversniy PageRank ne garantiruet maksimal'niy oxvat. Naprimer, na ris.7, gde L = 2, maksimal'naa pokrivau6aa sposobnost' rasprostranaetsa libo na slu4aynoe mnojestvo {1, 3}, libo na {2, 3}. Xota, vi4islenia inversnogo PageRank demonstriruut sleduu6iy stepennoy vektor: s = [0,05, 0,05, 0,04, 0,02, 0,02, 0,02, 0,02] ,
kotoriy vedet k slu4aynomu mnojestvu S = {1, 2}.
Tem ne menee, inversniy PageRank predstavlaet interes potomu, 4to vrema vipolnenia ego ras4etov polinomial'no, togda kak, opredelenie maksimal'nogo oxvata avlaetsa problemoy NP-polnoti2.  Ris.7: Graf, dla kotorogo inversniy PageRank ne predstavlaet maksimal'niy oxvat.
Vo-vtorix, uveli4enie oxvata ne vsegda avlaetsa nailu46ey strategiey. Proillustriruem eto, rasprostranaa pokazatel' doveria posredstvom razdelenia, bez u4eta kakix-libo ego sokra6eniy. Vozvra6aas' k Ris.7, vibiraem stranicu 2 kak slu4aynuu, ona okazivaetsa xoro6ey. Zatem stranici 4, 5 i 6, kajdaa polu4aet pokazatel' 1/3. Predpolojim, 4to slu4ayno vibrannaa stranica 3 takje budet xoro6ey. Stranica 7 polu4aet pokazatel' 1. V zavisimosti ot kone4noy celi, predpo4titel'nim mojet bit' ispol'zovanie stranici 3, t.k. mojno to4no predpolojit' kakie stranici ona opredelit, nesmotra na to, 4to ix mojet bit' nemnogo. Odnako esli ispol'zovat' pokazatel' doveria li6' dla sravnenia s drugim pokazatelem, sleduet rassmotret' bol'6ee koli4estvo stranic pust' s men'6ey to4nost'u.
5.2. Visokiy PageRank
Dopustim, 4to stepen' identifikacii stranic, kak xoro6ix ili ploxix, budet odinakovoy dla vsex veb-stranic. Bolee vajnim mojet okazat'sa dokazatel'stvo togo, 4to stranica, imeu6aa visokuu ocenku sredi rezul'tatov poiska, deystvitel'no avlaetsa xoro6ey. Naprimer, kontenti stranic p, q, r i s adekvatno i v ravnoy stepeni otve4aut vvedennomu zaprosu. Esli poiskovaa sistema ispol'zuet PageRank dla uporado4ivania rezul'tatov, to stranica s samim visokim PageRank naprimer, p, budet predstavlena pervoy, zatem stranica s men'6im PageRank – q i t.d. v poradke ubivania. Veroatnee, 4to pol'zovatela zainteresuut stranici p i q, a ne r i s, poetomu v pervuu o4ered' neobxodimo opredelit' pokazatel' doveria dla stranic p i q. Naprimer, esli stranica p okajetsa spamerskoy, to pol'zovatel' mojet vospol'zovat'sa stranicey q. Takim obrazom, vtoroe podtverjdenie evristi4nosti PageRank v vibore slu4aynogo nabora stranic zastavit otdat' predpo4tenie stranicam s visokim PageRank, tak kak takie stranici ukajut na dostoynie ix stranici. Sledovatel'no, mojno budet opredelit' sootvetstvuu6ie pokazateli doveria stranic, zanimau6ix pervie stroki v rezul'tatax poiska. Vibor slu4aynix stranic soglasno PageRank predostavit vozmojnost' opredelit', naskol'ko podxoda6ey avlaetsa stranica (po sravneniu s inversnim PageRank). No eti stranici potrebuut bolee t6atel'nogo rassmotrenia.
6. EKSPERIMENTI
6.1. Komplekt dannix
S cel'u vi4islenia algoritmov bili provedeni eksperimenti (avgust 2003) s ispol'zovaniem polnogo mnojestva stranic, naydennix i proindeksirovannix poiskovoy sistemoy Alta Vista.
Dla sokra6enia vi4islitel'nix zatrat, rabota budet provedena na urovne saytov, a ne otdel'nix stranic (sleduet otmetit', 4to vse predstavlennie metodi podxodat kak dla saytov, tak i dla stranic). Neskol'ko milliardov stranic bilo sgruppirovano v 31 003 946 saytov s pomo6'u special'nogo algoritma, kotoriy avlaetsa 4ast'u Alta Vista. Vse otdel'nie stranici s odinakovimi domennimi imenami3 bili ob&edineni v odin sayt. Re6iv provodit' eksperiment na urovne saytov, bila sdelana odna ssilka s sayta a na sayt b, togda kak na original'nom veb-grafe odna ili bolee ssilok so stranic sayta a na stranici sayta b. V na4ale raboti bilo otme4eno, 4to prakti4eski tret' vsex saytov (13 197 046) ne imela vxoda6ix ssilok. Za osnovu algoritmov uveli4enia pokazatela doveria berutsa dannie o vxoda6ix ssilkax, poetomu sayti, ne imeu6ie takix dannix ne mogli bit' ispol'zovani dla vi4islenia algoritma. K s4ast'u, sayti bez ssilok zanimaut nizkie pozicii v rezul'tatax zaprosa (polu4aut odinakovo nizkiy PageRank), poetomu ne tak kriti4no razdelenie saytov na ploxie i xoro6ie sredi nix. Dla dannix vi4isleniy, odin iz avtorov etoy raboti sigral rol' orakula, issledua stranici razli4nix saytov, proveraa ix na spam i predlagaa dopolnitel'nuu klassifikaciu, kotoraa budet predstavlena dalee. No ispol'zovanie algoritma ocenki avtora, mojet stat' pri4inoy neob&ektivnix rezul'tatov. Ru4noe vi4islenie pokazatela doveria zanalo nedeli: proverka sayta sostoala iz prosmotra bol'6ego koli4estva stranic s cel'u viavlenia namerenia obmanut' poiskovuu sistemu. Sleduu6ey trudnovipolnimoy zada4ey bilo nayti specialistov v oblasti poiskovix sistem, kotorie smogli bi vipolnit' dannoe zadanie. Vmesto etogo, avtor nabludal za rabotoy specialistov, izu4aa texniku opredelenia spamerskix saytov. V dal'ney6em, im bili predprinati popitki ispol'zovania dannix metodov s posleduu6im predstavleniem maksimal'no ob&ektivnix rezul'tatov.
6.2. Mnojestvo slu4ayno vibrannix stranic Perviy etap bil predstavlen eksperimentami po sravneniu inversnogo PageRank i visokogo PageRank (Razdel 5.1 i 5.2). Dla skorey6ego predstavlenia rezul'tatov, dla provedenia eksperimentov bili ispol'zovani kompleksnie veb-grafi, predstavlau6ie osnovnie xarakteristiki setevogo spama. Prinimaa vo vnimanie ograni4enia v ob&eme stat'i, opisanie eksperimentov ne budet predstavleno polnost'u. Sleduet otmetit' li6' to, 4to ispol'zovanie inversnogo PageRank dla opredelenia mnojestva slu4ayno vibrannix stranic, predstavlaetsa lu46im. Poetomu, vse dal'ney6ie eksperimenti budut provedeni s ispol'zovaniem dannogo metoda.
Metod inversnogo PageRank pozvolil vistroit' ves' process takim obrazom, 4tobi dat' pravil'nuu ocenku prognozirovania. V pervuu o4ered' bili predstavleni polnie vi4islenia inversnogo PageRank s pomo6'u veb-grafa na urovne saytov, so sleduu6imi parametrami αI = 0,85 i MI = 20. (Koefficient zatuxania, ravniy 0,85, vpervie bil zaavlen v i s tex por s4itaetsa standartnoy veli4inoy v PageRank literature. Testi pokazivaut, 4to 20 iteraciy bilo dostato4no, 4tobi dostignut' konvergencii na otnositel'noy uporado4ennosti saytov.) Posle uporado4ivania saytov na osnovanii zna4enia ix inversnogo PageRank (6ag(2) na Ris.5), osnovnoe vnimanie bilo udeleno pervim 25 000. Vmesto polnogo vi4islenia prognoza dla dannix saytov, sna4ala bila proizvedena beglaa ocenka, dla udalenia nekotorie somnitel'nix saytov. V 4astnosti, bilo zame4eno, 4to sayti s visokim pokazatelem inversnogo PageRank demonstriruut bol'6uu predraspolojennost' k spamu, glavnim obrazom iz-za klonov otkritix katalogov: nekotorie spameri delaut to4nie kopii vsego kontenta otkritogo kataloga DMOZ, v nadejde ulu46it' osnovnie pokazateli ili s namereniem sozdat' «Honeypot», o kotorix 6la re4' v razdele 3.1. 4tobi bistro izbavit'sa ot spama, iz spiska 25 000 saytov bili udaleni te, kotorie ne zna4ilis' v krupney6ix veb-katalogax, sokrativ pervona4al'niy nabor do 7 900 saytov. Viboro4naa proverka otfil'trovannix saytov pokazala, 4to bili udaleni nekotorie xoro6ie sayti.  Ris. 8: Diagramma primernoy ocenki saytov.
Iz ostav6ixsa 7 900 saytov, ocenke bili podvergnuti pervie 1 250 (mnojestvo slu4ayno vibrannix saytov S), iz kotorix podxoda6imi bili priznanni 178. Danniy process predstavlen na Ris.5, 6ag (3). Otnositel'no nebol'6oe koli4estvo saytov, sostavlau6ix slu4aynoe mnojestvo S+, stalo rezul'tatom jestkogo kriteria otbora: sayti ne tol'ko proveralis' na spamerskie, po otno6eniu k nim, takje, bil ispol'zovan vtoroy fil'tr. V sootvetstvii s nim, otbiralis' sayti tol'ko s 4etko raspoznavaemim vladel'cem (takie kak pravitel'stvennie ili obrazovatel'niy u4rejdenia i kompanii), osu6estvlau6im kontrol' za kontentom sayta. Dopolnitel'niy fil'tr garantiroval prodoljitel'nuu i ka4estvennuu rabotu slu4ayno vibrannogo mnojestva saytov.
6.3. Primernaa ocenka
4tobi opredelit' pokazateli, predstavlennie v Razdele 3.2, neobxodimo mnojestvo χ saytov s izvestnimi pokazatelami prognozirovania. Bilo vibrano 1000 saytov, dannoe koli4estvo smojet predostavit' nujnie dannie i v dostato4no korotkiy srok. Bilo re6eno ne vibirat' sayti slu4ayno. T.k. mnogie sayti mogli okazat'sa nebol'6imi, soderjat' li6' neskol'ko stranic i/ili imet' o4en' nizkiy PageRank. Izvestno, 4to nebol'6ie sayti i sayti s nizkim PageRank sleduut raspredeleniu po stepennoy zavisimosti, za4astuu okazivaas' odnimi iz poslednix. V sootvetstvii s razdelom 5.2, bolee vajnim predstavlaetsa opredelenie spama na saytax s visokim PageRank, t.k. imenno oni 4a6e drugix figuriruut v rezul'tatax zaprosa. K tomu je, predstavit' to4nuu ocenku nebol'6omu saytu slojnee iz-za nedostatka dannix o nem.
4tobi obespe4it' reprezentativnost', bil ispol'zovan sleduu6iy metod. Sayti bili raspolojeni v ubivau6im poradke, soglasno zna4eniu ix PageRank, ves' spisok bil razdelen na 20 blokov, kajdiy iz kotorix vklu4al raznoe koli4estvo saytov, no s pokazatelam PageRank v summe ravnom 5%, ot ob6ego pokazatela PageRank.
Takim obrazom perviy blok vklu4al 86 saytov s samimi visokimi pokazatelami, vo vtorom bloke bilo 665, togda kak 20-iy sostoal iz 5 mln. saytov s samimi nizkimi pokazatelami. Primerniy nabor iz 1000 saytov bil sostavlen putem slu4aynoy viborki iz kajdogo bloka. Dalee bila provedena poverka saytov s cel'u opredelenia spamerskix. Rezul'tati predstavleni na Ris.8 – diagramma, predstavlau6aa razli4nie vidi saytov. Takim obrazom, bilo opredeleno, 4to li6' 748 saytov budut ispol'zovani dla opredelenia pokazatela TrustRank.
- Xoro6ie. 563 sayta s ka4estvennimi kontentami i s nulevim ili nezna4itel'nim 4islom ssilok na spamerskie sayti.
- Veb-sistemi. 37 saytov, prinadleja6ix k sistemam, kotorie obespe4ivaut soxranenie Vsemirnoy seti (WWW), libo zanimautsa deatel'nost'u, blizkoy k internet-uslugam. Vse sayti xoro6ie, bol'6instvo ssilok avtomati4eskie. Eti sayti polu4ili osobuu markirovku, 4tobi uprostit' nabludenie za nimi.
- Reklama. 13 saytov funkcionirovali kak sredstva bannernoy reklami. Dannie sayti ne obladali poleznim kontentom, a ix pokazatel' PageRank osnovivalsa glavnim obrazom na polu4aemix imi avtomati4eskix ssilkax. Tem ne menee, oni s4itautsa xoro6imi saytami, ne predstavlau6imi spam.
- Spam. Na 135 saytax bili obnarujeni razli4nie vidi spama. Sootvetstvenno, oni priznautsa ploximi saytami.
Eti 748 saytov obrazuut mnojestvo χ. Ostav6iesa 252 bili priznani ne prigodnimi dla dal'ney6ix vi4isleniy po raznim pri4inam:
- Publi4niy xosting. 22 sayta razme6ali svoi stranici. Bol'6oe koli4estvo nezavisimix izdateley, predstavlau6ix raznoobraznie kontenti dla etix saytov, zatrudnili ix opredelenie kak xoro6ix ili ploxix. Sleduet otmetit', 4to na urovne stranic ne vozniknet podobnoy trudnosti.
- Aliasi. U 35 saytov bili al'ternativnie adresa, oni bili lu46e izvestni pod drugimi imenami. Takie sayti bili isklu4eni, t.k. vajnost' aliasa ne sootvetstvuet vajnosti original'nogo sayta.
- Pustie sayti. 56 saytov bili pustimi. Oni sostoali iz odnoy stranici, kotoraa ne otli4alas' visoko informativnost'u.
- Nesu6estvuu6ie sayti. 96 saytov s4italis' nesu6estvuu6imi – libo oni ne bili naydeni v domennoy sisteme imen, libo ispol'zovannie sistemi ne mogli ustanovit' tcp/ip svaz' s sootvetstvuu6imi komp'uterami.
- Neizvestnie sayti. 43 sayta ne udalos' ocenit' na osnove dostupnoy informacii. Glavnim obrazom eto bili Vosto4no-Aziatskie sayti, na kotorix li6' nezna4itel'naa 4ast' kontenta bila predstavlena na angliyskom azike.
6.4. Rezul'tati V Razdele 4 bili opisani sposobi pereda4i pokazatela doveria dla mnojestva slu4ayno vibrannix stranic. V etom razdele budut rassmotreni tri al'ternativnix varianta TrustRank i dve osnovnie strategii, i ocenena ix effektivnost' s pomo6'u viborki χ:
- TrustRank. Na ris.5 predstavleni ispol'zovanniy algoritm (MV = 20 iteraciy i koefficient zatuxania αV = 0,85) i vibrannie xoro6ie sayti (178).
- PageRank. S4itaetsa, 4to PageRank avlaetsa samim loal'nim k spamu pokazatelem, potomu 4to on ocenivaet li6' ser'eznie krupnomas6tabnie izmenenia (nezna4itel'nie izmenenia v strukture ssilki ne okazivaut vliania na pokazatel'). Vopros, kak spravlaetsa PageRank so spamom sey4as, budet sover6enno umestnim. Poetomu v ras4etax PageRank stranici «a» ispol'zovalsa kak pokazatel' dla T(a). Vnov' M = 20 iteraciy s koefficient zatuxania αV = 0,85.
- Pustoy Trust. Za vsemi saytami bil zakreplen pokazatel' pustogo doveria ravniy ½, za isklu4eniem 1250 slu4ayno vibrannix saytov s pokazatelami 0 ili 1.
 Ris. 9: Xoro6ie sayti v blokax PageRank i TrustRank.  Ris.10: Ploxie sayti v blokax PageRank i TrustRank.
6.4.1. PageRank protiv TrustRank
V pervuu o4ered' sleduet predstavit' raznicu mejdu PageRank i TrustRank. Algoritm PageRank ne u4itivaet ka4estvo sayta, a vozmojnie nakazania sayta za ne ka4estvennost' to4no ne opredeleni. Neredko sayti, sozdannie umelimi spamerami, polu4aut visokiy pokazatel' PageRank. Togda kak TrustRank prizvan razli4at' xoro6ie i ploxie sayti: eto daet nadejdu na to, 4to spamerskie sayti ne polu4at visokix pokazateley.
Na ris.9 i ris.10 predstavleno sravnenie PageRank i TrustRank s u4etom ploxix i xoro6ix saytov v kajdom bloke. Bloki PageRank bili predstavleni v razdele 6.3; bilo opredeleno, 4to bloki TrustRank vklu4aut takoe je 4islo saytov, 4to i bloki PageRank. Bloki s 17 po 20 bili ob&edineni i dla PageRank, i dla TrustRank. (Eti poslednie 4 bloka vklu4aut bolee 4em 13 mln. saytov, ne imeu6ix ssilok. Vse takie sayti polu4ili minimal'niy stati4eskiy pokazatel' PageRank i pokazatel' nulevogo TrustRank, predostavlaa vozmojnost' uporado4it' ix). Gorizontal'nie osi na ris.9 i 10 otme4aut 4islo blokov PageRank i TrustRank. Vertikal'nie osi na pervom risunke sootvetstvuut procentnomu sootno6eniu xoro6ix saytov v kajdom bloke, 4islo xoro6ix saytov delennoe na ob6ee 4islo saytov v bloke.  Ris.11: Ponijenie pokazatela TrustRank v blokax.
Sleduet pomnit', 4to dostoynie sayti, sayti veb-sistem, reklama rassmatrivautsa kak xoro6ie; otnositel'noe uveli4enie otme4ena belim, svetlo-serim i temno-serim sootvetstvenno. Vertikal'nie osi vtorogo risunka sootvetstvuut procentnomu sootno6eniu ploxix saytov v opredelennom bloke. Naprimer, soglasno ris.10, 31% priemlemix saytov v bloke TrustRank avlaetsa ploxim.
Na dannom risunke vidno, 4to TrustRank avlaetsa priemlemim sredstvom dla viavlenia spama. Zamet'te, 4to v pervix pati blokax TrustRank net spama, togda kak v blokax, raspolojennix nije otme4eno visokoe soderjanie spama. V to je vrema, udivitel'no, 4to vtoroy blok PageRank po4ti na 20% s4itaetsa ploxim. Dla PageRank, sootno6enie ploxix saytov dostiglo rekordnogo urovna v blokax 9 i 10 (50% spama).
Ris.11 predlagaet drugoy vzglad na otno6enia PageRank i TrustRank. Zdes' vvoditsa ponatie ponijenie(demotion), avlenie, kogda sayt iz bloka s bolee visokim PageRank, poavlaetsa v bloke s bolee nizkim TrustRank. Otricatel'noe ponijenie eto povi6enie(promotion), predpolagau6ee obratniy poradok deystviy: sayt iz bloka s nizkim PageRank poavlaetsa v bloke s bolee visokim TrustRank. Srednee ponijenie ploxix saytov – vajniy element vi4islenia TrustRank.
Gorizontal'nie osi na ris.11 sootvetstvuut blokam PageRank. Vertikal'nie obozna4aut koli4estvo blokov, sayti kotorix iz PageRank pereme6alis' (ponijalis') v TrustRank. Beliy cvet sootvetstvuet dostoynim saytam, 4erniy – spamu. Na ris.11 vidno, 4to sredi saytov, zanimau6ix visokie pozicii, net spama, eto svidetel'stvuet o effektivnosti TrustRank. Danniy pokazatel' demonstriruet i to, 4to xoro6ie sayti, v bol'6instve slu4aev, ostavalis' v tom je bloke, kuda popali izna4al'no. Sledovatel'no, mojno konstatirovat', 4to TrustRank (v otli4ie PageRank), garantiruet, 4to pervie pozicii budut zanimat' tol'ko xoro6ie sayti. K sojaleniu, iz-za nedostatka informacii (vnutrennie ssilki) o sayte, TrustRank ne mojet otli4it' xoro6iy sayt s nizkim pokazatelem ot ploxogo.  Ris.12: Pairwise orderedness (poparnaa uporado4ennost').
6.4.2. Pairwise orderedness (PO)
Dannie PO, predstavlennie v razdele 3.2, takje ispol'zuutsa dla vi4islenia pokazatela TrustRank. Dla provedenia etogo eksperimenta bil sostavleno mnojestvo vsex vozmojnix par saytov dla neskol'kix podmnojestv slu4aynoy viborki X. 4tobi proverit' TrustRank dla naibolee vajnix saytov, ispol'zuetsa podmnojestva χ, sostoa6ee iz 100 saytov s samimi visokimi pokazatelami PageRank. Zatem, postepenno, k podmnojestvu χ dobavlalis' sayti s men'6im PageRank. V kone4nom itoge, dla vi4islenia pokazatela PO bili ispol'zovani vse pari iz 748 saytov.
Rezul'tati eksperimenta pokazani na ris.12. Gorizontal'nie osi ukazivaut 4islo saytov, ispol'zovannix dla ras4eta, togda kak vertikal'nie osi predstavlaut pokazateli PO dla opredelennix saytov. Naprimer, dla 500 saytov s visokim PageRank, pokazatel' PO dla TrustRank budet raven priblizitel'no 0,95.
Na ris.12 takje izobrajeni pokazateli PO dla funkcii pustogo Trust i PageRank. Sovme6enie mnojestv slu4aynix viborok S i χ proizo6lo na 5 xoro6ix saytax, ot funkcii pustogo Trusteti sayti polu4ili pokazateli ravnie ½. Pokazateli PO dla pustoy funkcii ispol'zuutsa v tom slu4ae, kogda informacii o ka4estve sayta minimal'na. Takje i dla PageRank, pokazateli PO ukazivaut, skol'ko imeetsa nujnoy informacii dla opredelenia ka4estv sayta. Iz dannogo primera vidno, 4to TrustRank prevosxodit i pustuu funkciu i PageRank. 6.4.3. Pokazateli to4nost' (Precision) i vosproizvedenie (Recall)
Poslednie rezul'tati eksperimenta (ris.13) predstavlaut opredelenie TrustRank s u4etom pokazateley Precision i Recall. Pograni4nie pokazateli TrustRank, otdelau6ie 17 blokov TrustRank, ispol'zuutsa kak porogovie zna4enia δ, o kotorix govorilos' v razdele 6.4.1. Poslednie bloki, sootvetstvuu6ie kajdomu porogovomu zna4eniu, predstavleni na gorizontal'nix osax, na vertikal'nix pokazani pokazateli Precision i Recall.  Ris.13: Precision and recall.
U xoro6ix saytov, soglasno TrustRank, visokie pokazateli, sootvetstvenno, 4em nije pokazatel', temi xuje sayt. Takim obrazom, pokazateli Precision i Recall demonstriruut lineynoe ponijenie i povi6enie. Obratite vnimanie na visokiy pokazatel' Precision (0,82) dla vsego primernogo mnojestva: podobnoe zna4enie ne mojet bit' ob6im dla problem tradicionnogo poiska informacii, obi4no sostoa6ix iz bol'6ogo ob&ema dokumentov, gde li6' 4ast' avlaetsa podxoda6ey opredelennomu zaprosu. V otli4ie ot etogo, na6e primernoe mnojestvo sostoit, glavnim obrazom, iz xoro6ix dokumentov, vse iz kotorix podxoda6ie. Vot po4emu bazoviy pokazatel' Precision dla mnojestva χ takoy 613/(613+135) = 0,82. 7. Zaklu4enie
S uveli4eniem razmerov i zna4enia seti, rol' poiskovix sistem stanovitsa vse bolee zna4itel'noy. Odnako sey4as ser'eznoy ugrozoy dla poiskovix sistem stal setevoy spam, iz-za kotorogo uxud6aetsa funkcionirovanie razli4nix servisov. Dla bor'bi so spamom, poiskovie sistemi ispol'zuut razli4nie metodi. Provedennoe v dannoy stat'e issledovanie stalo odnoy iz popitok formalizovat' problemu i predstavit' ee kompleksnoe re6enie. Soglasno rezul'tatam eksperimenta, vozmojno to4no opredelat' visokoka4estvennie xoro6ie stranici, ne avlau6iesa spamom. Nesmotra na prodelanniy ob&em raboti, punktov, dostoynix bolee vnimatel'nogo rassmotrenia, ostalos' dostato4no. V dopolnenie ko vsemu vi6eskazannomu, sleduet otmetit', 4to ispol'zovannie metodi mogut bit' ulu46eni. Naprimer, vmesto vibora vsego slu4aynogo mnojestva srazu, sleduet rassmotret' ispol'zovanie po6agovogo processa. Eto mojet stat' temoy budu6ix issledovaniy.
Obratite vnimanie, 4to su6estvuet neskol'ko ekvivalentnix opredeleniy ponatia PageRank, kotorie mogut nesu6estvenno otli4at'sa matemati4eskoy formulirovkoy i 4islovimi zna4eniami, no predstavlat' otnositel'no odinakovuu uporado4ennost' mejdu duma veb-stranicami. Problema opredelenia minimal'nogo nabora stranic, predstavlau6ix maksimal'nuu pokrivau6uu sposobnost', podobna probleme nezavisimogo nabora na napravlennom grafe, kak pokazano dalee. Veb- grafi mogut bit' transformirovani v napravlennie grafi ς" = (ν,ε"), gde rebro grafa (p,q) º ε" pokazivaet, 4to na stranicu q mojno popast' so stranici p. Sporno, 4to takaa informacia ne vnes¸t nikakix izmeneniy v ves' algoritm, tak kak on vklu4aet ob6irniy poisk s polinominal'nim vremenem ispolnenia. Zatem, naxojdenie minimal'nogo mnojestva obespe4ivaet maksimal'niy oxvat, kotoriy sxoden s maksimal'nim nezavisimim mnojestvom dla ς", kotoroe avlaetsa problemoy NP-polnoti. Domennoe ima– eto 4ast' URL, raspolojennaa mejdu prefiksom http://, kotoriy nazivaetsa sxema i pervim sle6om, kotoriy sleduet za visokourovnevim domenom, naprimer, .com ili TCP nomerom porta cervera. Naprimer, domennoe ima URL http://www.romver.ru/my/index.php – eto www.romver.ru. www.vldb.org Zoltan G'engi (Zoltan Gyongyi), Gektor Garsia-Molina (Hector Garcia-Molina), An Pedersen (Jan Pedersen)/Perevod pod red. Anni Makarovoy i Eleni Popovoy |
