最近、学校で習ったことをちょっとくらいは世間に役立てようと、いろいろごちゃごちゃしてるわけですが、ぼちぼち進行してたりしてます。
というか、普段やってたことを、学校で整理して勉強して、改めてフィードバックしてるだけだったりもするんですが。

今日は、グラフ構造を解析する上での超基本技の強連結成分分解というテクニックでレポートを書かなくてはならい感じでした。
ざっくりいうと、リンクがぐるっと一周回ってると、それが同じくラスタとして抽出できるということです。
同じような内容のwebページがリンクしあってるというのであれば、これを使ってウェブページを分類できそうです。

と、おもって単純にやってみたらうまくいきませんでしたorz
なんでかというと、ほとんどのページがTOPページへリンクされているので、ほとんどのページが同じくラスタになってしまうわけですね(^^;;;;;;;;;;;
つまり適当なところで、リンクを分割せねばなりません。
完全にやろうとすると、完全にコスト過多（どうせ適当に書いたって実験はいい成績つく・・・）なので、とりあえずそれっぽい方法を考案してみました。

手順の概略は単純です。

1. 被リンク数でソートする。
2. 割とはっきりと被リンク数がジャンプしている箇所が見つかるので、そこを閾値に設定
3. 閾値以上の被リンク数をもつページへのリンクを全部カットする
4. 強連結成分分解する

改良点の発想は、被リンク数の多いページを「インデックスページ」か「目次」と考えて、そこに末端のページからリンクバックしないようにしようという感じです。
これがまぁまぁいい感じにできました。最初一つのクラスタだった（つまりまったく分類できてなかった）のがとりあえず意味のある4つとその他に分類できました。
とりあえず学部実験なのでこんなもんでいいか・・・と見切りをつけてざざっと書いた。

一応、他の場合も考えてみたりしました。
たとえば、「被リンク数ではなくてページ内のリンクの数で閾値を決める」「被リンク数とリンク数の両方を使う」「被リンク数とリンク数の差の自乗を使う」とかなんとか。
結構偏りがでるので意味があるかなと思ってやってみたんですが、どうもいい感じにはなりません。
被リンク数が一番いい感じでした。（いい感じって何だろう

グーグルのページランクもしかりですが、被リンクにはやはりそれなりの意味（情報）があるのかもしれないですね。
ただ今テスト前なのと、もっとやりたいことと、やんなくちゃいけないことと、楽しいことたちが待ってるので、このくらいにしようと思います。

今回はあらかじめ与えられたリンク情報からやったので必ずしも一般的な議論ではないですが、解析としてはまぁまぁ面白かった気がします。

追記：

クローラから設計するときはもうちょい賢い実装をします。が、学校の課題に全力注いでも、リターンが少なすぎるというちょっと悲しい現実があったりするので、そこらへんはスルーです。
なので、あんまし突っ込まないでください。

追記：

適当な深さで分割できるようにできると便利なんだろうけど。と、ちょっと思った。