Link Analysis

Anand Rajaraman and Jeff Ullman, Mining of Massive Datasets, Chapter 5.

基礎っぽいけど,この辺,グラフアルゴリズムの界隈とはちょっと違う界隈だよな〜

  • PageRank
    • 昔のRank : term spam で死亡
    • 定義
      • 行き止まりがあったり強連結じゃなかったらやばい
    • でも本当の Web Graph の構造はこうなってる (P.151,この図オモロイ大事)
    • 行き止まりに対応するには?
      • 行き止まり削除して,親と同じ page rank にする,か,taxation
    • taxation
      • たまにやめてどっかとぶ
  • Topic-Sensitive Pagerank
    • taxation の部分を偏らせる
  • Link Spam
    • TrustRank: 信用デキそうな奴らに偏った topic-sensitive pagerank
    • spam mass: PageRank と TrustRank の差がでかいとスパムだわ
  • HITS
    • hub っぽさ h と authority っぽさ a が交互に出てくる