211service.com
Naukowiec znajduje algorytm typu PageRank z lat 40.
Algorytm PageRank jest kluczową częścią metody Google rankingu stron internetowych w wynikach wyszukiwania. Wykorzystuje sieć linków między stronami internetowymi, aby określić ich wartość i, jak wiadomo, ocenia stronę jako ważną, jeśli jest do niej linkowana przez inne ważne strony.
Jedną z kluczowych cech tego pomysłu jest to, że wymaga iteracyjnego podejścia do ciągłej ponownej oceny wartości strony, ponieważ ważność innych jest różna. Algorytmy iteracyjnego rankingu stały się od tego czasu ważną częścią teorii sieci.
PageRank został opracowany w 1998 roku przez założycieli Google, Sergeya Brina i Larry'ego Page'a, a jego wpływ był tak duży, że łatwo zapomnieć, że podejście nie było całkowicie nowatorskie. Massimo Franceschet z Uniwersytetu w Udine we Włoszech wskazuje, że pomysł ten był wielokrotnie z powodzeniem wykorzystywany w nauce XX wieku, jeszcze zanim narodzili się Brin i Page. Dziś przedstawia krótką historię iteracyjnych algorytmów rankingowych i wykresy ich ewolucji przed pojawieniem się Google.
Rozpoczyna w odwrotnej kolejności chronologicznej od prac Jona Kleinberga, informatyka z Cornell University, który zaledwie kilka lat wcześniej opracował niemal identyczne podejście do PageRank. Brin i Page odwołują się nawet do jego pracy w swoim słynnym artykule przedstawiającym PageRank.
Kleinberg nazwał swój algorytm Hypertext Induced Topic Search lub HITS i traktował strony internetowe jako huby i autorytety. Wykorzystano w nim cykliczną definicję, według której urzędy są stronami wskazywanymi przez huby, a huby to strony, które wskazują urzędy, a ich rozwiązanie wymaga iteracyjnego podejścia.
W upalnych dniach boomu internetowego pod koniec XX wieku, zanim Google odniósł taki sukces, prace Kleinberga były szeroko komentowane w mediach.
Franceschet analizuje również prace Gabriela Pinskiego i Francisa Narina, którzy opracowali sposób rankingu czasopism. Ich zasadą było, że czasopismo jest ważne, jeśli jest cytowane przez inne ważne czasopisma. Podobnie jak PageRank i HITS, wymaga to iteracyjnej metody wykorzystania struktury powiązań między czasopismami w celu stworzenia rankingu.
Jednak na długo wcześniej Charles H Hubbell z Uniwersytetu Kalifornijskiego w Santa Barbara w podobny sposób analizował sieci społecznościowe. W 1965 opublikował technikę określania ważności jednostek na podstawie ważności osób, które je popierają. To znowu ma charakterystyczną definicję kołową i rozwiązanie iteracyjne. Hubbell jest uznawany przez wielu, w tym Kleinberga, za pioniera w iteracyjnej teorii rankingowej.
Ale wielką niespodzianką jest odkrycie przez Francescheta jeszcze wcześniejszego prekursora PageRank w pracy ekonomisty z Harvardu Wassily'ego Leontiefa. W 1941 r. Leontief opublikował artykuł, w którym dzieli gospodarkę kraju na sektory, które zarówno dostarczają, jak i otrzymują od siebie zasoby, choć nie w równej mierze. Jedno ważne pytanie brzmi: jaka jest wartość każdego sektora, gdy są one tak ściśle zintegrowane? Odpowiedzią Leontiefa było opracowanie iteracyjnej metody wyceny każdego sektora w oparciu o znaczenie sektorów, które go dostarczają. Brzmi znajomo? W 1973 Leontief otrzymał za tę pracę Nagrodę Nobla w dziedzinie ekonomii.
Jasne jest, że idee stojące za PageRank mają szacowną historię, ale zaskoczeniem jest to, że sięgają co najmniej lat 40. XX wieku. Ciekawie będzie zobaczyć, czy ktoś może znaleźć podobną pracę, która poprzedza to.
Nr ref.: arxiv.org/abs/1002.2858 : PageRank: Stań na ramionach gigantów