「Dynamic PageRank using Evolving Teleportation」の編集履歴(バックアップ)一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
* Dynamic PageRank Using Evolving Teleportation
- Ryan A. Rossi and David F. Gleich
- WAW 2012
* 概要
- 嗜好ベクトルが変化する下でPageRankの微分方程式を考える
- Euler法が実は、べき乗法=Richardson法と似た手法
- 嗜好ベクトルが固定なら、普通のPageRankに収束する
- 色々便利; 予測
* 動的テレポーテーションなPageRank
- $$ \Delta\mathbf{x}^{(k)} $$
* 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の値を比べたりする
-- ページ対で相関が出たりする
- ページビュー予測にも使える
* まとめ
- シンプルだが楽しい
- 普通に嗜好ベクトルを動的に変更するのかと思ったが、違った
&tags()
2017/01/04