PageRankの計算 in D DouKaku?

PageRankの計算

ページランク - 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]

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

post comment

Posted feedbacks - D

固有ベクトルはべき乗法を使って自前で計算しています。
行列演算についてはかなり手を抜いています。

import std.stdio;
import std.math;

//  行列演算用の手抜き関数 ここから
real[][] zeroMatrix(uint rowSize, uint colSize){
    real[][] zeroMatrix;
    for(uint i; i < rowSize; i++){
        real[] row;
        for(uint j; j < colSize; j++){
            row ~= 0.0;
        }
        zeroMatrix ~= row;
    }
    return zeroMatrix;
}

real dotProduct(real[] rowVector, real[] colVector){
    real dotProduct = 0.0;
    foreach(i, e; rowVector){
        dotProduct += e * colVector[i];
    }
    return dotProduct;
}

real norm(real[] vector){
    return sqrt(dotProduct(vector, vector));
}

real[] normalize(real[] vector){
    return divide(vector, norm(vector));
}

real[] multiply(real[][] matrix, real[] colVector){
    real[] retColVector;
    foreach(row; matrix){
        retColVector ~= dotProduct(row, colVector);
    }
    return retColVector;
}

real[] divide(real[] vector, real divisor){
    real[] retVector;
    foreach(e; vector){
        retVector ~= e / divisor;
    }
    return retVector;
}

real[] eigenVector(real[][] matrix){
    real[] ev0;
    for(uint i; i < matrix.length; i++){
        ev0 ~= i == 0;
    }
    for(uint t; t < 1000; t++){
        real[] ev1 = normalize(multiply(matrix, ev0));
        for(uint i; i < ev0.length; i++){
            if(abs(ev0[i] - ev1[i]) > 1e-16){
                ev0 = ev1.dup;
                break;
            }
            if(i == ev0.length - 1){
                return ev1;
            }
        }
    }
    return [];
}
//  行列演算用の手抜き関数 ここまで


real[] pageRank(uint[][] data){
    real[][] mat = zeroMatrix(data.length, data.length);
    foreach(i, row; data){
        foreach(j; row){
            mat[j - 1][i] = 1.0 / row.length;
        }
    }
    real[] eigenVector = eigenVector(mat);
    real[] pageRank;
    real sum = 0.0;
    foreach(e; eigenVector){
        sum += e;
    }
    foreach(e; eigenVector){
        pageRank ~= e / sum;
    }
    return pageRank;
}

void main(){
    uint[][] data = [
                     [2, 3, 4, 5, 7],
                     [1],
                     [1, 2],
                     [2, 3, 5],
                     [1, 3, 4, 6],
                     [1, 5],
                     [5]
                    ];
    writefln(pageRank(data));
      //=> [0.303514,0.166134,0.140575,0.105431,0.178914,0.0447284,0.0607028]
}

DouKaku?

PageRankの計算

Posted feedbacks - D

Index

Feed

Other

Link

Pathtraq