PageRank, czyli jak Google stał się bogaty
28.09.2009 - Krzysztof Dryś
Prosty przykładZałóżmy, że Białego Pudelka odwiedza dziennie 100 000 osób oraz, że linkuje on do 1000 innych stron. Jeden z tych linków prowadzi do temperowanie-olowkow.pl. Można więc spodziewać się, że osób dziennie przejdzie z pierwszego portalu na drugi. Strony temperowanie-kredek.pl i temperowanie-dlugopisow.pl odwiedza dziennie odpowiednio tylko i osób. Każda z nich linkuje do stron. Szacujemy więc, że z pierwszej na temperowanie-olowkow.pl będzie dwudziestu gości, a z drugiej dziesięciu. Właśnie oszacowaliśmy, że na stronę temperowanie-dlugopisow.pl zagląda dziennie 130 osób. Ale żeby to zrobić musieliśmy wiedzieć, ile osób dziennie zagląda do stron, które do naszego portalu linkują. Niestety, takiej wiedzy raczej nie będziemy posiadać. Na szczęście okazuje się, że wcale nie jest nam ona konieczna! Załóżmy, dla uproszczenia, że internet składa się z czterech stron. Nazwijmy je: A,B,C i D. Na rysunku obok widać jak te strony wzajemnie do siebie linkują. Spróbujmy oszacować wartość . Na stronie C są dwa linki, w tym jeden do strony A. Oznacza to, że połowa ludzi ze strony C przechodzi na stronę A. Podobnie jedna trzecia ludzi ze strony D przechodzi na stronę A. Oznacza to, że: Tyle, że my nie znamy ani ani ! Spróbujmy oszacować , i w ten sam sposób, jak poprzednio oszacowaliśmy . To znaczy, patrząc na linki do tych stron. Daje to następujące równania: Na koniec załóżmy, że łącza popularność stron , , i wynosi . Oznacza to równanie: Teraz umiemy rozwiązać wszystkie równania. Uzyskujemy wynik: Chcemy powiedzieć, która strona jest najbardziej popularna. W ogóle nie potrzebujemy do tego N. Już teraz umiemy powiedzieć, że najpopularniejsza jest strona B. Następna w kolejności jest A, a potem C i D. W ten sposób udało się nam ustalić względną popularność stron patrząc tylko na linki między nimi. Właśnie poznaliśmy ogólną ideę stojącą za algorytmem PageRank - szacowanie popularności strony na podstawie prowadzących do niej linków. Podsumujmy założenia, które zrobiliśmy:
(3 ocen) |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com