PageRankの計算
Posted feedbacks - C#
標準では、固有値も行列演算もサポートされていないので、自分で計算しています。結果は、合っていると思います。 0.30351438 0.16613419 0.14057508 0.10543131 0.17891374 0.04472843 0.06070287
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | using System;
class Program
{
static void Main()
{
string data = "2 3 4 5 7,1,1 2,2 3 5,1 3 4 6,1 5,5";
double[] pageRank = Calc(data);
foreach (double d in pageRank) Console.WriteLine("{0:F8}", d);
}
static double[] Calc(string data)
{
string[] ss = data.Split(',');
double[,] m = new double[ss.Length, ss.Length];
for (int i = 0; i < ss.Length; ++i)
{
string[] tt = ss[i].Split();
for (int j = 0; j < tt.Length; ++j)
m[int.Parse(tt[j]) - 1, i] = 1.0 / tt.Length;
}
double[] pageRank = new double[ss.Length];
for (int i = 0; i < pageRank.Length; ++i) pageRank[i] = 1.0 / pageRank.Length;
double df = 1;
while (df > 1e-8)
{
double[] nxt = new double[ss.Length];
for (int i = 0; i < ss.Length; ++i)
for (int j = 0; j < ss.Length; ++j)
nxt[i] += m[i, j] * pageRank[j];
df = 0;
for (int i = 0; i < ss.Length; ++i)
df = Math.Max(df, Math.Abs(nxt[i] - pageRank[i]));
pageRank = nxt;
}
return pageRank;
}
}
|
ところてん
#3404()
Rating0/0=0.00
詳しい導出方法はGoogle の秘密 - PageRank 徹底解説の3章に載っていますが、 簡単に説明すると
という流れになります。
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]このお題はところてんさんの「行列演算系のお題が欲しい」という要望を元に考えたものです。ありがとうございました。[ reply ]