JavaでPageRankアルゴリズム

有名なgoogleのPageRankアルゴリズム。
今更ながらどうやって実装してるのか調べてみました。

評価の高いページに参照されてるページは評価が高いはず、の仮説に基づいているのは有名な話ですが、実際にこれをコードに落としこむロジックはなかなか綺麗で良くできているものだと感心してしまいました。

論文に書かれている再帰的な数式をどうプログラムで表現すべきか、的な話はこちらが詳しいので興味を持った方はご参照を。

リンク解析とか: 重要度尺度と von Neumann カーネル



今回はこのPageRankをJavaで実装してみようと思いました。
はじめは普通にPowerMethodをJavaで実装しようかと思ったんですが、使いやすそうなライブラリを見っけたのでこれを使って書いて見ることにしました。

利用したのはJung(Java Universal Network/Graph Framework)というネットワーク・グラフ解析用のライブラリ。JungにはHITSやPageRankなどノード間をスコア付けするクラスが多数含まれています。

実際にサンプルコードを書くと次のようになりました。

  Graph<Integer, Integer> g = new DirectedOrderedSparseMultigraph<Integer, Integer>();

  // add 5 nodes to graph model.
  g.addVertex(0);
  g.addVertex(1);
  g.addVertex(2);
  g.addVertex(3);
  g.addVertex(4);
  // add edge to graph model
  g.addEdge(0, 0,1,EdgeType.DIRECTED); // directed edge from 0 to 1
  g.addEdge(1, 0,2,EdgeType.DIRECTED); // directed edge from 0 to 2
  g.addEdge(2, 1,2,EdgeType.DIRECTED); // directed edge from 1 to 2
  g.addEdge(3, 1,3,EdgeType.DIRECTED); 
  g.addEdge(4, 2,1,EdgeType.DIRECTED); 
  g.addEdge(5, 2,2,EdgeType.DIRECTED); 
  g.addEdge(6, 2,3,EdgeType.DIRECTED); 
  // calculate the page rank. 
  PageRank<Integer,Integer> pr = new PageRank<Integer,Integer>(g,0.2);
  pr.evaluate();  
  
  System.out.println(g);
  
  for (Integer i : g.getVertices()) {
          System.out.println(pr.getVertexScore(i));
  }

なんて簡単。
しかし、もうpagerankも学術用ライブラリに普通にはいってるご時世なんですね。

おまけ。
せっかくなので各種言語でサンプルコードやライブラリを集めてみました。

python

リンク解析とか: 重要度尺度と von Neumann カーネル(冒頭で紹介したサイト)

perl

PDL で PageRank

ruby

PageRankをRubyで実装

C++

初投稿　PageRankの計算 C++でどう書く？