2012年1月11日水曜日

最密グラフのヒューリスティクス

金曜日に聞いた話で、submodular を使うと与えられたグラフの最密部分グラフがわかる、ということで、これはSNLの計算につかえるのでは?と思って調べている。

まず、いきなり submodular だとハードルが高すぎるので、比較的わかりやすそうなヒューリスティクスで、雰囲気をつかむことにした。

今回実装したヒューリスティクスは、

http://www.cs.umd.edu/~barna/icalp-final.pdf
である。
アルゴリズムとしては、degree の低い node からはずしていって、外すごとに密度を計算する。
この過程で最大の密度を達成したところが、ヒューリスティクスの算出する最密部分グラフである。

このヒューリスティクスでは2倍の精度で最適解を出力する。
つまり、最大密度が 0.9 なら、このヒューリスティクスでは 0.45 から 0.9 の密度となる部分グラフが求まる。

実際にやってみるとわかったが、2倍の精度というのは自分の感覚と相当ずれている。
たとえば、
[0,1]x[0,1] の2次元正方形にランダムに100個のノードをばら撒いて、[0.1,0.5]x[0.2,0.6] に 20 個をばら撒く。
このとき、距離が 0.15 以下となるノード同士を枝でつなぐ。

想定としては [0.1,0.5]x[0.2,0.6]に集中配備だから、ここが最密部分グラフとなるかと思うのだが、乱数によって、ここが出力されたり、グラフ全体を出力したり、ということが、ままある。
あと、乱数の関係で2ノードだけが他から孤立していて、その2ノードは互いにつながっている、という孤島ができることがあるのだが、このとき何故か片方だけが最密部分グラフに取り込まれたりする。

やはり、2倍の精度というのは、SNL 計算には甘いのかもしれない。
いずれにしても、だいたいの雰囲気はわかったので、これで submodular についても検討してみようと思う。

今日の作業内容:最密部分グラフ 3h
今日のランチ:ちゅらさん
明日の予測作業時間:3h

0 件のコメント:

コメントを投稿