Link Evolution: Analysis and Algorithms - todo314 @ ウィキ

Link Evolution: Analysis and Algorithms

• Steve Chien, Cynthia Dwork, Ravi Kumar, Daniel R. Simon, D. Sivakumar
• Internet Mathematics 2010

概要

• PageRankの動的更新手法
• アイデアは追加・削除された辺の近傍のみを真面目に再計算する

提案手法 aggregation/disaggregation method

• 観察: 辺ijが追加されたら，iとjの近傍についてのみPageRankスコアが変化する

1. S(t)←時刻tで追加・削除された辺の近傍集合
2. G'←V\S(t)を1つの頂点に縮約したグラフ
   • 辺の遷移確率は注意深く設定する
3. G'のPageRankを計算
4. 各i∈S(t)についてPageRankスコアをG'のそれに更新する

• ※S(t)の選び方はいろいろある

欠点

• 理論的保証がない
• 誤差が累積するので大量の動的更新に対応するためには定期的に再計算し直す必要がある

Internet Mathematics PageRank 動的グラフ

2014/12/06