21章はリンク解析について。PageRankやHITSについて説明している。
以下の点から、リンク解析は重要である。
- あるページのみを見るよりも、そのページのリンク情報も一緒に見るほうが効果がある。
- アンカーテキストは、そのページの内容を特徴付けてくれるものであることが多い。
※ただし、常に上記のことが成立するとは限らない。
(例)Google bombs(グーグル爆弾)
ページとは関連性のないキーワードのアンカーテキストを用いた大量のリンクを与えることでGoogle検索エンジンで上位表示させる手法。
有名な例としては、“miserable failure”(みじめな失敗)というキーワードで検索すると、ブッシュ大統領の経歴ページが上位に出ていたことがあった。
引用文分析
引用文分析とは、科学文献の引用文を分析する手法。
共引用類似度
引用文がオーバーラップしている2つの文献の類似度を、共引用類似度(cocitation similarity)といい、特徴の類似性を示してくれる。
PageRank
Web上で、Webサーファーがランダムウォークすることを考える。
あるページからスタートし、リンクをたどりながら他のページへ移動する。
PageRank(ページランク)とは、そのような場合に、サーファーが各ページにいる確率の極限値でランキングする手法である。
ドキュメント i からドキュメント j にリンクされていることを、以下のグラフで表す。
各ページに有用度(1)を割り当て、その有用度をリンクに沿って他のページへと普及させる。
また、ページから複数のリンクが出ている場合は、そのページへの有用度をそれらに均等に分割する。すなわち、以下の式が成立する。
例として、以下のグラフを考える。
まず、リンクされている行に1を入れる。
次に、各列の合計を1にする。
このようにして行列を生成する。
しかし、このままでは以下のような問題が生じる。
Dead end
以下のようにリンクを全くしていないページが存在する場合、ランダムウォークはそこで止まってしまう。
これをDead endといい、これが生じると、PageRank値がうまく定まらない。
これを回避するために、ランダムウォークだけでなく、他ページへランダムにジャンプする確率も考えることにする。
そのページがDead endなら、等しい確率でいずれかのページにジャンプ、そうでなければ、基本的にはランダムウォークを行うが、ある小さな確率(例えば10%など)で、いずれかのページにランダムジャンプすると考える。
これによりDead endは回避される。
しかし、実はこれ以外にもPageRank値がうまく定まらない場合があり、さらに以下のように一般化して考える必要がある。
エルゴード的マルコフ連鎖
マルコフ連鎖が以下の性質を持つ時、エルゴード的であるという。
- 可約性
全てのページへのパスがある
- 非振動性
ランダムウォークに周期性がない
このようにすると、例えば以下のグラフは周期性があるために非エルゴード的であり、不適切となる。
Webグラフ上に、このエルゴード的マルコフ連鎖を適用したのがPageRankである。
以下にPageRankの問題点をあげる。
- 実際のWebサーファーはランダムウォークを行わない。
例えば、バックボタンやブックマークを使ったり、検索を行ったりするため、実際にはランダムウォークにならない。
しかし、ページのランキングという目的で考えれば、マルコフモデルで十分であるいえる。
- 単純にPageRankを用いるだけでは、結果はよくならない。
例えば、"video service"というクエリを考える。
この場合、PageRank値が高く、クエリのタームを含んでいるページが上位にランキングされるので、例えばYahooのようなページ("video"も"service"も含んでいる)が上位にランキングされる。
しかし、これは情報ニーズを完全に無視しており、望んでいる結果ではない。
PageRankだけではこのような問題点が生じるため、実際は他の手法と組み合わせて用いられている。
まとめると、PageRankは完全ではないが、Webランキングにおいてかなり重要な要素の1つであるといえる。
HITS
HITS(Hyperlink-Induced Topic Search)は、PageRankとは異なるランキング手法であり、以下の2つの概念を考える。
- ハブ…よいリンクを持つページ
- オーソリティ…よい情報を持つページ
以下が定義である。
- 多くのよいオーソリティをリンクしているページは、よいハブである。
- 多くのよいページからリンクされているページは、よいオーソリティである。
このように、相互再帰的に定義されている。
以下にハブとオーソリティの計算手法をあげる。
- まず、普通にWeb検索を行う。これで得られた検索結果をルートセットと呼ぶ。
- 次に、ルートセット内のページのリンク先、リンク元情報を全て見付ける。
- ベースセット内で、以下を用いてハブとオーソリティを計算する。
以下に、HITSの問題点をあげる。
トピックドリフト(topic drift)
ベースセット内に情報ニーズとは全く関係のないページが密なリンク構造をもつ場合、情報ニーズに合ったハブ・オーソリティを抽出することができない。