チェイランク
PageRankとCheiRankの平面上のリンクを持つノード

CheiRankは、リンクの方向が反転した有向ネットワーク用に構築されたGoogle行列の最大実固有値を持つ固有ベクトルです。これは、与えられた初期リンク方向を持つGoogle行列の最大固有ベクトルである、入力リンクの数に比例してネットワークノードを平均的にランク付けするPageRankベクトルに似ています 。リンク方向が反転しているため、CheiRankは出力リンクの数に比例してネットワークノードを平均的にランク付けします。各ノードはCheiRankベクトルとPageRankベクトルの両方に属しているため、有向ネットワーク上の情報フローのランク付けは2次元になります。 G ∗ {\displaystyle G^{*}} G {\displaystyle G}

意味

図1. Linuxカーネルネットワークのプロシージャコールの分布（Linuxバージョン2.6.32、行列サイズ ）のPageRank確率とCheiRank確率の平面上における分布。色はノードの密度を示し、白は最大値、青は最小値、黒のスペースにはノードがない（Chepelianskiiより） x = log 10 ⁡ P i {\displaystyle x=\log _{10}P_{i}} y = log 10 ⁡ P i ∗ {\displaystyle y=\log _{10}{P}_{i}^{*}} N = 285509 {\displaystyle N=285509} α = 0.85 {\displaystyle \alpha =0.85}

与えられた有向ネットワークに対して、Google 行列は、記事「Google 行列」で説明されている方法で構築されます。Pag ​​eRankベクトルは、最大実固有値 を持つ固有ベクトルです。これは[1]で導入され、記事「PageRank」で説明されています。同様に、CheiRank は、同じ方法で構築された行列の最大実固有値 を持つ固有ベクトルですが、最初に与えられた隣接行列のリンクの方向を反転しています。行列と は両方ともPerron–Frobenius 演算子のクラスに属し、Perron–Frobenius の定理によれば、 CheiRankおよび PageRank固有ベクトルは、確率として解釈できる非負の要素を持ちます。[2] [3]したがって、ネットワークのすべてのノードは、それぞれCheiRank および PageRank のランクを使用して、確率の降順で並べることができます。平均して、PageRank 確率は、 を持つ入力リンクの数に比例します。[4] [5] [6]ワールド ワイド ウェブ (WWW) ネットワークでは指数で、は入力リンク分布の指数です。[4] [5]同様に CheiRank 確率は平均して出力リンクの数に比例し、 はWWW の出力リンク分布の指数です。[4] [5] CheiRank は、Linux カーネル ソフトウェアのプロシージャ コール ネットワーク用に導入されました。 [7]用語自体は Zhirov で使用されました。[ 8] PageRank が非常によく知られた人気のノードを強調表示するのに対し、CheiRank は非常に通信的なノードを強調表示します。トップ PageRank ノードと CheiRank ノードはHITS アルゴリズム[9]に現れるオーソリティとハブにある程度類似していますが、HITS はクエリに依存し、ランク確率はネットワークのすべてのノードを分類します。各ノードは CheiRank と PageRank の両方に属しているため、ネットワーク ノードの 2 次元ランキングが得られます。リンクの方向が反転したネットワークにおけるPageRankの初期の研究はあったが[10] [11]、2次元ランキングの特性については詳細に分析されていなかった。 λ = 1 {\displaystyle \lambda =1} G ∗ {\displaystyle G^{*}} G {\displaystyle G} G {\displaystyle G} G ∗ {\displaystyle G^{*}} P i ∗ {\displaystyle P_{i}^{*}} P i {\displaystyle P_{i}} N {\displaystyle N} i {\displaystyle i} K i ∗ , K i {\displaystyle K_{i}^{*},K_{i}} P i ∗ , P i {\displaystyle P_{i}^{*},P_{i}} P i {\displaystyle P_{i}} P i ∝ 1 / K i β {\displaystyle P_{i}\propto 1/{K_{i}}^{\beta }} β = 1 / ( ν − 1 ) ≈ 0.9 {\displaystyle \beta =1/(\nu -1)\approx 0.9} ν ≈ 2.1 {\displaystyle \nu \approx 2.1} P i ∗ ∝ 1 / K i ∗ β ∗ {\displaystyle P_{i}^{*}\propto 1/{K_{i}^{*}}^{\beta ^{*}}} β ∗ = 1 / ( ν ∗ − 1 ) ≈ 0.6 {\displaystyle \beta ^{*}=1/(\nu ^{*}-1)\approx 0.6} ν ∗ ≈ 2.7 {\displaystyle \nu ^{*}\approx 2.7} P i {\displaystyle P_{i}} P i ∗ {\displaystyle P_{i}^{*}}

図2. PageRank （赤線）とCheiRank （青線）の確率と、対応するランク指標およびへ の依存性。破線は それぞれ傾きがべき乗則の依存性を示しており、（Zhirovより） P {\displaystyle P} P ∗ {\displaystyle P^{*}} K {\displaystyle K} K ∗ {\displaystyle K^{*}} β = 0.92 ; 0.57 {\displaystyle \beta =0.92;0.57} β = 1 / ( ν − 1 ) {\displaystyle \beta =1/(\nu -1)}

例

Linuxカーネルソフトウェアのプロシージャ呼び出しネットワークにおけるPageRankとCheiRankの平面上のノード分布の例を図1に示します。[7]

図3. Wikipedia英語版記事（2009年）のPageRankおよびCheiRank指数平面における密度分布。青は最小値、白は最大値（黒はゼロ）で色分け表示。緑/赤の点はPageRank/CheiRank上位100人、黄色のプラスはハートの著書上位100人、記事数（ジロフより） 0 < ln ⁡ K , ln ⁡ K ∗ < ln ⁡ N {\displaystyle 0<\ln K,\ln K^{*}<\ln N} N = 3282257 {\displaystyle N=3282257}

Wikipedia英語版記事のハイパーリンクネットワークの への依存性は、Zhirovの図2に示されています。Pag​​eRankとCheiRankの平面におけるこれらの記事の分布は、Zhirovの図3に示されています。Pag​​eRankとCheiRankの違いは、最高ランクのWikipedia記事の名前（2009年）から明確に見られます。Pag​​eRankのトップには、1.米国、2.英国、3.フランスがあり、CheiRankには、1.ポータル:目次/知識の概要/地理と場所、2.年別の国家指導者のリスト、3.ポータル:目次/索引/地理と場所があります。明らかに、PageRankは、多数の入力リンクを持つ広く知られている主題に関する最初の記事を選択しますが、CheiRankは、多くの出力リンクを持つコミュニケーション性の高い記事を最初に選択します。記事は2Dで分布しているので、2Dセットの線への投影に対応するさまざまな方法でランク付けできます。水平線と垂直線はPageRankとCheiRankに対応し、2DRankはZhirovで説明されているように、CheiRankとPageRankの特性を組み合わせたものです。[8]ウィキペディアのトップ記事として1.インド、2.シンガポール、3.パキスタンが表示されます。 P , P ∗ {\displaystyle P,P^{*}} K , K ∗ {\displaystyle K,K^{*}}

2Dランキングは、Wikipedia記事の特性を、新しく豊かで実りある方法で明らかにします。Pag​​eRankによると、Wikipedia記事に登場する上位100人の人物は、5つの主要カテゴリの活動において、それぞれ58（政治）、10（宗教）、17（芸術）、15（科学）、0（スポーツ）となっており、政治家の重要性は過大評価されています。CheiRankではそれぞれ15、1、52、16、16ですが、2DRankでは24、5、62、7、2となっています。このような2Dランキングは、WWWを含む様々な複雑な有向ネットワークに有用に応用できます。

CheiRankとPageRankは世界貿易ネットワーク、つまり国際貿易において自然に現れ、それぞれ特定の国の輸出と輸入の流れと結びついています。[12]

PageRankとCheiRankに基づく2次元検索エンジンの開発の可能性が検討されている。[13]有向ネットワークは、PageRankベクトルとCheiRankベクトル間の相関係数によって特徴付けられる。特定のネットワークではこの相関係数はゼロに近い（例：Linuxカーネルネットワーク）が、他のネットワークでは大きな相関係数値を持つ（例：Wikipediaや大学ネットワーク）。[7] [13]

シンプルなネットワークの例

図4. 有向ネットワークの例
図5. 関連マトリックス S {\displaystyle S}
図6. 関連マトリックス S ∗ {\displaystyle S^{*}}

関連する PageRank ベクトルと CheiRank ベクトルの決定に使用されるGoogle 行列およびの構築の簡単な例を以下に示します。7 つのノードを持つ有向ネットワークの例を図 4 に示します。記事Google 行列で説明されている規則を使用して構築された行列を図 5 に示します。関連する Google 行列 は であり、PageRank ベクトルは 単位固有値 ( ) を持つ の右固有ベクトルです。同様に、CheiRank 固有ベクトルを決定するために、図 4 のリンクのすべての方向を反転してから、図 6 に示すように、反転したリンク方向を持つネットワークに適用されたのと同じ規則に従って行列を構築します。関連する Google 行列 は であり、 CheiRank ベクトルは 単位固有値 ( ) を持つの右固有ベクトルです。ここでは、通常の値で取得された減衰係数を示します。 G {\displaystyle G} G ∗ {\displaystyle G^{*}} S {\displaystyle S} G = α S + ( 1 − α ) e e T / N {\displaystyle G=\alpha S+(1-\alpha )ee^{T}/N} G {\displaystyle G} G P = P {\displaystyle GP=P} S ∗ {\displaystyle S^{*}} G ∗ = α S ∗ + ( 1 − α ) e e T / N {\displaystyle G^{*}=\alpha S^{*}+(1-\alpha )ee^{T}/N} G ∗ {\displaystyle G^{*}} G ∗ P ∗ = P ∗ {\displaystyle G^{*}P^{*}=P^{*}} α ≈ 0.85 {\displaystyle \alpha \approx 0.85}

参照

参考文献

  1. ^ Brin S.; Page L. (1998)、「大規模ハイパーテキストWeb検索エンジンの解剖学」、コンピュータネットワークとISDNシステム、30 ( 1–7 ): 107、doi :10.1016/S0169-7552(98)00110-X、S2CID  7587743
  2. ^ ラングビル、エイミー・N.、カール・マイヤー（2006年）『GoogleのPageRankとその先』プリンストン大学出版局、ISBN 0-691-12202-4。
  3. ^ オースティン、デイビッド (2008). 「Googleはいかにしてウェブの干し草の山からあなたの針を見つけるのか」AMS特集コラム.
  4. ^ abc Donato D.; Laura L.; Leonardi S.; Millozzi S. (2004)、「Webgraphの大規模特性」、European Physical Journal B、38 (2): 239、Bibcode :2004EPJB...38..239D、doi :10.1140/epjb/e2004-00056-6、S2CID  10640375
  5. ^ abc Pandurangan G.; Ranghavan P.; Upfal E. (2005)、「PageRankを用いたWeb構造の特徴づけ」、インターネット数学、3 :1、doi : 10.1080/15427951.2006.10129114
  6. ^ Litvak, N. ; Scheinhardt, WRW; Volkovich, Y. (2008) 「In-DegreeとPageRankの確率的関係」、Lecture Notes in Computer Science、vol. 4936、p. 72
  7. ^ abc Chepelianskii, Alexei D. (2010). 「ソフトウェアアーキテクチャの物理法則に向けて」arXiv : 1003.5455 [cs.SE].
  8. ^ アブ ・ジロフAO;ジロフ OV; Shepelyansky DL (2010)、「Wikipedia 記事の 2 次元ランキング」、European Physical Journal B、77 (4): 523、arXiv : 1006.4270、Bibcode :2010EPJB...77..523Z、doi :10.1140/epjb/e2010-10500-7、S2CID  18014470
  9. ^ Kleinberg, Jon (1999). 「ハイパーリンク環境における権威ある情報源」. Journal of the ACM . 46 (5): 604– 632. doi : 10.1145/324133.324140 . S2CID  221584113.
  10. ^ Fogaras, D. (2003) 「ウェブ閲覧はどこから始めるべきか？」Lecture Notes in Computer Science、vol. 2877、p. 65
  11. ^ Hrisitidis V.; Hwang H.; Papakonstantinou Y. (2008)、「データベースにおける権威ベースのキーワード検索」、ACM Trans. Database Syst.、33 :1、doi :10.1145/1331904.1331905、S2CID  11978441
  12. ^ Ermann L.; Shepelyansky DL (2011). 「世界貿易ネットワークのGoogleマトリックス」. Acta Physica Polonica A. 120 ( 6A): A. arXiv : 1103.5027 . Bibcode :2011AcPPA.120..158E. doi :10.12693/APhysPolA.120.A-158. S2CID  18315654.
  13. ^ ab Ermann L.; Chepelianskii AD; Shepelyansky DL (2011). 「2次元検索エンジンに向けて」. 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.
  • Wikipedia記事の2次元ランキング
  • 世界貿易: CheiRank 対 PageRank
  • 2次元検索エンジンに向けて
  • Wikipediaのトップ人物
Retrieved from "https://en.wikipedia.org/w/index.php?title=CheiRank&oldid=1312256965"