The Effect of the Back Button in a Random Walk: Application for PageRank - todo314 @ ウィキ

The Effect of the Back Button in a Random Walk: Application for PageRank

• Fabien Mathieu, Mohamed Bouklit
• WWW 2004

概要

• バックボタンを入れたPageRankを考える
• 計算も早そう

Back Button Model

Reversible Back

• バックボタンの効果: 1つ前の「状態」に戻る
  • 2回バックすると，今いるページに戻る
  • 記憶領域は前の状態一つだけ
  • どれかの辺をたどる確率とバックボタンの確率は同じ
• t+1ステップ目でwからvに遷移する確率
  • Pr[今wにいてwvを辿る]+Pr[vからwに移動した状態でバック] (wv∈E)
  • Pr[vからwに移動した状態でバック] (wv!∈W)

Irreversible Back

• 連続して2回バックできない
• リンクを辿った場合とバックボタンを使った場合を場合分け
• Pr[wv]はwだけに依存するので割と簡単（らしい）

ランダムジャンプ

• そのまんま

まとめ

• バックボタンの確率は適当だなあ…

PageRank WWW

2014/12/08