구글 매트릭스

그림 1. PageRank 인덱스에 기재된 위키피디아 기사 네트워크의 구글 매트릭스. 상위 200 X 200 매트릭스 요소의 fragment를 나타내며, 총 사이즈 N=3282257 (from)

Google 매트릭스는 Google의 PageRank 알고리즘에 사용되는 특정 확률 매트릭스입니다.매트릭스는 페이지 간의 링크를 나타내는 가장자리가 있는 그래프를 나타냅니다.각 페이지의 PageRank는 Google 매트릭스에서 power method를 사용하여 반복적으로 생성할 수 있습니다.단, 멱법 수렴을 위해서는 행렬이 확률적, 환원 불가능 및 비주기적이어야 합니다.

인접행렬 A와 마르코프행렬 S

구글 매트릭스 G를 생성하기 위해서는 먼저 페이지 또는 노드 간의 관계를 나타내는 인접 매트릭스 A를 생성해야 합니다.

N페이지라고 가정하면, 다음과 같이 A를 기입할 수 있습니다.

매트릭스 $A_{i,j}$ $A_{i,j}$ i $A_{i,j}$ {\ $display$ $A_{i,$ j}는 $A_{i,j}$ $노드$ j {\ $display$ j $}$ 에 $j$ $노드$ i {\ $displaystyle$ i $i$ 에 대한 링크가 있는 경우 1로 채워지고 그 이외의 경우 0으로 채워집니다.이것은 링크의 인접 매트릭스입니다.
소정의 네트워크의 마르코프 체인에서의 천이에 대응하는 관련행렬 S는 $k_{j}=\Sigma _{i=1}^{N}A_{i,j}$ $k_{j}=\Sigma _{i=1}^{N}A_{i,j}$ $\{$ $display k_{j$ }=\ $Sigma_{i=1}^N}A_{i,$ jdisplay k_j}{i, $j$ }{j}{i $,$ j}{ $display$ k_j}{i $k_{j}=\Sigma _{i=1}^{N}A_{i,j}$ }{i}}{i}}{display}}{i}}{n}}}{ $k_{j}=\Sigma _{i=1}^{N}A_{i,j}$ }}{cline}}}}}{cline}}}로 A로 나누어 A에서 구성된다.다른 모든 노드에 접속합니다.행렬 요소가 0인 컬럼(당글링 노드에 대응)은 상수값 1/N으로 대체됩니다. $이러한$ 절차에 따라 모든 싱크에서 $다른$ 모든 노드에 $a$ $링크$ 가 추가됩니다 $.$
이제 구성에서는 행렬 S의 모든 열에 있는 모든 원소의 합이 합계와 같습니다.이렇게 해서 행렬 S는 수학적으로 잘 정의되고 마르코프 사슬의 클래스와 페론-프로베니우스 연산자의 클래스에 속합니다.따라서 S는 PageRank 알고리즘에 적합합니다.

구글 매트릭스 G 구축

그림 2. 캠브리지 대학 네트워크의 구글 매트릭스(2006년), PageRank 인덱스의 베이스에 굵은 매트릭스 요소를 기입하고, 합계 사이즈 N=212710을 나타낸다(from).

최종 구글 매트릭스 G는 S를 통해 다음과 같이 표현될 수 있다.

G_{ij}=\alpha S_{ij}+(1-\alpha){\frac {1}{N}\;\;\;\;\;\;\;;(1)

이 구성에 의해 각 매트릭스 컬럼 내의 모든 음이 아닌 요소의 합계는 통일성과 같다. $(\displaystyle \alpha)$ 는 $\alpha$ 감쇠계수로 알려져 있습니다.

일반적으로 S는 희박한 행렬이며, 현대의 다이렉트 네트워크의 경우 라인 또는 열에 0이 아닌 요소가 10개 정도밖에 없기 때문에 벡터에 행렬 ^[2]^[3]G를 곱하는 데 필요한 것은 약 10N배입니다.

Google 매트릭스의 예

간단한 네트워크 내에서 Eq.(1)를 통해 $매트릭스$ S(\ $display style$ S $)$ 를 $S$ 구축하는 예를 CheiRank 기사에 제시합니다.

실제 매트릭스의 경우 Google은 0.85 정도의 감쇠 $(\displaystyle\$ alpha)^[2]^[3]^[4]를 $\alpha$ 사용합니다. $(1-\alpha )$ ( $(1-\alpha )$ - $(1-\alpha )$ α $)({displaystyle (1-\$ alpha)})는 $(1-\alpha)$ 임의의 페이지에서 랜덤으로 점프할 가능성을 제공합니다. $행렬$ G $(\displaystyle$ G $)$ 는 $G$ 마르코프 ^[2]사슬의 페론-프로베니우스 연산자 클래스에 속합니다.구글 매트릭스 구조의 예는 2009년 위키피디아 기사 하이퍼링크 네트워크의 경우 그림 1과 2006년 케임브리지 대학 네트워크의 경우 그림 2에 나와 있다.

G 행렬의 스펙트럼 및 고유 상태

그림 3. 그림 2의 케임브리지 대학 Google 매트릭스 고유값 스펙트럼은 α

\alpha =1

(\displaystyle \alpha =

1)로

\alpha =1

파란색 점은 고립된 부분공간의 고유값을 나타내고, 빨간색 점은 핵심성분의 고유값을 나타낸다(부터).

0 $0<\alpha <1$ < $0<\alpha <1$ < $0<\alpha <1$ \ $displaystyle$ 0 < \ $alpha$ < $1$ } $0<\alpha <1$ $P_{i}$ $\lambda =1$ \ $displaystyle$ \ $displayda =$ 1 with $\lambda =1$ the 、 non-negative $P_{i}$ $Pi {$ $displaystyle$ $P_$ {i $}$ ^[2]} non for for 。이러한 확률의 감소에 따라 PageRank $P_{i}$ $(\$ 와 $P_{i}$ Google 검색에서 웹 페이지의 순위를 매기기 위해 사용되는 $K_{i}$ $(\displaystyle K_i})$ 가 $K_{i}$ 지정됩니다.보통 월드 와이드 웹에서는 P $P\propto 1/K^{\beta }$ 1 / $P\propto 1/K^{\beta }$ (\ $displaystyle$ P $\propto$ 1 $/K^{\beta})$ 와 $P\propto 1/K^{{\beta }}$ β $\beta \approx 0.9$ 0 $.9$ (\ $displaystyle \beta \$ 。 $N_{P}\propto 1/P^{\nu }$ PageRank 값을 가진 노드의 수는 N $N_{P}\propto 1/P^{\nu }$ 1 / $N_{P}\propto 1/P^{\nu }$ ${\$ { $style$ N_ ${P}\propto$ 1/ $P^{\nu }$ } $\nu =1+1/\beta \approx 2.1$ $\nu =1+1/\beta \approx 2.1$ $\nu =1+1/\beta \approx 2.1$ + 1 / $\nu =1+1/\beta \approx 2.1$ 2.1 { $display$ \ $nu$ $\lambda =1$ $1$ / 1 $\nu =1+1/\beta \approx 2.1$ ^[6]^[7]1 \ } 1 $N_{P}\propto 1/P^{\nu }$ 1 1 1 $\lambda =1$ 111111111111111111111111111111111111111111111111111111111111111110 $0<\alpha$ < $0<\alpha$ { $displaystyle$ 0 < \ $alpha }$ 일 $0<\alpha$ $0<\alpha$ 최대 $\lambda =1$ $=$ $\lambda =1$ { $displaystyle$ \ $displayda$ _ { i }을 $제외$ 하고 모든 고유값은 $\lambda _{i}\rightarrow \alpha \lambda _{i}$ ^[2] $\lambda _{i}\rightarrow \alpha \lambda _{i}$ ${\$ $\lambda _{i}\rightarrow \alpha \lambda _{i}$ { $displaystyle$ \ $displayda$ _ $\lambda =1$ { $i$ $\lambda =1$ 로 $이동$ 합니다 $\lambda _{i}\rightarrow \alpha \lambda _{i}$ .PageRank 벡터는 $\alpha$ α {\ $displaystyle \alpha}$ 에 $\alpha$ $\alpha$ 다르지만 $\lambda _{i}<1$ i < $\lambda _{i}<1$ {\ $displaystyle \displayda _{$ i}<1}인 $\lambda _{i}<1$ 다른 고유 벡터는 $\lambda =1$ $=$ 1 { $displaystyle \displayda$ $1$ }의 상수 왼쪽 벡터에 대한 직교성이 있기 때문에 변경되지 않습니다. $\lambda =1$ $\lambda =1$ { $displaystyle \displayda =1}$ 과 $\lambda =1$ 기타 고유값 $1-\alpha \approx 0.15$ - $1-\alpha \approx 0.15$ 0. $1-\alpha \approx 0.15$ ${displaystyle 1-\alpha$ \ $약$ 0. $15}$ 사이의 $1-\alpha \approx 0.15$ 갭은 G{ $displaystyle$ G $}$ 매트릭스에서 $G$ $약$ 50배 후에 PageRank에 랜덤 초기 벡터가 빠르게 수렴된다.

그림4. 사전 네트워크용 α

\alpha =1

{\displaystyle \alpha

=1}

의

\alpha =1

복소 평면 내 Google 매트릭스 고유값

\lambda _{i}

i {\

displaystyle

\

da

_{i}

의

\lambda _{i}

분포: Roget (A, N=2909) 및 FoldOC (C, N=136 WW)웨일스 대학교(Cardiff) (D, N=2778), 버밍엄 시티 대학교(E, N=1931), 킬 대학교(Staffordshire) (F, N=1937), 노팅엄 트렌트 대학교(G, N=1960), 리버풀 존 무어스 대학교(N135, N)

$\alpha =1$ $\alpha =1$ 1 $(예$ : [6] 참조)에서 $행렬$ G(\ $displaystyle$ $\alpha =$ $1$ )는 $G$ 일반적으로 많은 축퇴 고유값 $\lambda =1$ $\lambda =1$ $1($ : [6]^[8] 참조)을 가집니다.다양한 다이렉트 네트워크의 Google 매트릭스의 고유치 스펙트럼의 예를 그림 3과 ^[8]그림 4에 나타낸다.

Google 매트릭스는 동적 지도용 Ulam 메서드 [8]에 의해 생성된 Ulam 네트워크를 위해 구성할 수도 있습니다.그러한 행렬의 스펙트럼 특성은 [9,10,11,12,13,15]^[5]^[9]에 설명되어 있다.다수의 경우 스펙트럼은 프랙탈 와일 법칙[10,12]에 의해 설명된다.

그림5. Linux 커널

N=285509

2.6.32의 Google

매트릭스

G(\

displaystyle

G

)

의

G

복소 평면에서의 고유값

\lambda

(\

displaystyle \displayda)

의

\lambda

N=285509

분포는 α

\alpha =0.85

0

.

\

alpha =

0

85

)에서

\alpha =0.85

곡선으로 나타낸다.

그림 6 Linux 커널 버전 2.6.32용 Google 매트릭스의 고유 상태에 대한 대략적인 확률 분포.가로줄은 §

displaystyle \lambda

_

{i} }(

에서)에 의해 수직으로 정렬된 첫 번째 64개의 고유 벡터를 나타냅니다.

Google 매트릭스는 [15]에 소개된 Linux 커널 소프트웨어의 프로시저 호출 네트워크와 같은 다른 다이렉트 네트워크에도 구성할 수 있습니다. $\lambda$ 경우 § $\lambda$ { $displaystyle$ $\lambda}$ 의 $\lambda$ 스펙트럼은 프랙탈 치수 $d\approx 1.3$ 1 $.3인$ $d\approx 1.3$ 프랙탈 와일 법칙에 의해 기술된다(의 그림 5 $참조$ ).수치분석 결과 $G$ 의 $G$ 고유상태는 현지화되어 있습니다(의 그림 6 참조).Arnoldi 반복 방법을 사용하면 크기가 큰 행렬에 대해 많은 고유값과 고유 벡터를 계산할 수 있다[13].^[5]^[9]

G $(\displaystyle$ G $)$ 매트릭스의 $G$ $다른$ 예로는 Google Brain 매트릭스[17]와 비즈니스 프로세스 관리[18]가 있습니다.^[1]참조 항목도 참조하십시오.DNA 염기서열에 대한 Google 매트릭스 분석의 적용은 [20]에 설명되어 있다.이러한 구글 매트릭스 접근방식은 사람에 대한 다국어 위키피디아 기사 순위를 매겨 문화의 얽힘을 분석할 수도 있다[21].

이력 메모

감쇠 계수를 가진 Google 매트릭스는 1998년 Sergey Brin과 Larry Page에 의해 기술되었습니다. PageRank의 역사에 대한 기사도 참조하십시오[23].

「」를 참조해 주세요.

레퍼런스

^ ^a ^b ^c Ermann, L.; Chepelianskii, A. D.; Shepelyansky, D. L. (2011). "Towards two-dimensional search engines". Journal of Physics A. 45 (27): 275101. arXiv:1106.6215. Bibcode:2012JPhA...45A5101E. doi:10.1088/1751-8113/45/27/275101. S2CID 14827486.
^ ^a ^b ^c ^d ^e Langville, Amy N.; Meyer, Carl (2006). Google's PageRank and Beyond. Princeton University Press. ISBN 978-0-691-12202-1.
^ ^a ^b Austin, David (2008). "How Google Finds Your Needle in the Web's Haystack". AMS Feature Columns.
^ Law, Edith (2008-10-09). "PageRank Lecture 12" (PDF).
^ ^a ^b ^c ^d Frahm, K. M.; Georgeot, B.; Shepelyansky, D. L. (2011-11-01). "Universal emergence of PageRank". Journal of Physics A. 44 (46): 465101. arXiv:1105.1062. Bibcode:2011JPhA...44T5101F. doi:10.1088/1751-8113/44/46/465101. S2CID 16292743.
^ Donato, Debora; Laura, Luigi; Leonardi, Stefano; Millozzi, Stefano (2004-03-30). "Large scale properties of the Webgraph" (PDF). European Physical Journal B. 38 (2): 239–243. Bibcode:2004EPJB...38..239D. CiteSeerX 10.1.1.104.2136. doi:10.1140/epjb/e2004-00056-6. S2CID 10640375.
^ Pandurangan, Gopal; Ranghavan, Prabhakar; Upfal, Eli (2005). "Using PageRank to Characterize Web Structure" (PDF). Internet Mathematics. 3 (1): 1–20. doi:10.1080/15427951.2006.10129114. S2CID 101281.
^ ^a ^b ^c Georgeot, Bertrand; Giraud, Olivier; Shepelyansky, Dima L. (2010-05-25). "Spectral properties of the Google matrix of the World Wide Web and other directed networks". Physical Review E. 81 (5): 056109. arXiv:1002.3342. Bibcode:2010PhRvE..81e6109G. doi:10.1103/PhysRevE.81.056109. PMID 20866299. S2CID 14490804.
^ ^a ^b ^c ^d ^e ^f Ermann, L.; Chepelianskii, A. D.; Shepelyansky, D. L. (2011). "Fractal Weyl law for Linux Kernel Architecture". European Physical Journal B. 79 (1): 115–120. arXiv:1005.1395. Bibcode:2011EPJB...79..115E. doi:10.1140/epjb/e2010-10774-7. S2CID 445348.

Serra-Capizzano, Stefano (2005). "Jordan Canonical Form of the Google Matrix: a Potential Contribution to the PageRank Computation". SIAM J. Matrix Anal. Appl. 27 (2): 305. doi:10.1137/s0895479804441407. hdl:11383/1494937.
Ulam, Stanislaw (1960). A Collection of Mathematical Problems. Interscience Tracts in Pure and Applied Mathematics. New York: Interscience. p. 73.
Froyland G.; Padberg K. (2009). "Almost-invariant sets and invariant manifolds—Connecting probabilistic and geometric descriptions of coherent structures in flows". Physica D. 238 (16): 1507. Bibcode:2009PhyD..238.1507F. doi:10.1016/j.physd.2009.03.002.
Shepelyansky D.L.; Zhirov O.V. (2010). "Google matrix, dynamical attractors and Ulam networks". Phys. Rev. E. 81 (3): 036213. arXiv:0905.4162. Bibcode:2010PhRvE..81c6213S. doi:10.1103/physreve.81.036213. PMID 20365838. S2CID 15874766.
Ermann L.; Shepelyansky D.L. (2010). "Google matrix and Ulam networks of intermittency maps". Phys. Rev. E. 81 (3): 036221. arXiv:0911.3823. Bibcode:2010PhRvE..81c6221E. doi:10.1103/physreve.81.036221. PMID 20365846. S2CID 388806.
Ermann L.; Shepelyansky D.L. (2010). "Ulam method and fractal Weyl law for Perron-Frobenius operators". Eur. Phys. J. B. 75 (3): 299–304. arXiv:0912.5083. Bibcode:2010EPJB...75..299E. doi:10.1140/epjb/e2010-00144-0. S2CID 54899977.
Frahm K.M.; Shepelyansky D.L. (2010). "Ulam method for the Chirikov standard map". Eur. Phys. J. B. 76 (1): 57–68. arXiv:1004.1349. Bibcode:2010EPJB...76...57F. doi:10.1140/epjb/e2010-00190-6. S2CID 55539783.
Chepelianskii, Alexei D. (2010). "Towards physical laws for software architecture". arXiv:1003.5455 [cs.SE].
Shepelyansky D.L.; Zhirov O.V. (2010). "Towards Google matrix of brain". Phys. Lett. A. 374 (31–32): 3206. arXiv:1002.4583. Bibcode:2010PhLA..374.3206S. doi:10.1016/j.physleta.2010.06.007.
Abel M.; Shepelyansky D.L. (2011). "Google matrix of business process management". Eur. Phys. J. B. 84 (4): 493. arXiv:1009.2631. Bibcode:2011EPJB...84..493A. doi:10.1140/epjb/e2010-10710-y. S2CID 15510734.
Kandiah, Vivek; Shepelyansky, Dima L. (2013). "Google Matrix Analysis of DNA Sequences". PLOS ONE. 8 (5): e61519. arXiv:1301.1626. Bibcode:2013PLoSO...861519K. doi:10.1371/journal.pone.0061519. PMC 3650020. PMID 23671568.
Eom, Young-Ho; Shepelyansky, Dima L. (2013). "Highlighting Entanglement of Cultures via Ranking of Multilingual Wikipedia Articles". PLOS ONE. 8 (10): e74554. arXiv:1306.6259. Bibcode:2013PLoSO...874554E. doi:10.1371/journal.pone.0074554. PMC 3789750. PMID 24098338.
Brin S.; Page L. (1998). "The anatomy of a large-scale hypertextual Web search engine". Computer Networks and ISDN Systems. 30 (1–7): 107. doi:10.1016/s0169-7552(98)00110-x.
Massimo, Franceschet (2010). "PageRank: Standing on the shoulders of giants". arXiv:1002.2858 [cs.IR].
Vigna, Sebastiano (2010). "Spectral Ranking" (PDF).

외부 링크

[Ermann2011-1] Ermann, L.; Chepelianskii, A. D.; Shepelyansky, D. L. (2011). "Towards two-dimensional search engines". Journal of Physics A. 45 (27): 275101. arXiv:1106.6215. Bibcode:2012JPhA...45A5101E. doi:10.1088/1751-8113/45/27/275101. S2CID 14827486.

[Langville2006-2] Langville, Amy N.; Meyer, Carl (2006). Google's PageRank and Beyond. Princeton University Press. ISBN 978-0-691-12202-1.

[Austin2008-3] Austin, David (2008). "How Google Finds Your Needle in the Web's Haystack". AMS Feature Columns.

[4] Law, Edith (2008-10-09). "PageRank Lecture 12" (PDF).

[Frahm2011-5] Frahm, K. M.; Georgeot, B.; Shepelyansky, D. L. (2011-11-01). "Universal emergence of PageRank". Journal of Physics A. 44 (46): 465101. arXiv:1105.1062. Bibcode:2011JPhA...44T5101F. doi:10.1088/1751-8113/44/46/465101. S2CID 16292743.

[6] Donato, Debora; Laura, Luigi; Leonardi, Stefano; Millozzi, Stefano (2004-03-30). "Large scale properties of the Webgraph" (PDF). European Physical Journal B. 38 (2): 239–243. Bibcode:2004EPJB...38..239D. CiteSeerX 10.1.1.104.2136. doi:10.1140/epjb/e2004-00056-6. S2CID 10640375.

[7] Pandurangan, Gopal; Ranghavan, Prabhakar; Upfal, Eli (2005). "Using PageRank to Characterize Web Structure" (PDF). Internet Mathematics. 3 (1): 1–20. doi:10.1080/15427951.2006.10129114. S2CID 101281.

[Georgeot2010-8] Georgeot, Bertrand; Giraud, Olivier; Shepelyansky, Dima L. (2010-05-25). "Spectral properties of the Google matrix of the World Wide Web and other directed networks". Physical Review E. 81 (5): 056109. arXiv:1002.3342. Bibcode:2010PhRvE..81e6109G. doi:10.1103/PhysRevE.81.056109. PMID 20866299. S2CID 14490804.

[Ermann2011-2-9] ^ ^a ^b ^c ^d ^e ^f Ermann, L.; Chepelianskii, A. D.; Shepelyansky, D. L. (2011). "Fractal Weyl law for Linux Kernel Architecture". European Physical Journal B. 79 (1): 115–120. arXiv:1005.1395. Bibcode:2011EPJB...79..115E. doi:10.1140/epjb/e2010-10774-7. S2CID 445348.

[2]

[3]

[4]

[6]

[7]

[8]

[5]

[9]

[1]

Search

구글 매트릭스

네임스페이스

더

목차

인접행렬 A와 마르코프행렬 S

구글 매트릭스 G 구축

Google 매트릭스의 예

G 행렬의 스펙트럼 및 고유 상태

이력 메모

「」를 참조해 주세요.

레퍼런스

외부 링크

Search

구글 매트릭스

인접행렬 A와 마르코프행렬 S

구글 매트릭스 G 구축

Google 매트릭스의 예

G 행렬의 스펙트럼 및 고유 상태

이력 메모

「 」를 참조해 주세요.

레퍼런스

외부 링크

「」를 참조해 주세요.