Dynamic PageRank using Evolving Teleportation - todo314 @ ウィキ

Dynamic PageRank Using Evolving Teleportation

• Ryan A. Rossi and David F. Gleich
• WAW 2012

概要

• 嗜好ベクトルが変化する下でPageRankの微分方程式を考える
• Euler法が実は、べき乗法=Richardson法と似た手法
• 嗜好ベクトルが固定なら、普通のPageRankに収束する
• 色々便利; 予測

動的テレポーテーションなPageRank

• Δx^(k) = x^(k+1)-x^(k) = (1-α)v-(I-αP)x^(k)のアナロジーで、
• x'(t) = (1-α)v(t)-(I-αP)x(t)という微分方程式を考える
• 普通の微分方程式なので、x(t)は解ける
• 特にv(t)=tの時は、x(t)=exp[-(I-αP)t](x(0)-x)+x
  • xは素のPageRank
• だから、t→∞で、x(t)→x
• 計算は（とりあえず）Euler法: x(t+h)=x(t)+h[(1-α)v(t)-(I-αP)x(t)]
  • ほぼべき乗法ぢゃん
• 実用的には、v(t)は離散的--単位時刻毎にv(t)が変化する--で、Euler法では刻み幅hで計算する
  • 同じv(t)について、1/h回べき乗法をやる感じ
• x(t)が0≦t≦tmaxについて分かるがこれどう使うの？
  • 例: その場での値、全体の積分、max-min、時系列のクラスタリング、等する

実験

• Wikipedia: 1時間ごとの訪問数が分かる、全20時間
• Twitter: 月毎のツイート数が分かる、全6ヶ月間
• ランキングを比べるとかなり違う
• ページビューと動的PageRankの値を比べたりする
  • ページ対で相関が出たりする
• ページビュー予測にも使える

まとめ

• シンプルだが楽しい
• 普通に嗜好ベクトルを動的に変更するのかと思ったが、違った

PageRank WAW

2017/01/04