Matice Google - Google matrix

Tento článek má několik problémů. Prosím pomozte vylepši to nebo diskutovat o těchto otázkách na internetu diskusní stránka. (Zjistěte, jak a kdy tyto zprávy ze šablony odebrat) tento článek poskytuje nedostatečný kontext osobám, které toto téma neznají. Prosím pomozte vylepšit článek podle poskytuje čtenáři více kontextu. (Březen 2019) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) tento článek má nejasný styl citace. Použité odkazy mohou být jasnější odlišným nebo konzistentním stylem citace a poznámka pod čarou. (Prosince 2014) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Obr. 1. Matice Google sítě článků Wikipedie, napsaná v základech indexu PageRank; je zobrazen fragment nejlepších prvků matice 200 x 200, celková velikost N = 3282257 (od ^[1])

A Matice Google je zvláštní stochastická matice který používá Google je PageRank algoritmus. Matice představuje graf s hranami představujícími odkazy mezi stránkami. PageRank každé stránky lze poté iterativně generovat z matice Google pomocí metoda napájení. Aby se však energetická metoda sbíhala, musí být matice stochastická, neredukovatelné a neperiodické.

Matice sousedství A a Markovova matice S

Za účelem vygenerování matice Google G, musíme nejprve vygenerovat matici sousedství A což představuje vztahy mezi stránkami nebo uzly.

Za předpokladu, že existují N stránky, můžeme vyplnit A provedením následujícího:

1. Maticový prvek ${displaystyle A_ {i, j}}$ je naplněn 1 if uzlem ${displaystyle j}$ má odkaz na uzel ${displaystyle i}$a 0 jinak; toto je matice sousedství odkazů.
2. Související matice S odpovídající přechodům v a Markovův řetězec dané sítě je konstruováno z A dělením prvků sloupce "j" počtem ${displaystyle k_ {j} = Sigma _ {i = 1} ^ {N} A_ {i, j}}$ kde ${displaystyle k_ {j}}$ je celkový počet odchozích odkazů z uzluj do všech ostatních uzlů. Sloupce s prvky nulové matice, které odpovídají visícím uzlům, jsou nahrazeny konstantní hodnotou 1 / N. Takový postup přidává odkaz z každého stavu klesání a houpání ${displaystyle a}$ do každého dalšího uzlu.
3. Nyní konstrukcí součet všech prvků v libovolném sloupci matice S se rovná jednotě. Tímto způsobem matice S je matematicky dobře definovaný a patří do třídy Markovových řetězců a do třídy operátorů Perron-Frobenius. To dělá S vhodné pro PageRank algoritmus.

Konstrukce Google matice G

Obr. Google matice sítě Cambridge University (2006), hrubozrnné maticové prvky jsou zapsány do základů PageRank indexu, je uvedena celková velikost N = 212710 (z ^[1])

Potom může být konečná matice Google G vyjádřena pomocí S tak jako:

${displaystyle G_ {ij} = alfa S_ {ij} + (1-alfa) {frac {1} {N}} ;;;;;;;;;;;; (1)}$

Konstrukcí se součet všech nezáporných prvků uvnitř každého sloupce matice rovná jednotce. Numerický koeficient ${displaystyle alpha}$ je známý jako tlumící faktor.

Obvykle S je řídká matice a pro moderní směrované sítě má pouze asi deset nenulových prvků v řádku nebo sloupci, tedy jen asi 10N k násobení vektoru maticí je zapotřebí násobeníG.^[2][3]

Příklady matice Google

Příklad matice ${displaystyle S}$ konstrukce v rovnici (1) v rámci jednoduché sítě je uvedena v článku CheiRank.

Pro vlastní matici používá Google tlumicí faktor ${displaystyle alpha}$ kolem 0,85.^[2][3][4] Termín ${displaystyle (1-alfa)}$ dává pravděpodobnost surfaře, že náhodně skočí na libovolnou stránku. Matice ${displaystyle G}$ patří do třídy Provozovatelé společnosti Perron-Frobenius z Markovovy řetězy.^[2] Příklady struktury matice Google jsou uvedeny na obrázku 1 pro síť hypertextových odkazů na články Wikipedie v roce 2009 v malém měřítku a na obrázku 2 pro síť University of Cambridge v roce 2006 ve velkém měřítku.

Spektrum a vlastní stavy G matice

Obr. Spektrum vlastních čísel Google matice University of Cambridge z obr ${displaystyle alpha = 1}$, modré body ukazují vlastní čísla izolovaných podprostorů, červené body ukazují vlastní čísla základní složky (z ^[5])

Pro ${displaystyle 0$ existuje pouze jedna maximální vlastní hodnota ${displaystyle lambda = 1}$ s odpovídajícím pravým vlastním vektorem, který má nezáporné prvky ${displaystyle P_ {i}}$ což lze považovat za stacionární rozdělení pravděpodobnosti.^[2] Tyto pravděpodobnosti seřazené podle jejich klesajících hodnot dávají vektor PageRank ${displaystyle P_ {i}}$ s hodnocením PageRank ${displaystyle K_ {i}}$ používá vyhledávání Google k hodnocení webových stránek. Obvykle je to pro World Wide Web ${displaystyle Ppropto 1 / K ^ {eta}}$ s ${displaystyle eta cca 0,9}$. Počet uzlů s danou hodnotou PageRank se změní na ${displaystyle N_ {P} propto 1 / P ^ {u}}$ s exponentem ${displaystyle u = 1 + 1 / eta přibližně 2,1}$.^[6][7] Levý vlastní vektor v ${displaystyle lambda = 1}$ má konstantní maticové prvky. S ${displaystyle 0$ všechna vlastní čísla se pohybují jako ${displaystyle lambda _ {i} ightarrow alfa lambda _ {i}}$ kromě maximálního vlastního čísla ${displaystyle lambda = 1}$, který zůstává nezměněn.^[2] Vektor PageRank se liší podle ${displaystyle alpha}$ ale jiné vlastní vektory s ${displaystyle lambda _ {i} <1}$ zůstanou nezměněny kvůli jejich ortogonalitě vůči konstantnímu levému vektoru v ${displaystyle lambda = 1}$. Rozdíl mezi ${displaystyle lambda = 1}$ a další bytí vlastních čísel ${displaystyle 1-alfa cca 0,15}$ poskytuje rychlou konvergenci náhodného počátečního vektoru do PageRank přibližně po 50 násobeních ${displaystyle G}$ matice.

Obr. Rozdělení vlastních čísel ${displaystyle lambda _ {i}}$ matic Google v komplexní rovině v ${displaystyle alpha = 1}$ pro sítě slovníků: Roget (A, N = 1022), ODLIS (B, N = 2909) a FOLDOC (C, N = 13356); WWW sítě britských univerzit: University of Wales (Cardiff) (D, N = 2778), Birmingham City University (E, N = 10631), Keele University (Staffordshire) (F, N = 11437), Nottingham Trent University (G, N = 12660), Liverpool John Moores University (H, N = 13578) (údaje pro univerzity jsou za rok 2002) (od ^[8])

Na ${displaystyle alpha = 1}$ matice ${displaystyle G}$má obecně mnoho zdegenerovaných vlastních čísel ${displaystyle lambda = 1}$(viz např. [6]^[8]). Příklady spektra vlastních čísel matice Google různých směrovaných sítí je znázorněno na obr.3 z ^[5] a obr. 4 z.^[8]

Matici Google lze také vytvořit pro sítě Ulam generované metodou Ulam [8] pro dynamické mapy. Spektrální vlastnosti takových matic jsou popsány v [9,10,11,12,13,15].^[5][9] V řadě případů je spektrum popsáno fraktálním Weylovým zákonem [10,12].

Obr. Rozdělení vlastních čísel ${displaystyle lambda}$ v komplexní rovině pro matici Google ${displaystyle G}$ linuxového jádra verze 2.6.32 s velikostí matice ${displaystyle N = 285509}$ na ${displaystyle alpha = 0,85}$, jednotkový kruh je zobrazen plnou křivkou (od ^[9])

Obr.6 Hrubozrnné rozdělení pravděpodobnosti pro vlastní stavy matice Google pro jádro Linuxu verze 2.6.32. Vodorovné čáry zobrazují prvních 64 vlastních vektorů seřazených svisle podle ${displaystyle | lambda _ {i} |}$ (z ^[9])

Matici Google lze vytvořit i pro jiné směrované sítě, např. pro síť volání procedur softwaru Linux Kernel představeného v [15]. V tomto případě spektrum ${displaystyle lambda}$ je popsán fraktálním Weylovým zákonem s fraktální dimenzí ${displaystyle d cca 1,3}$ (viz obr. 5 z ^[9]). Numerická analýza ukazuje, že vlastní stavy matice ${displaystyle G}$ jsou lokalizovány (viz obr.6 z ^[9]). Arnoldiho iterace metoda umožňuje vypočítat mnoho vlastních čísel a vektorů pro matice poměrně velké velikosti [13].^[5][9]

Další příklady ${displaystyle G}$ matice zahrnuje Google matici mozku [17] a řízení podnikových procesů [18], viz také.^[1] Aplikace maticové analýzy Google na sekvence DNA jsou popsány v [20]. Takový přístup pomocí matice Google umožňuje také analyzovat zapletení kultur prostřednictvím hodnocení vícejazyčných článků na Wikipedii o osobách [21]

Historické poznámky

Matici Google s tlumícím faktorem popsal Sergej Brin a Larry Page v roce 1998 [22], viz také články o historii PageRank [23], [24].

Viz také

• CheiRank
• Arnoldiho iterace
• Markovův řetězec
• Operátor přenosu
• Perron – Frobeniova věta
• Webové vyhledávače

Reference

externí odkazy

• Google matrix ve Scholarpedia
• Vypnutí Google PR
• Video přednášky na IHES Workshop „Google matrix: základní, aplikace a další“, říjen 2018