211service.com
Vědec najde algoritmus PageRank-Type ze 40. let 20. století
Algoritmus PageRank je klíčovou součástí metody Google pro hodnocení webových stránek ve výsledcích vyhledávání. Využívá síť odkazů mezi webovými stránkami k určení jejich hodnoty a, což je známé, posuzuje stránku jako důležitou, pokud na ni odkazují jiné důležité stránky.
Jedním z klíčových rysů této myšlenky je, že vyžaduje iterativní přístup k neustálému přehodnocování hodnoty stránky, protože se mění důležitost ostatních. Iterativní hodnotící algoritmy se od té doby staly důležitou součástí teorie sítí.
Hodnocení PageRank bylo vyvinuto v roce 1998 zakladateli společnosti Google Sergey Brin a Larry Page a jeho dopad byl takový, že je snadné zapomenout, že tento přístup nebyl úplně nový. Massimo Franceschet na univerzitě v Udine v Itálii poukazuje na to, že tato myšlenka byla ve vědě 20. století mnohokrát úspěšně využita, dokonce ještě předtím, než se narodili Brin a Page. Dnes představuje krátkou historii iterativních hodnotících algoritmů a mapuje jejich vývoj před vznikem společnosti Google.
Začíná v obráceném chronologickém pořadí prací Jona Kleinberga, počítačového vědce z Cornell University, který jen o několik let dříve vyvinul téměř identický přístup k hodnocení PageRank. Brin a Page dokonce odkazují na jeho práci ve svém slavném článku zavádějícím PageRank.
Kleinberg nazval svůj algoritmus Hypertext Induced Topic Search nebo HITS a považoval webové stránky za centra a orgány. Použila kruhovou definici, že autority jsou stránky, na které odkazují rozbočovače, a rozbočovače jsou stránky, které odkazují na autority a jejichž řešení vyžaduje iterativní přístup.
V opojných dnech dotcom boomu na konci 20. století, než se Google stal tak úspěšným, se Kleinbergově práci dostalo značné mediální pozornosti.
Franceschet také zkoumá práci Gabriela Pinskiho a Francise Narina, kteří vyvinuli způsob hodnocení časopisů. Jejich pravidlem bylo, že časopis je důležitý, pokud je citován jinými důležitými časopisy. Stejně jako PageRank a HITS to vyžaduje iterativní metodu k využití struktury odkazů mezi časopisy k vytvoření hodnocení.
Dlouho předtím však podobným způsobem analyzoval sociální sítě Charles H Hubbell z Kalifornské univerzity v Santa Barbaře. V roce 1965 publikoval techniku určování důležitosti jednotlivců na základě důležitosti lidí, kteří je podporují. To má opět charakteristickou kruhovou definici a iterativní řešení. Hubbell je uznáván mnoha, včetně Kleinberga, jako průkopník v teorii iterativního hodnocení.
Ale velkým překvapením je Franceschetův objev ještě dřívějšího předchůdce PageRanku v práci harvardského ekonoma Wassily Leontiefa. V roce 1941 Leontief publikoval článek, ve kterém rozděluje ekonomiku země na sektory, které si navzájem dodávají a přijímají zdroje, i když ne ve stejné míře. Jedna důležitá otázka zní: jaká je hodnota každého sektoru, když jsou tak těsně integrovány? Leontiefovou odpovědí bylo vyvinout iterativní metodu oceňování každého sektoru na základě důležitosti sektorů, které jej dodávají. Zní povědomě? V roce 1973 byla Leontiefovi za tuto práci udělena Nobelova cena za ekonomii.
Je jasné, že myšlenky PageRanku mají úctyhodnou historii, ale překvapením je, že se datují přinejmenším do 40. let minulého století. Bude zajímavé sledovat, jestli někdo najde nějakou podobnou práci, která tomu předcházela.
Ref: arxiv.org/abs/1002.2858 : PageRank: Postavte se na ramena obrů