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スコアが変化する
-
S(t)←時刻tで追加・削除された辺の近傍集合
-
G'←V\S(t)を1つの頂点に縮約したグラフ
-
G'のPageRankを計算
-
各i∈S(t)についてPageRankスコアをG'のそれに更新する
欠点
-
理論的保証がない
-
誤差が累積するので大量の動的更新に対応するためには定期的に再計算し直す必要がある
Internet Mathematics PageRank 動的グラフ
2014/12/06
最終更新:2014年12月06日 22:32