PageRankのべき乗法、マルコフ連鎖の凝集
(「Google PageRankの数理」から)

@flashingwind

2010.5.3

2006年度の専攻科ゼミで参考にしたレビュー[1]の著者らによるより詳細な解説が、昨年(日本語版が)出版された[2]である。

PageRankべき乗法の収束回数は高々50〜100

「漸近的な収束の速さ(asymptonic rate of convergence)」:

計算量はO(n)

疎であるので…

凝集

近似凝集、近似更新

リンク変更時の再計算の計算量削減のため。

正確な凝集(exact aggregation)

意図

本来は分割統治のためのものである。 が、以下などは、リンク構造に関係すると考えられ、クラスタリングのためにに使えないか。 指標: $\pi$$\pi $$\omega^T$$\pi_2 ^T$がどの程度近似できているか。

その他

参考文献

1
Amy N.Langville, Carl D.Meyer ``A Survey of Eigenvector Methods for Information Retrieval'', SIAM Review Vol.47 No.1, pp.135-161 (2005).

2
Amy N.Langville, Carl D.Meyer, 岩野 和生 (翻訳), 黒川 利明 (翻訳), 黒川 洋 (翻訳)『Google PageRankの数理―—最強検索エンジンのランキング手法を求めて』共立出版 (2009/10/10).

この文書について...

PageRankのべき乗法、マルコフ連鎖の凝集
(「Google PageRankの数理」から)

この文書はLaTeX2HTML 翻訳プログラム Version 2008 (1.71)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds,
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

日本語化したもの( 2008 (1.71) JA patch-2.1beta1.12 版)

Copyright © 1998, 1999, Kenshi Muto, Debian Project.
Copyright © 2001-2010, Shige TAKENO, Niigata Inst.Tech.

を用いて生成されました。

コマンド行は以下の通りでした。:
latex2html seminar-20100503html.tex -split 0 -html_version 4.0 math -antialias.

翻訳は munenori によって 2010-06-04 に実行されました。

munenori 2010-06-04