Weibo での PageRank アルゴリズムの適用

このアイデアは、かなり早い段階で思いつきました。私は検索エンジンの経験があるため、検索エンジンにおける PageRank アルゴリズムの重要性を深く理解しています。これは間違いなくコア テクノロジーの 1 つです。ただし、このブログでは PageRank アルゴリズムの原理を紹介するつもりはありません。代わりに、この重要なアルゴリズムが Sina Weibo でどのように適用されているかを見てみましょう。

Web ページの重要性はリンクを通じて伝達されます。 Weiboではどうですか？これも事実です。しかし、Weiboでは状況はより複雑です。そこで私は、PageRank全体を計算する（つまり、全員が計算に参加する）ことには同意できないとWeiboで指摘しました。これにはいくつかの理由があります:

1. 人物の主題属性は、Web ページの主題属性とは異なります。 Web ページには、通常 1 つのトピックしかありませんが、人には多くのトピック属性があります。トピック属性は、人の興味として理解できます。一般的に、人は複数の興味を持っています。
2. 人々の興味は時間とともに変化し、ほとんどの Web ページのテーマは作成後も基本的に変更されません (ただし、Web ページの PageRank は、主にリンク関係の変化などにより、定期的に再計算する必要があります)。
3. 興味に基づいた注目に加えて、Sina Weibo には友情、つまり本当の友情もあります。

1 点目については、人々の興味の多様性は非常に明白であり、各ユーザーのタグや Weibo コンテンツから直接見ることができます。それで、私たちは何をすべきでしょうか?私のポイントは、特定の分野における Weibo ユーザーの PageRank を計算することです。このようにして、この分野における人々の影響力のランキングを得ることができます。これは非常に便利です。草の根レベルの人は専門家を探すのに、ヘッドハンターは候補者を探すのに使えます。候補者のレベルを非常に直感的に表示できます。上記のことを理解するために、例を挙げてみましょう。まずはタグから。Weiboユーザーはなぜタグを使うのでしょうか？（Twitterにはタグがありません。Sina Weiboはデータの宝庫です。10人中1人しかタグを持っていませんが、それでもこのデータは非常に貴重です。）おそらく2つの理由があると思います:

1. 私の興味は映画、音楽、考古学などです。
2. 私の専門分野: Java、データマイニング、機械学習、自然言語理解など。

タグはユーザー自身によって定義されるため、正確でない場合があります。このとき、正確さの度合いを測定するための手段が必要です。Pag​​eRank は良い手段です。たとえば、私は自分の興味を「考古学」と名付けています。通常は、考古学情報のWeiboや考古学の権威をフォローします。この注意がなければ、関心は疑わしいものとなるでしょう。たとえば、私は自分自身を「複雑ネットワーク」とタグ付けしましたが、私のファンは誰もこれに興味がありません。それでも私はこの分野の専門家になれますか？専門家はすべての人に認められる必要があります。したがって、主にこの観点からすると、完全な PageRank に対する需要はそれほど強くありません。

2 点目に関しては、ソーシャル ネットワークは変化し、進化していることを十分に理解する必要があります。多くの人々がこの進化の法則とプロセスを研究しています。今は興味がないけど、まだここにはいません。しかし、この「変更」はランク計算にどの程度の影響を与えるのでしょうか?実際、ネットワークの進化は段階に分かれています。大きな変化もあれば、ゆっくりとした変化もあります。大きな変化があったときはネットワーク構造が大きく変化しますが、それ以外のときはネットワーク構造は比較的安定しています。例えば、Sina Weiboは現在毎日ユーザーが登録しており、登録ユーザー数が5億人を突破したと発表されるのもそう遠くないかもしれません。しかし、一部の地域ではネットワーク構造が比較的安定し、来るべき人がほぼ全員来ているという状況です。彼は来るべきではなかったし、今後も来る可能性は低い。そのため、現時点では、PageRank を計算して得られたランキング結果は、一定期間適用されます。ただし、Web ページを再計算するよりも頻繁に、定期的に再計算することをお勧めします。

3 点目に関して、私たちが主に考慮するのは、社交界の探索です。ここでは多くは語りません。

長々と話して、話が脱線してしまいました。では、何を使って計算するのでしょうか?スタンドアロン ツールキット、MapReduce ベースのツール、Spark ベースのツールなど、PageRank を効率的に計算する方法は多数あります。 Graphchi というツールを紹介します。これは非常に強力で、Spark よりも強力で、Hadoop に似ていると言われています。そのまま渡すだけです。

上記では、Weibo での PageRank の適用について詳しく説明しています。次に、graphchi を使用して、ほぼ完全な PageRank である 3,000 万人の PageRank を計算します。

grapchi の使い方を簡単に紹介します。

1. graphchi をダウンロード: wget http://graphchi.googlecode.com/files/graphchi_src_v0.1.7b.tar.gz
2. tar zxvf graphchi_src_v0.1.7b.tar.gz
3. cd graphchi_v0.1.7b
4. example_apps/pagerank を作成する
5. bin/example_apps/pagerank ファイル your_graph_file <num_of_iterations>

上記の your_graph_file は、次の 2 つの形式で表すことができます。

1. エッジリストフォーマット:ソース 距離1 値1
2. 隣接リスト形式: src 4 dist1 dist2 dist3 dist4

いくつかの便利なパラメータ、コマンドは次のとおりです。

 bin/myapps/myprogram ファイル GRAPH-FILE config1 configvalue1 config2 configvalue2

以下の設定項目は非常に便利で、実行時にファイルタイプを設定する必要はありません。よく使用されるものは次のとおりです。

1. ファイルの後にグラフデータファイルが続く
2. filetype の後にグラフ ストレージ タイプ edgelist または adjacencylist が続きます。
3. exectthreads 計算するスレッドの数
4. membudget_mb グラフデータの読み込みに使用できるメモリの量

次に例を示します。

 bin/example_apps/pagerank ファイル ../pg/part1_sort.txt 3 ファイルタイプ edgelist execthreads 8 membudget_mb 4096

データとツールを準備して実行を開始します————3,000 万人のランダム サンプルの PageRank 結果を見てみましょう。

これはデータの一部であり、多少簡略化してあります。ある程度の効果も見ることができます。例えば、ファンの質のランキングとして理解することができます。しかし、「機械学習」などの特定の分野であれば、誰がその分野の専門家で、誰が優れているのかを理解できます。これはもう少し便利です。

[注意] Graphchi は現在、2^31 までのノード ID をサポートしています。これより大きいノード ID は計算できません。したがって、計算をするときは、まず準備をしなければなりません。

オリジナルリンク: http://www.cnblogs.com/sing1ee/archive/2012/12/13/2811581.html