Tracking the Random Surfer: Empirically Measured Teleportation Parameters in ...

Tracking the Random Surfer: Empirically Measured Teleportation Parameters in PageRank

  • David F. Gleich, Paul G. Constantine, Abraham D. Flaxman, Asela Gunawardana
  • WWW 2010

概要

  • PageRankのαの値は何なんだ?
  • 平均が0.3~0.7のβ分布に従う

分布の測定

  • 人一人なら簡単
  • (リンククリックによる総閲覧ページ数) / (総閲覧ページ数)
  • 複数人いると,平均とかいうわけにも行かない
    • PageRankはαに対して非線形だから
  • 代わりに,人毎にαを求め,グループ全体にフィットする分布を求める
  • ↓の2方法

ツールバーのログ

  • ウェブ上
    • いい感じにβ分布にフィットする
  • Wikipediaのログ
    • 上の割り算をちょっとだけ変形

アプリケーションのログ

  • hellomovies.com
  • JavaScript走るから統計がとれる(らしい?)

結果

  • ウェブ上は0.6くらい
  • Wikipediaは0.3~0.4くらい
  • hellomovies.comは0.6~0.7くらい
  • Wikipediaだけジャンプしまくる
    • 仮説: 目的の情報が欲しいだけなので,あんまりブラウズする必要がない
  • サイトごとには月とかによらず安定している
  • ドメインごととかで考えるのが大事そう

PageRankの計算

  • αの分布が与えられた上で,期待PageRankベクトルを求めたい
  • 厳密には積分になるけれどダルいので,フィット前のヒストグラムとか色々使って近似
    • Gaussian Quadratureなるもの
  • α=0.85と求めた3分布でPageRankを計算してみた
  • 元の設定だとカテゴリページが多いっぽい
    • β分布のだとちょっと違う

まとめ

  • 色々なαが考えられるので,αの変更に対する再計算が一瞬でできると楽しい

PageRank WWW

2014/12/11

タグ:

WWW PageRank
最終更新:2015年07月31日 15:39