CheiRank - CheiRank - Wikipedia

Uzly s odkazy v rovině PageRank a CheiRank

The CheiRank je vlastní vektor s maximální skutečnou vlastní hodnotou Matice Google ${ displaystyle G ^ {*}}$ konstruováno pro směrovanou síť s obrácenými směry odkazů. Je to podobné jako u PageRank vektor, který řadí síťové uzly v průměru úměrně k počtu příchozích odkazů, které jsou maximálním vlastním vektorem Matice Google ${ displaystyle G}$ s daným počátečním směrem odkazů. Kvůli inverzi směrů spojů CheiRank řadí síťové uzly v průměru úměrně počtu odchozích spojů. Protože každý uzel patří jak do CheiRank, tak do PageRank vektory se stává pořadí toku informací v směrované síti dvourozměrný.

Definice

Obr. 1. Distribuce volání procedur sítě Linux Kernel v rovině pravděpodobnosti PageRank

{ displaystyle x = log _ {10} P_ {i}}

a pravděpodobnost CheiRank

{ displaystyle y = log _ {10} {P} _ {i} ^ {*}}

pro Linux verze 2.6.32 s velikostí matice

{ displaystyle N = 285509}

na

{ displaystyle alpha = 0,85}

, barva ukazuje hustotu uzlů s bílou pro maximum a modrou pro minimum, černý prostor nemá žádné uzly (od Chepelianskii)

U dané směrované sítě je matice Google konstruována způsobem popsaným v článku Matice Google. The PageRank vektor je vlastní vektor s maximální skutečnou vlastní hodnotou ${ displaystyle lambda = 1}$ . To bylo představeno v^[1] a je popsána v článku PageRank. Podobným způsobem je CheiRank vlastní vektor s maximální skutečnou vlastní hodnotou matice ${ displaystyle G ^ {*}}$ postaveno stejným způsobem jako ${ displaystyle G}$ ale pomocí obráceného směru spojů v původně dané matici sousedství. Obě matice ${ displaystyle G}$ a ${ displaystyle G ^ {*}}$ patří do třídy operátorů Perron – Frobenius a podle Perron – Frobeniova věta CheiRank ${ displaystyle P_ {i} ^ {*}}$ a PageRank ${ displaystyle P_ {i}}$ vlastní vektory mají nezáporné složky, které lze interpretovat jako pravděpodobnosti.^[2]^[3] Tedy vše ${ displaystyle N}$ uzly ${ displaystyle i}$ sítě lze objednat v sestupném pořadí pravděpodobnosti s řadami ${ displaystyle K_ {i} ^ {*}, K_ {i}}$ pro CheiRank a PageRank ${ displaystyle P_ {i} ^ {*}, P_ {i}}$ resp. V průměru pravděpodobnost PageRank ${ displaystyle P_ {i}}$ je úměrná počtu příchozích odkazů s ${ displaystyle P_ {i} propto 1 / {K_ {i}} ^ { beta}}$ .^[4]^[5]^[6] Pro síť WWW (exponent) ${ displaystyle beta = 1 / ( nu -1) přibližně 0,9}$ kde ${ displaystyle nu přibližně 2,1}$ je exponent pro distribuci příchozích odkazů.^[4]^[5] Podobným způsobem je pravděpodobnost CheiRank průměrně úměrná počtu odchozích odkazů s ${ displaystyle P_ {i} ^ {*} propto 1 / {K_ {i} ^ {*}} ^ { beta ^ {*}}}$ s ${ displaystyle beta ^ {*} = 1 / ( nu ^ {*} - 1) přibližně 0,6}$ kde ${ displaystyle nu ^ {*} přibližně 2,7}$ je exponent pro distribuci odchozích odkazů na WWW.^[4]^[5] CheiRank byl představen pro síť volání procedur softwaru Linux Kernel v,^[7] samotný termín byl použit v Žirově.^[8] Zatímco PageRank zdůrazňuje velmi dobře známé a populární uzly, CheiRank zdůrazňuje velmi komunikativní uzly. Nejlepší uzly PageRank a CheiRank mají určitou analogii s úřady a rozbočovači, které se objevují v Algoritmus HITS^[9] ale HITS je závislá na dotazu, zatímco pravděpodobnosti pořadí ${ displaystyle P_ {i}}$ a ${ displaystyle P_ {i} ^ {*}}$ klasifikovat všechny uzly sítě. Vzhledem k tomu, že každý uzel patří jak CheiRank, tak PageRank, získáme dvourozměrné hodnocení síťových uzlů. Byly provedeny první studie PageRank v sítích s obráceným směrem odkazů^[10]^[11] ale vlastnosti dvourozměrného hodnocení nebyly podrobně analyzovány.

Obr. Závislost pravděpodobnosti PageRank

{ displaystyle P}

(červená křivka) a CheiRank

{ displaystyle P ^ {*}}

(modrá křivka) na odpovídajících indexech pořadí

{ displaystyle K}

a

{ displaystyle K ^ {*}}

. Přímé přerušované čáry znázorňují závislost zákonu síly na sklonu

{ displaystyle beta = 0,92; 0,57}

příslušně odpovídá

{ displaystyle beta = 1 / ( nu -1)}

(od Žirova)

Příklady

Příklad distribuce uzlů v rovině PageRank a CheiRank je uveden na obr.1 pro síť volání procedur softwaru Linux Kernel.^[7]

Obr. Distribuce hustoty článků Wikipedia English (2009) v rovině indexů PageRank a CheiRank

{ displaystyle 0 < ln K, ln K ^ {*} < ln N}

zobrazeno barvou s modrou pro minimum a bílou pro maximum (černá pro nulu); zelené / červené body ukazují 100 nejlepších osobností z PageRank / CheiRank, žluté plusy ukazují 100 nejlepších osobností z Hartovy knihy, počet článků

{ displaystyle N = 3282257}

(od Žirova)

Závislost ${ displaystyle P, P ^ {*}}$ na ${ displaystyle K, K ^ {*}}$ pro síť hypertextových odkazů síť Wikipedia Anglické články jsou znázorněny na obr.2 od Žirova. Distribuce těchto článků v rovině PageRank a CheiRank je znázorněna na obr.3 od Žirova. Rozdíl mezi PageRank a CheiRank je jasně patrný z názvů článků Wikipedie (2009) s nejvyšším hodnocením. V horní části PageRank máme 1. Spojené státy, 2. Spojené království, 3. Francie, zatímco pro CheiRank najdeme 1. Portál: Obsah / Přehled znalostí / Zeměpis a místa, 2. Seznam státních vůdců podle roku, 3. Portál: Obsah / Rejstřík / Zeměpis a místa. Je zřejmé, že PageRank vybírá první články o široce známém tématu s velkým počtem příchozích odkazů, zatímco CheiRank vybírá první vysoce komunikativní články s mnoha odchozími odkazy. Vzhledem k tomu, že články jsou distribuovány ve 2D, lze je řadit různými způsoby podle projekce 2D sady na řádek. Vodorovné a svislé čáry odpovídají PageRank a CheiRank, 2DRank kombinuje vlastnosti CheiRank a PageRank, jak je popsáno v Žirově.^[8] Poskytuje nejlepší články z Wikipedie 1. Indie, 2. Singapur, 3. Pákistán.

Hodnocení 2D zvýrazňuje vlastnosti článků na Wikipedii novým bohatým a plodným způsobem. Podle hodnocení PageRank má 100 nejlepších osobností popsaných v článcích na Wikipedii aktivity v 5 hlavních kategoriích: 58 (politika), 10 (náboženství), 17 (umění), 15 (věda), 0 (sport), a proto je důležitý význam politiků silně nadhodnocen. CheiRank dává 15, 1, 52, 16, 16, zatímco pro 2DRank najde 24, 5, 62, 7, 2. Takový typ 2D žebříčku může najít užitečné aplikace pro různé komplexně zaměřené sítě včetně WWW.

CheiRank a PageRank se přirozeně objevují pro světovou obchodní síť, nebo mezinárodní obchod, kde a souvisí s toky exportu a importu pro danou zemi.^[12]

Jsou zváženy možnosti vývoje dvourozměrných vyhledávačů založených na PageRank a CheiRank.^[13] Směrované sítě lze charakterizovat korelátorem mezi vektory PageRank a CheiRank: v určitých sítích se tento korelátor blíží nule (např. Síť Linux Kernel), zatímco jiné sítě mají velké hodnoty korelátoru (např. Wikipedia nebo univerzitní sítě).^[7]^[13]

Jednoduchý příklad sítě

Obr. Příklad směrované sítě

Obr. Související matice

{ displaystyle S}

Obr. Související matice

{ displaystyle S ^ {*}}

Jednoduchý příklad konstrukce matic Google ${ displaystyle G}$ a ${ displaystyle G ^ {*}}$ , který se používá ke stanovení souvisejících vektorů PageRank a CheiRank, je uveden níže. Příklad směrované sítě se 7 uzly je uveden na obr.4. Matice ${ displaystyle S}$ , postavený na pravidlech popsaných v článku Matice Google, je znázorněno na obr.5; související matice Google je ${ displaystyle G = alpha S + (1- alpha) ee ^ {T} / N}$ a vektor PageRank je pravým vlastním vektorem ${ displaystyle G}$ s vlastní hodnotou jednotky ( ${ displaystyle GP = P}$ ). Podobným způsobem, aby se určil vlastní vektor CheiRank, jsou všechny směry odkazů na obrázku 4 obrácené, pak matice ${ displaystyle S ^ {*}}$ je postaven podle stejných pravidel platných pro síť s obrácenými směry odkazů, jak je znázorněno na obr.6. Související matice Google je ${ displaystyle G ^ {*} = alpha S ^ {*} + (1- alpha) ee ^ {T} / N}$ a vektor CheiRank je správný vlastní vektor ${ displaystyle G ^ {*}}$ s vlastní hodnotou jednotky ( ${ displaystyle G ^ {*} P ^ {*} = P ^ {*}}$ ). Tady ${ displaystyle alpha přibližně 0,85}$ je tlumicí faktor při své obvyklé hodnotě.

Viz také

Reference

^ Brin S .; Page L. (1998), „Anatomie rozsáhlého hypertextového webového vyhledávače“, Počítačové sítě a systémy ISDN, 30 (1–7): 107, doi:10.1016 / S0169-7552 (98) 00110-X
^ Langville, Amy N.; Carl Meyer (2006). Google PageRank a další. Princeton University Press. ISBN 0-691-12202-4.
^ Austin, David (2008). „Jak Google najde vaši jehlu v kupce sena na webu“. Sloupce funkcí AMS.
^ ^A ^b ^C Donato D .; Laura L .; Leonardi S .; Millozzi S. (2004), „Vlastnosti webgrafu ve velkém měřítku“, Evropský fyzický deník B, 38 (2): 239, Bibcode:2004EPJB ... 38..239D, doi:10.1140 / epjb / e2004-00056-6, S2CID 10640375
^ ^A ^b ^C Pandurangan G .; Ranghavan P .; Upfal E. (2005), „Použití PageRank k charakterizaci struktury webu“, Internetová matematika., 3: 1, doi:10.1080/15427951.2006.10129114
^ Litvak N .; Scheinhardt W.R.W; Volkovich Y. (2008), Pravděpodobnostní vztah mezi In-Degree a PageRank, Přednášky v informatice, 4936, str. 72
^ ^A ^b ^C Chepelianskii, Alexei D. (2010). "Směrem k fyzickým zákonům pro softwarovou architekturu". arXiv:1003.5455 [cs.SE ].
^ ^A ^b Zhirov A.O .; Žirov O.V .; Shepelyansky D.L. (2010), „Dvojrozměrné hodnocení článků na Wikipedii“, Evropský fyzický deník B, 77 (4): 523, arXiv:1006.4270, Bibcode:2010EPJB ... 77..523Z, doi:10.1140 / epjb / e2010-10500-7, S2CID 18014470
^ Kleinberg, Jon (1999). "Autoritativní zdroje v prostředí hypertextových odkazů". Deník ACM. 46 (5): 604–632. doi:10.1145/324133.324140.
^ Fogaras, D. (2003), Kde začít procházet web?, Přednášky v informatice, 2877, str. 65
^ Hrisitidis V .; Hwang H .; Papakonstantinou Y (2008), „Hledání klíčových slov podle autorit v databázích“, ACM Trans. Database Syst., 33: 1, doi:10.1145/1331904.1331905
^ Ermann L .; Shepelyansky D.L. (2011). "Google matice světové obchodní sítě". Acta Physica Polonica A. 120 (6A): A. arXiv:1103.5027. Bibcode:2011AcPPA.120..158E. doi:10.12693 / APhysPolA.120.A-158. S2CID 18315654.
^ ^A ^b Ermann L .; Chepelianskii A.D .; Shepelyansky D.L. (2011). "Směrem k dvourozměrným vyhledávačům". Journal of Physics A: Mathematical and Theoretical. 45 (27): 275101. arXiv:1106.6215. Bibcode:2012JPhA ... 45A5101E. doi:10.1088/1751-8113/45/27/275101. S2CID 14827486.

externí odkazy

[1] Brin S .; Page L. (1998), „Anatomie rozsáhlého hypertextového webového vyhledávače“, Počítačové sítě a systémy ISDN, 30 (1–7): 107, doi:10.1016 / S0169-7552 (98) 00110-X

[2] Langville, Amy N.; Carl Meyer (2006). Google PageRank a další. Princeton University Press. ISBN 0-691-12202-4.

[3] Austin, David (2008). „Jak Google najde vaši jehlu v kupce sena na webu“. Sloupce funkcí AMS.

[Donato-4] A ^b ^C Donato D .; Laura L .; Leonardi S .; Millozzi S. (2004), „Vlastnosti webgrafu ve velkém měřítku“, Evropský fyzický deník B, 38 (2): 239, Bibcode:2004EPJB ... 38..239D, doi:10.1140 / epjb / e2004-00056-6, S2CID 10640375

[Pandurangan-5] A ^b ^C Pandurangan G .; Ranghavan P .; Upfal E. (2005), „Použití PageRank k charakterizaci struktury webu“, Internetová matematika., 3: 1, doi:10.1080/15427951.2006.10129114

[6] Litvak N .; Scheinhardt W.R.W; Volkovich Y. (2008), Pravděpodobnostní vztah mezi In-Degree a PageRank, Přednášky v informatice, 4936, str. 72

[Chepelianskii-7] A ^b ^C Chepelianskii, Alexei D. (2010). "Směrem k fyzickým zákonům pro softwarovou architekturu". arXiv:1003.5455 [cs.SE ].

[Zhirov-8] A ^b Zhirov A.O .; Žirov O.V .; Shepelyansky D.L. (2010), „Dvojrozměrné hodnocení článků na Wikipedii“, Evropský fyzický deník B, 77 (4): 523, arXiv:1006.4270, Bibcode:2010EPJB ... 77..523Z, doi:10.1140 / epjb / e2010-10500-7, S2CID 18014470

[9] Kleinberg, Jon (1999). "Autoritativní zdroje v prostředí hypertextových odkazů". Deník ACM. 46 (5): 604–632. doi:10.1145/324133.324140.

[10] Fogaras, D. (2003), Kde začít procházet web?, Přednášky v informatice, 2877, str. 65

[11] Hrisitidis V .; Hwang H .; Papakonstantinou Y (2008), „Hledání klíčových slov podle autorit v databázích“, ACM Trans. Database Syst., 33: 1, doi:10.1145/1331904.1331905

[12] Ermann L .; Shepelyansky D.L. (2011). "Google matice světové obchodní sítě". Acta Physica Polonica A. 120 (6A): A. arXiv:1103.5027. Bibcode:2011AcPPA.120..158E. doi:10.12693 / APhysPolA.120.A-158. S2CID 18315654.

[Ermann-13] A ^b Ermann L .; Chepelianskii A.D .; Shepelyansky D.L. (2011). "Směrem k dvourozměrným vyhledávačům". Journal of Physics A: Mathematical and Theoretical. 45 (27): 275101. arXiv:1106.6215. Bibcode:2012JPhA ... 45A5101E. doi:10.1088/1751-8113/45/27/275101. S2CID 14827486.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]