DouKaku?

ページランク - Wikipediaを求めるプログラムを作ってください。(PageRankはGoogleの商標です)

詳しい導出方法はGoogle の秘密 - PageRank 徹底解説の3章に載っていますが、 簡単に説明すると

1. ページがn枚ある場合、n×nの2次元配列を用意する。
2. ページiからページjにリンクがある場合、mat[j][i] = 1 / num_link[i]とする。ただしnum_link[i]はi番目のページから出ているリンクの総数。
3. 行列計算ライブラリを使ってできあがった2次元配列の固有値、固有ベクトルを求める。
4. 出力された固有ベクトルから合計が1になるようなPageRankを算出する

という流れになります。

Pythonで表現すると下のようになります。 ?????の部分は空行を入れて10行でしたので 何百行ものコードになってしまった場合は きっとお題の趣旨から外れていると思います。 このお題の趣旨は「行列計算ライブラリを使って」PageRankを計算することなので、 自力で固有値の計算を実装することは求められていません。

data = {
    1: [2, 3, 4, 5, 7],
    2: [1],
    3: [1, 2],
    4: [2, 3, 5],
    5: [1, 3, 4, 6],
    6: [1, 5],
    7: [5],
}

?????

print pagerank
# [0.303514376997, 0.166134185304, 0.140575079872,
#  0.105431309904, 0.178913738019, 0.0447284345048,
#  0.0607028753994]

このお題はところてんさんの「行列演算系のお題が欲しい」という要望を元に考えたものです。ありがとうございました。

一番乗り？

出力は

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

という感じです。

JAMAを使いました。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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}"))