DouKaku? 2333 yuin: 一番乗り？出力は { 0...(PageRankの計算)

Comment detail

一番乗り？

出力は

{
0.3035143769968051,
0.16613418530351443,
0.1405750798722045,
0.10543130990415332,
0.17891373801916935,
0.04472843450479228,
0.06070287539936102
}

という感じです。

JAMAを使いました。

see: JAMA

import Jama._

def pagerank(data:Map[int, List[int]]):Array[double] = {
  val m = (1 to data.size).map(x=>Array.make(data.size, 0d)).toArray
  for(val i <- data) {
    for(val j <- i._2) {
      m(j-1)(i._1-1) = 1.toDouble / i._2.size
    }
  }

  val m2 = new Matrix((new Matrix(m)).eig.getV.getArray.map(x=>x(0)), data.size)
  val norm1 = m2.norm1
  m2.getArray.map(x => x(0) / norm1)
}
println(pagerank(Map(
  1 -> List(2,3,4,5,7),
  2 -> List(1),
  3 -> List(1,2),
  4 -> List(2,3,5),
  5 -> List(1,3,4,6),
  6 -> List(1,5),
  7 -> List(5)
)).mkString("{\n",",\n","\n}"))

参考のサイト「Googleの秘密 - PageRank徹底解説」での求め方では「絶対値が最大の固有値に対応する固有ベクトル」を取り出すようになっています。しかし、当サイト自身にもありますが、現実には該当する固有ベクトルは必ず第一列目に来るようです。そんなものなのでしょうか。

私も詳しくないのですが。

詳しくは参考URLに書いてありますが、このお題のようなリンク構造のグラフは強連結ですので、対応する遷移行列は常に絶対値が最大1の固有値の固有ベクトルを持ちます。

ですのでそんなものだ、と理解しています。

see: アルゴリズム工学特論

僕も詳しくはないですが、数学的に「固有値を求める」と表現したときには、どういう手順で求めるのかまでは言及しておらず、結果がどういう順番で並んでいるかは定義されていません。

一方、数値計算ライブラリはなんらかのアルゴリズムで実装されているわけで、アルゴリズムによっては結果が必ずソートされた状態で出てくるものもあるかとは思います。現状は「どうも固有ベクトルが固有値でソートされた状態で出てくるライブラリが多そうだ」ということでしょう。

つまり最大固有値の固有ベクトルが1行目にあるかどうかは、固有値の性質ではなくライブラリの性質なので、ライブラリによっては1行目にないかもしれません。

なるほど、やはりライブラリの実装依存なのですね。よく解りました。

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq