Googleマトリックス
Stochastic matrix representing links between entities
図1. PageRankインデックスに基づいて記述されたWikipedia記事ネットワークのGoogleマトリックス。上位200 x 200のマトリックス要素の断片を示し、合計サイズN = 3282257（[1]より）

Google行列は、GoogleのPageRankアルゴリズムで使用される特殊な確率行列です。この行列は、ページ間のリンクを表すエッジを持つグラフを表します。各ページのPageRankは、Google行列からべき乗法を用いて反復的に生成できます。ただし、べき乗法が収束するためには、行列は確率的、既約、かつ非周期的である必要があります。

隣接行列あおよびマルコフ行列S

Google マトリックスGを生成するには、まずページまたはノード間の関係を表す 隣接マトリックス Aを生成する必要があります。

Nページあると仮定すると、次のようにして Aを埋めることができます。

  1. ノードにノードへのリンクがある場合は行列要素に 1 が入り、ない場合は 0 が入ります。これはリンクの隣接行列です。 A i , j {\displaystyle A_{i,j}} j {\displaystyle j} i {\displaystyle i}
  2. 与えられたネットワークのマルコフ連鎖における遷移に対応する関連行列Sは、 Aの列「j」の要素を で割ることによって構築されます。ここではノードjから他のすべてのノードへの出力リンクの総数です 。行列要素がゼロの列（ダングリングノードに対応）は、定数値1/Nに置き換えられます。この手順により、すべてのシンク（ダングリング状態）から他のすべてのノードへのリンクが追加されます。 k j = Σ i = 1 N A i , j {\displaystyle k_{j}=\Sigma _{i=1}^{N}A_{i,j}} k j {\displaystyle k_{j}} a {\displaystyle a}
  3. この構成により、行列Sの任意の列のすべての要素の和は1に等しくなります。このように、行列Sは数学的に明確に定義され、マルコフ連鎖のクラスとペロン・フロベニウス作用素のクラスに属します。そのため、SはPageRankアルゴリズムに適しています。

Googleマトリックスの構築G

図2. ケンブリッジ大学ネットワークのGoogleマトリックス（2006年）。粗粒度のマトリックス要素はPageRankインデックスのベースで記述され、総サイズN = 212710が示されている（[1]より）

最終的な Google 行列 G は、Sを介して次のように表現できます。

G i j = α S i j + ( 1 − α ) 1 N ( 1 ) {\displaystyle G_{ij}=\alpha S_{ij}+(1-\alpha ){\frac {1}{N}}\;\;\;\;\;\;\;\;\;\;\;(1)}

この構成により、各行列列内のすべての非負要素の和は1に等しくなります。この数値係数は減衰係数と呼ばれます。 α {\displaystyle \alpha }

通常、Sは疎行列であり、現代の有向ネットワークでは、行または列に約10個の非ゼロ要素しか持たないため、ベクトルと行列 Gを乗算するには約10N回の乗算のみが必要です。[2] [3]

Googleマトリックスの例

単純なネットワーク内で式(1)による行列構築の例は、論文CheiRankに記載されています。 S {\displaystyle S}

実際の行列では、Googleは約0.85の減衰係数を使用しています。[2] [3] [4]この項は、サーファーが任意のページにランダムにジャンプする確率を表します。この行列は、マルコフ連鎖のペロン・フロベニウス作用素のクラスに属します。[2] Google行列構造の例としては、2009年のWikipedia記事ハイパーリンクネットワーク（小規模）の図1と、2006年のケンブリッジ大学ネットワーク（大規模）の図2が挙げられます。 α {\displaystyle \alpha } ( 1 − α ) {\displaystyle (1-\alpha )} G {\displaystyle G}

スペクトルと固有状態Gマトリックス

図3. 図2のケンブリッジ大学のGoogle行列の固有値のスペクトル。 青い点は孤立した部分空間の固有値、赤い点はコア成分の固有値を示す（[5]より）。 α = 1 {\displaystyle \alpha =1}

というのは、対応する右固有ベクトル を持つ最大固有値は 1 つしか存在しないからであり、この右固有ベクトルは非負の要素を持ち、定常確率分布とみなせるからである。[2]これらの確率を減少値の順に並べると、PageRank ベクトル が得られ、このPageRank はGoogle 検索でウェブページのランク付けに使われる。通常、ワールド ワイド ウェブでは となる。特定の PageRank 値を持つノードの数は、指数 とともに のように増減する。[6] [7]における左固有ベクトルは、定数行列要素を持つ。 のすべての固有値は のように移動するが、最大固有値だけは変化しない。[2] PageRank ベクトルは とともに変化するが、 を持つその他の固有ベクトルは、における定数左ベクトルに直交するため変化しない。とその他の固有値の間のギャップにより、行列を約 50 回乗算すると、ランダム初期ベクトルが PageRank に急速に収束する。 0 < α < 1 {\displaystyle 0<\alpha <1} λ = 1 {\displaystyle \lambda =1} P i {\displaystyle P_{i}} P i {\displaystyle P_{i}} K i {\displaystyle K_{i}} P ∝ 1 / K β {\displaystyle P\propto 1/K^{\beta }} β ≈ 0.9 {\displaystyle \beta \approx 0.9} N P ∝ 1 / P ν {\displaystyle N_{P}\propto 1/P^{\nu }} ν = 1 + 1 / β ≈ 2.1 {\displaystyle \nu =1+1/\beta \approx 2.1} λ = 1 {\displaystyle \lambda =1} 0 < α {\displaystyle 0<\alpha } λ i → α λ i {\displaystyle \lambda _{i}\rightarrow \alpha \lambda _{i}} λ = 1 {\displaystyle \lambda =1} α {\displaystyle \alpha } λ i < 1 {\displaystyle \lambda _{i}<1} λ = 1 {\displaystyle \lambda =1} λ = 1 {\displaystyle \lambda =1} 1 − α ≈ 0.15 {\displaystyle 1-\alpha \approx 0.15} G {\displaystyle G}

図4. 辞書ネットワークにおけるGoogle行列の複素平面における固有値の分布: Roget (A, N=1022)、ODLIS (B, N=2909)、FOLDOC (C, N=13356); 英国の大学WWWネットワーク: ウェールズ大学(カーディフ) (D, N=2778)、バーミンガム・シティ大学 (E, N=10631)、キール大学(スタッフォードシャー) (F, N=11437)、ノッティンガム・トレント大学 (G, N=12660)、リバプール・ジョン・ムーアズ大学 (H, N=13578)(大学のデータは2002年のものです) ( [8]より) λ i {\displaystyle \lambda _{i}} α = 1 {\displaystyle \alpha =1}

行列は 一般に多くの退化した固有値を持つ （例えば[6] [8]を参照）。様々な有向ネットワークのGoogle行列の固有値スペクトルの例は、[5]の図3と[8]の図4に示されている。 α = 1 {\displaystyle \alpha =1} G {\displaystyle G} λ = 1 {\displaystyle \lambda =1}

Google行列は、力学写像に対するUlam法[8]によって生成されたUlamネットワークに対しても構築できる。このような行列のスペクトル特性については[9,10,11,12,13,15]で議論されている[5] [9] 。多くの場合、スペクトルはフラクタルWeyl法則によって記述される[10,12]。

図5. Linuxカーネルバージョン2.6.32のGoogle行列の複素平面における固有値の分布（行列サイズは、単位円は実線で示されている（[9]より） λ {\displaystyle \lambda } G {\displaystyle G} N = 285509 {\displaystyle N=285509} α = 0.85 {\displaystyle \alpha =0.85}
図6 Linuxカーネルバージョン2.6.32におけるGoogle行列の固有状態の粗視化確率分布。水平線は最初の64個の固有ベクトルを縦に並べたもの（[9]より） | λ i | {\displaystyle |\lambda _{i}|}

Google行列は、他の有向ネットワーク、例えば[15]で紹介されたLinuxカーネルソフトウェアの手続き呼び出しネットワークに対しても構築できる。この場合、のスペクトルはフラクタル次元を持つフラクタルワイル則によって記述される（[9]の図5を参照）。数値解析により、行列の固有状態は局所化されていることが示される（ [9]の図6を参照）。アーノルディ反復法を用いると、比較的大きなサイズの行列に対しても多くの固有値と固有ベクトルを計算することができる[13]。[5] [9] λ {\displaystyle \lambda } d ≈ 1.3 {\displaystyle d\approx 1.3} G {\displaystyle G}

マトリックスの他の例としては、Googleの脳マトリックス[17]やビジネスプロセスマネジメント[18]などが挙げられる。[1]も参照のこと。Googleマトリックス分析のDNA配列への応用については[20]で説明されている。このようなGoogleマトリックスアプローチは、人物に関する多言語Wikipedia記事のランキング付けを通じて、文化の絡み合いを分析することも可能にする[21]。 G {\displaystyle G}

歴史的ノート

減衰係数を持つGoogleマトリックスは、 1998年にセルゲイ・ブリン氏とラリー・ペイジ氏によって説明されました[22]。また、PageRankの歴史に関する記事も参照してください[23],[24]。

参照

参考文献

  1. ^ abc Ermann, L.; Chepelianskii, AD; Shepelyansky, DL (2011). 「2次元検索エンジンに向けて」Journal of Physics A . 45 (27) 275101. arXiv : 1106.6215 . Bibcode :2012JPhA...45A5101E. doi :10.1088/1751-8113/45/27/275101. S2CID  14827486.
  2. ^ abcde Langville, Amy N. ; Meyer, Carl (2006). GoogleのPageRankとその先.プリンストン大学出版局. ISBN 978-0-691-12202-1。
  3. ^ ab オースティン、デイビッド (2008). 「Googleはウェブの干し草の山からあなたの針を見つける方法」AMS特集コラム.
  4. ^ Law, Edith (2008年10月9日). 「PageRank Lecture 12」(PDF) .
  5. ^ abcd Frahm, KM; Georgeot, B.; Shepelyansky, DL (2011-11-01). 「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. ^ ドナート、デボラ;ローラ、ルイージ。レオナルディ、ステファノ。ミロッツィ、ステファノ (2004-03-30)。 「ウェブグラフの大規模プロパティ」(PDF)。ヨーロッパ物理ジャーナル B。38 (2): 239–243。書誌コード:2004EPJB...38..239D。CiteSeerX 10.1.1.104.2136。土井：10.1140/epjb/e2004-00056-6。S2CID  10640375。 
  7. ^ Pandurangan, Gopal; Ranghavan, Prabhakar; Upfal, Eli (2005). 「PageRankを用いたWeb構造の特徴づけ」(PDF) . Internet Mathematics . 3 (1): 1– 20. doi : 10.1080/15427951.2006.10129114 . S2CID  101281.
  8. ^ abc Georgeot, Bertrand; Giraud, Olivier; Shepelyansky, Dima L. (2010-05-25). 「World Wide Webおよびその他の有向ネットワークにおけるGoogle行列のスペクトル特性」. Physical Review E. 81 ( 5) 056109. arXiv : 1002.3342 . Bibcode :2010PhRvE..81e6109G. doi :10.1103/PhysRevE.81.056109. PMID  20866299. S2CID  14490804.
  9. ^ abcdef Ermann, L.; Chepelianskii, AD; Shepelyansky, DL (2011). 「Linuxカーネルアーキテクチャにおけるフラクタル・ワイル則」. European Physical Journal B . 79 (1): 115– 120. arXiv : 1005.1395 . Bibcode :2011EPJB...79..115E. doi :10.1140/epjb/e2010-10774-7. S2CID  445348.
  • セラ＝カピッツァーノ、ステファノ (2005). 「Googleマトリックスのジョーダン標準形：PageRank計算への潜在的貢献」SIAM J. Matrix Anal. Appl . 27 (2): 305. doi :10.1137/s0895479804441407. hdl : 11383/1494937 .
  • ウラム、スタニスワフ (1960). 『数学問題集』 . インターサイエンス社, 純粋数学と応用数学の小冊子. ニューヨーク: インターサイエンス. p. 73.
  • Froyland G.; Padberg K. (2009). 「ほぼ不変集合と不変多様体 ― 流れにおけるコヒーレント構造の確率的記述と幾何学的記述の結合」Physica D . 238 (16): 1507. Bibcode :2009PhyD..238.1507F. doi :10.1016/j.physd.2009.03.002.
  • Shepelyansky DL; Zhirov OV (2010). 「Google行列、動的アトラクター、そしてUlamネットワーク」. 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 DL (2010). 「Google行列とUlamネットワークによる間欠性マップ」. 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 DL (2010). 「ペロン・フロベニウス作用素に対するウラム法とフラクタル・ワイル則」. 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 KM; Shepelyansky DL (2010). 「チリコフ標準写像のためのウラム法」. 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). 「ソフトウェアアーキテクチャのための物理法則に向けて」arXiv : 1003.5455 [cs.SE].
  • シェペリャンスキー DL;ジロフ OV (2010)。 「脳のGoogleマトリックスに向けて」。物理学。レット。 Ａ．​ 374 ( 31–32 ): 3206.arXiv : 1002.4583。ビブコード:2010PhLA..374.3206S。土井：10.1016/j.physleta.2010.06.007。
  • Abel M.; Shepelyansky DL (2011). 「Googleマトリックスによるビジネスプロセスマネジメント」. 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). 「DNA配列のGoogleマトリックス解析」. 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). 「多言語Wikipedia記事のランキングによる文化の絡み合いの強調」. 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). 「大規模ハイパーテキストWeb検索エンジンの解剖学」.コンピュータネットワークとISDNシステム. 30 ( 1–7 ): 107. doi :10.1016/s0169-7552(98)00110-x. S2CID  7587743.
  • マッシモ・フランチェシェ（2010）「PageRank：巨人の肩の上に立つ」arXiv：1002.2858 [cs.IR]。
  • Vigna, Sebastiano (2010). 「スペクトルランキング」(PDF) .
  • Scholarpedia の Google マトリックス
  • Google PR 停止
  • IHESワークショップ「Googleマトリックス：基礎、応用、そしてその先」におけるビデオ講義、2018年10月
Retrieved from "https://en.wikipedia.org/w/index.php?title=Google_matrix&oldid=1313942772"