PageRankについて教えてください。

[wakarannyo]

C++で実装しなければならないのですが、どのように処理したら良いのか分からないので教えてください。

実行方法
<program name> RUN <input filename> <number of iterations> <decay factor>

<input filename>は、最初に２番目の項目に接続接続していることを示す、
1行に2つのノード、すなわち1つのグラフのリンクを含んでいます。
たとえば、入力ファイル内の2つの行は次のようになります。
yahoo.co.jp google.co.jp
google.co.jp google.com

また、以下の内容を含む。
1。 PageRankアルゴリズムと、画面への出力、診断情報の結果を出力。
最終的な出力は、入力グラフの各ノードのPageRankである必要があります。
2。重複リンク、外部からのリンクを持つノード、および自己ループを正しく処理。

[みけCAT]

丸投げは禁止です。フォーラムルールをお読みください。
自分で出来た途中のコードがあれば、それを提示してください。
このPageRankアルゴリズムについて詳しく教えてください。

[wakarannyo]

質問の意図が分からないので、ページランクについて知っている方がいたら教えてほしいという内容です。
アルゴリズムが分かれば解決できるのですが、そのアルゴリズムが分からないので、
ソースコードに落とすことが出来ない状況にあります。
こんな感じで解けば良いというのが例でも分かれば自分もソースを作ることが出来るのですが、
分からないのが今の状況です。

現在作りかけのソースは以下になります。

コード:

 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <stdio.h>
#include <string.h>
#include <fstream>
#include <string>
using namespace std;

const double EPS = 1e-9;
typedef float number;
typedef vector<vector<int> > adj_t; // 隣接リスト方式で作る
class PageRank {

private:
    int n; // ページ数
    adj_t a; // リンクデータ
    number alpha; // ランダムに飛ぶ確率
    vector<int> initial; // 最初に値を振るノード
    
    inline double sq(double x) { return x*x; }
    double diff(const vector<number>& prev, const vector<number>& cur) {
        double ret = 0.0;
        for (int i = 0; i < n; i++)
            ret += sq(cur[i]-prev[i]);
        return ret;
    }

public:
    PageRank(int n, number alpha): n(n), a(n), alpha(alpha) {
        for (int i = 0; i < n; i++) initial.push_back(i);
    }

    PageRank(int n, number alpha, vector<int> initial): n(n), a(n), alpha(alpha), initial(initial) {}
    void add_link(int from, int to) {
        a[from].push_back(to);
    }

    vector<number> calc() {
        //シーケンシャルアクセス用にソートしておく。(HDでは重要、今回はほぼ意味なし)
        for (int i = 0; i < n; i++) sort(a[i].begin(), a[i].end());
        
        const int ini_size = initial.size();
        const number beta = 1.0/ini_size; // ベータはつまりこういう意味
        vector<number> prev(n), cur(n, beta);
        do {
            cur.swap(prev);
            cur.clear();
            cur.resize(n);
            for (int i = 0; i < n; i++) {
                const int size = a[i].size();
                const double val = 1.0/size * (1.0-alpha);
                for (int j = 0 ; j < size; j++) 
				    cur[a[i][j]] += prev[i]*val;
            }
            const number alphabeta = alpha*beta;
            for (int i = 0; i < ini_size; i++)
                cur[initial[i]] += alphabeta;
        
            //for debug
            for (int i = 0; i < n; i++) cerr<<prev[i]<<" "; cerr<<endl;
        }
        while (diff(prev,cur) > EPS);
        return cur;
    }
};

int main(int argc, char *argv[]) {

//    printf("***%s***\n", argv[i]);

printf("argv[0]=[%s]\n",argv[0]);
printf("argv[1]=[%s]\n",argv[1]);
printf("argv[2]=[%s]\n",argv[2]);
printf("argv[3]=[%s]\n",argv[3]);

    if (strcmp(argv[1],"CHECK") == 0) {
		printf("CHECK DATA\n");
	}
    else if (strcmp(argv[1],"RUN") == 0) {
		printf("RUN DATA\n");
	}
	else{
		printf("OTHER INPUT DATA\n");
		return 0;
	}



    const number alpha = 0.15;
//    int node; cin>>node; // ノード数

	string file_name = argv[2];
	ifstream fin(file_name.c_str());
	if(!fin)
	{
		cout<<"fail open file"<<endl;
		return 0;
	}
    int node; fin>>node; // ノード数
/*    
	while(fin>>data)
	{
		net[i][j++] = data;
		if(j==size)
		{
			i++;j=0;
		}
	}
*/

//printf("cin=[%d]\n",cin);
printf("node=[%d]\n",node);

    PageRank pr(node, alpha);
    for (int i = 0; i < node; i++) {
//        int m; cin>>m;
        int m; fin>>m;

printf("m=[%d]\n",m);

        assert(m > 0); // 終端ノードがないことを保障
        for (int j = 0; j < m; j++) {
//            int k; cin>>k;
            int k; fin>>k;
printf("k=[%d]\n",k);

            pr.add_link(i,k);
        }
    }
    vector<number> result = pr.calc();
    number sum = 0.0;
    cout<<"\nresult:"<<endl;
    for (int i = 0; i < result.size(); i++) {
        sum += result[i];
printf("sum=[%d]\n",sum);
//        cout<<result[i]<<endl;
    }
//    cout<<"sum="<<sum<<endl; // 1にならないとおかしい

    return 0;
}

[softya（ソフト屋)]

codeタグを使ってくださいね。

PageRankアルゴリズムとコレのことではないでしょうか？
「ページランク - Wikipedia」
http://ja.wikipedia.org/wiki/%E3%83%9A% ... 3%E3%82%AF

[wakarannyo]

はい、そのページランクのアルゴリズムなのですが、
それと、今回問題として出された以下の内容と結びつかなくって困っております。

> 実行方法
> <program name> RUN <input filename> <number of iterations> <decay factor>
>
> <input filename>は、最初に２番目の項目に接続接続していることを示す、
> 1行に2つのノード、すなわち1つのグラフのリンクを含んでいます。
> たとえば、入力ファイル内の2つの行は次のようになります。
> yahoo.co.jp google.co.jp
> google.co.jp google.com

[softya（ソフト屋)]

深く考えずに書いてますが、 グラフ理論でアルゴリズムを組み立てろって事だと思います。
テキストデータを次のように解釈しろってことでしょう。

コード:

ノード    　　エッジ
yahoo.co.jp google.co.jp
google.co.jp google.com

私もグラフ理論には詳しくないので、これ以上の答えは出せませんが今までの講義内容でヒントとなるような内容は無かったのでしょうか？

参考になりそうなサイト。文字化けしたら文字エンコーディングはEUC-JPを選んでください。
「Google の秘密 - PageRank 徹底解説」
http://homepage2.nifty.com/baba_hajime/ ... erank.html

[YuO]

ちゃんとフォーラムルールにしたがって，マルチポスト先への相互リンクを行って下さい。

PageRankを実装するには？ - VIsual C++ Q & A掲示板 - Programming Library - VB/VC/Delphi総合情報ページ (注:トップページは音が鳴ります)

[wakarannyo]

初めてこの掲示板を使用したのでフォーラムルールが分かっていなくてすみません。

[softya（ソフト屋)]

今からでも遅くないのでルールにある通り相互リンクをお願いします。

[ゆうたろう]

ページランクのアルゴリズムがわからないとのことですが
自分だったらどうするか考えててみればいいと思います
自分なら貴重な情報のサイトを見つけたら
①ブラウザのブクマボタンを押す
②何度もそのページを訪問する
とかですね。
なんらかの方法で上の数値を取得できたら。あとは大きい順にソートするだけでいいと思います
その値が多きければ多いほど有効な情報である可能性が高いってことです
（②はIP抜いて同一IPが３日以内に同じページ訪問したらカウント＋１とするとか）
まあページの重要度を測るのは被リンク数だけじゃなく他にもあるし
簡単なほう選べばいいんじゃないでしょうかってことです