Google マトリックス

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

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

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

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

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

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

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

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

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

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

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

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

Google行列は、動的マップのUlam法[8]によって生成されたUlamネットワークに対しても構築できます。このような行列のスペクトル特性は[9,10,11,12,13,15]で説明されています。^{[5] [9]}多くの場合、スペクトルはフラクタルワイルの法則によって記述されます[10,12]。

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

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

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

• チェイランク
• アーノルディ反復法
• マルコフ連鎖
• 転送オペレータ
• ペロン・フロベニウスの定理
• ウェブ検索エンジン

• Scholarpedia の Google マトリックス
• Google PR 停止
• IHES ワークショップ「Google マトリックス: 基礎、応用、そしてその先」でのビデオ講義、2018 年 10 月