Haveliwala, T.H., Efficient Computation of PageRank?, Stanford Univ.Technical Report, 1999. GoogleのPageRankアルゴリズムは、親ページの重要度(importance)に基づいて、子のページの重要度を決めるアルゴリズム.ハブとその重みによって子の重みも決定される. 言葉の定義: rank:全ページの重要度を並べたベクトル 重要度は,出てるリンクで等分される,マルコフ配分における発生交通量のようなものがどう収束するか. 計算法: Rank(i+i) = M×Rank(i) をMが固有値Rank*になるまで反復計算 ・行き止まりリンクがある場合の対応. リンクが張られているページだけではなく全ページからランダムに選択する項を加える.通常15%で全体からランダムに選択するとする. 入出力コスト: メモリの問題.リンクと接続ノードを全て格納するためには32bitかかる. ブロック分割法で対応.分割がない場合と同じ計算時間で計算可能. 収束分析: 上位ページに関しては,25回の計算で100回とほぼ同じ値が得られる.個別キーワードの上位ページの場合,10回の計算で100回とほぼ同じ値が得られる. 研究に関連して: ・ページランクと配分の関係は?交通量配分における通りやすさは媒介中心性. 通信のネットワークや交通のネットワークの理論,手法論が応用されてきている. ・大規模ネットワークの場合,ブロック分割・メモリを工夫するところに注意. =================================================== まとめ ページランクとは,親ページの重要度(importance)に基づいて、子のページの重要度を決めるアルゴリズム.ハブとその重みによって子の重みも決定される.ここで,rankとは全ページの重要度を並べたベクトルのことを表し,Rank(i+i) = M×Rank(i)をが固有値Rank*になるまで反復計算することで求める.Mとは,リンク構造を表す行列を表す.重要なページからリンクされているページは重要である,といようにリンクされている数だけではなくリンクそのものの重みを考慮している点が特徴といえる.また,外向きリンクが存在しないページについても確率的に訪れることを表現するため,リンク先の中からランダムに選択する項と,webページ全体からランダムに選択する項をそれぞれ定式化することで,リンクされていないページにもある確率で到達する現象を表現した.計算コストが膨大となることに対する方策として,ブロック分割法を用いて効率的なメモリ管理を考案し,18,922,290程度のノードを持つwebページに対しても通常コンピュータで計算可能とした.