PageRankの計算 in Java DouKaku?

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

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

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

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

Javaも標準では行列計算がサポートされていないので、冪乗法で。
固有ベクトルの計算はページランク計算を前提としない、汎用のもののつもり。（ライブラリの代わりなので）
収束しない場合にArithmeticExceptionを投げてるけど、これは手抜き。ホントは（呼び出し元は収束するか事前に判断できないので）チェック例外を投げるべき。

public class PageRank {
    private static final int MAX_REPEAT = 1000;

    public static void main(String[] argv) {
        int[][] data = {{ 2, 3, 4, 5, 7 }, 
                        { 1 }, 
                        { 1, 2 }, 
                        { 2, 3, 5 },
                        { 1, 3, 4, 6 }, 
                        { 1, 5 }, 
                        { 5 }};

        double[][] a = new double[data.length][];
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < data[i].length; j++) {
            a[data[i][j] - 1][i] = 1.0 / data[i].length;
            }
        }
        double[] eigVec = calcEigenVector(a);

        double sum = 0.0;
        for (int i = 0; i < eigVec.length; i++) sum += eigVec[i];
        for (int i = 0; i < eigVec.length; i++) System.out.println(eigVec[i] / sum);
    }

    /** べき乗法により、行列の固有ベクトルを求める。 */
    private static double[] calcEigenVector(double[][] mat) {
        final int n = mat.length;
        if(n != mat[0].length) throw new IllegalArgumentException("正方行列じゃないとダメだよ。");
        double eigVec[] = new double[n];
        eigVec[0] = 1.0;

        double eigVal = 1.0;
        
        for(int count=0; count < MAX_REPEAT; count++) {
            double[] newVec = new double[n];
            double df = 0;
            for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) newVec[i] += mat[i][j] * eigVec[j];
            df = Math.max(df, Math.abs(newVec[i] - eigVal * eigVec[i]));
            }
            if(df < 1.0e-8) return eigVec;
            
            double norm = 0;
            for (int i = 0; i < n; ++i) norm += newVec[i] * newVec[i];
            eigVal = Math.sqrt(norm);
            for (int i = 0; i < newVec.length; i++) eigVec[i] = newVec[i] / eigVal;
        }
        throw new ArithmeticException(MAX_REPEAT+"回やっても収束しませんでした。");
    }
}

JAMA使用版を書きました。

不勉強にてJAMAのことも、そもそもScalaがJVM上の言語であることも知りませんでした…orz

最初 jakarta-commons Mathを覗いてみたんですけど、Matrixはあっても固有ベクトル計算はサポートされてなくて、奥村先生のアルゴリズム辞典のヤコビ法のやつを使ったんですが、うまくお題の答えにならなくて(なにが間違っていたかは以下のコードを書いてわかりました。)、結局あのコードになったんですけどね。

package doukaku;
import Jama.Matrix;

public class PageRank {

	public static void main(String[] argv) {
		int[][] data = {{ 2, 3, 4, 5, 7 }, 
				         { 1 }, 
				         { 1, 2 }, 
				         { 2, 3, 5 },
				         { 1, 3, 4, 6 }, 
				         { 1, 5 }, 
				         { 5 }};

		double[][] a = new double[data.length][data.length];
		for (int i = 0; i < data.length; i++) {
			for (int j = 0; j < data[i].length; j++) {
				a[data[i][j] - 1][i] = 1.0 / data[i].length;
			}
		}
		double[] eigVec = new Matrix(a).eig().getV().transpose().getArray()[0];
		double norm1 = new Matrix(eigVec, eigVec.length).norm1();
		for (int i = 0; i < eigVec.length; i++) System.out.println(eigVec[i] / norm1);
	}
}

DouKaku?

PageRankの計算

Posted feedbacks - Java

Index

Feed

Other

Link

Pathtraq