JavaでPageRankアルゴリズム

有名なgoogleのPageRankアルゴリズム。<br />
今更ながらどうやって実装してるのか調べてみました。<br />
<br />
評価の高いページに参照されてるページは評価が高いはず、の仮説に基づいているのは有名な話ですが、実際にこれをコードに落としこむロジックはなかなか綺麗で良くできているものだと感心してしまいました。<br />
<br />
<a href="http://ilpubs.stanford.edu:8090/361/1/1998-8.pdf" target="_blank">論文</a>に書かれている再帰的な数式をどうプログラムで表現すべきか、的な話はこちらが詳しいので興味を持った方はご参照を。<br />
<br />
<a href="http://d.hatena.ne.jp/smly/20090228/1235792969" target="_blank">リンク解析とか: 重要度尺度と von Neumann カーネル</a><br />
<br />
<!--more--><br />
<br />
今回はこのPageRankをJavaで実装してみようと思いました。<br />
はじめは普通にPowerMethodをJavaで実装しようかと思ったんですが、使いやすそうなライブラリを見っけたのでこれを使って書いて見ることにしました。<br />
<div class="p1">
<br />
利用したのは<a href="http://jung.sourceforge.net/" target="_blank">Jung(Java Universal Network/Graph Framework)</a>というネットワーク・グラフ解析用のライブラリ。JungにはHITSやPageRankなどノード間をスコア付けするクラスが多数含まれています。<br />
<br />
実際にサンプルコードを書くと次のようになりました。<br />
<br />
<pre class="brush: javascript;" type="syntaxhighlighter">  Graph&lt;Integer, Integer&gt; g = new DirectedOrderedSparseMultigraph&lt;Integer, Integer&gt;();

  // 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&lt;Integer,Integer&gt; pr = new PageRank&lt;Integer,Integer&gt;(g,0.2);
  pr.evaluate(); 
 
  System.out.println(g);
 
  for (Integer i : g.getVertices()) {
          System.out.println(pr.getVertexScore(i));
  }
</pre>
<br />
<br />
なんて簡単。<br />
しかし、もうpagerankも学術用ライブラリに普通にはいってるご時世なんですね。</div>
<br />
<br />
<br />
おまけ。<br />
せっかくなので各種言語でサンプルコードやライブラリを集めてみました。<br />
<br />
<br />
<h3>
python</h3>
<a href="http://d.hatena.ne.jp/smly/20090228/1235792969" target="_blank">リンク解析とか: 重要度尺度と von Neumann カーネル</a>(冒頭で紹介したサイト)<br />
<br />
<h3>
</h3>
<h3>
perl</h3>
<a href="http://d.hatena.ne.jp/naoya/20090305/1236255363%22" target="_blank">PDL で PageRank</a><br />
<br />
<h3>
ruby</h3>
<a href="http://d.hatena.ne.jp/yyuto/20091029/1256829755" target="_blank">PageRankをRubyで実装</a><br />
<br />
<h3>
C++</h3>
<a href="http://yoheiz.blogspot.jp/2007/09/pagerank-c.html" target="_blank">初投稿　PageRankの計算 C++でどう書く？</a><br />
<br />
<br />

コメント

コメントを投稿

このブログの人気の投稿

麻雀の牌を表示するJavascriptライブラリ

イメージ
以前に公開したJavaの麻雀AIサーバである SmartBird から麻雀の牌を描画する部分だけ取り出してライブラリ化しました。 https://github.com/kentan/MahjongTileDrawingJS/tree/master 麻雀の牌はフリー素材などがいっぱいあったりしますが、今回公開したのはHTML5のcanvasタグを使ってその場で描画するタイプです。 使い方は下記のようにシンプル。 萬子はCharacter,索子はBamboo,筒子はCircleで表現しているので例えば5索を書きたい場合はdrawBamboo5("canvasタグのID")といったふうに呼び出せば、引数に指定したcanvasタグに5索が描かれます。 サンプル用のhtmlファイル <html> <head></head> <body onload="startDrawing()"> <canvas id = "canvas1" width="50px" height="60px"></canvas> </body> ライブラリを呼び出すサンプル用のjavascript function startDrawing(){ tileDrawing.drawCharactor1("canvas1"); } 詳細はgithubにあるサンプルコードを見てください
続きを読む

[読書感想文]Accelarate

Accelarate 日本語版はこっち。 LeanとDevOpsの科学［Accelerate］ テクノロジーの戦略的活用が組織変革を加速する Who should read this? 少々おすすめ先に悩む本である。 DevOpsのプラクティスの効果について理論付けがなされているので、DevOpsを自社に導入したい人にはいいかもしれないと思ったが、今の時代においてそもそもDevOpsを導入していないステージの会社にはいろいろと前提がかけているために読みやすさかける本になっているだろう。 普段実践していることについて、主観的・感覚的には正しさを信じているのだが、それだけでは飽き足らず、客観的な裏付けがほしい、みたいな人が読んで嬉しい本になるのかもしれない。 Impression DevOpsやLeanの手法に知見のある人には、少々退屈な本に映るかもしれない。いわば業界の常識となったプラクティスがデータに基づいて結論として書かれている。後半はServeyを行う際の理論や手法について書かれており、このあたりもDevOpsとLeanに興味があって本を手にとった人には期待はずれに思えるかもしれない。 普段当たり前と信じていたことが、 科学的な理論に基づいたServeyによって得られたデータによって裏付けられたことがわかるのが本書の利点だろうか。
続きを読む

[読書感想文]バイリンガルを育てる

バイリンガルを育てる まとめ 英語教育やバイリンガル教育が専門の湯川笑子博士が自分自身の二人の子供にバイリンガル教育をさせたときの記録集。体験や観察をもとに論文も書いているようであり、詳細な記録は参考になる。 教育内容として大きく目をひかれるのは下記のような事柄 子供には常に英語で話しかける。 幼少期に英語の本の読み聞かせを毎日30分から2時間程度 ネイティブなEnglish Speakerと多くの交流があり、自宅にホームステイさせたり等、子供をInternationalな環境においていた。 子供は幼少期に海外で教育させた。 長男。4ヶ月-1歳半と5歳5ヶ月-5歳10ヶ月までハワイ、6歳-8歳ころにスウェーデンの幼稚園、学校に通う 長女は4歳-5歳ころにスウェーデンの保育園に通う 感想 おうちでバイリンガル や おやこえいご などを読んだときも同じ感想を抱いたが、やはり親（特に母親）の尋常でない献身ぶりが目を引く。毎日2時間も英語の本を読み聞かせるだけでも、尋常でない気力が必要だし、ましてや海外に引っ越して現地の教育を受けさせるなどというのは並々ならぬ覚悟がいるだろう。著者の場合は、自分の研究テーマと同一していることもあり、仕事のキャリアと英語教育のメリットを同一化させられたのも大きな要因であろう。 参考にはなるが、一般的な日本人にとってすぐさま真似できそうな実践はなさそうである。また、結局この本で行ったバイリンガル教育の結果、成人した子どもたちがどのような英語力・日本語力が身についたのかが不明なのも実践の効果を伺い知れる情報がなく残念ではある。
続きを読む