web - Pagerank: 自分自身を指すノード

Question

それ自体を指しているノードとダングリング ノードの PageRank 値を計算したい場合、ダングリング ノードを削除すると、初期 (および最終) の PageRank は 1 になりますか?

Answer 1

元のページ ランク アルゴリズムでは、自己ループは許可されません。ただし、自己ループを明示的に追加するか、リンク構造に存在するものを考慮するいくつかのバリエーションがあります。

したがって、ここには 2 つのノードのみを含む完全な Web (またはクロールした Web) があります。A には自己ループと B への別のリンクがあります。B にはリンクがありません。これにより、最終的な PR ベクトルの値が 0 になります。MMDS book (Ullman) は、(1) デッドエンドを再帰的に削除する、または (2) 課税パラメータを追加する、いくつかのオプションを提案しています。 あなたの例では、2 番目のノードを削除できます。図 ii を参照してください。これで、自己ループを持つノードが 1 つだけ残ります。削除されたノードのスコアはまだ 0 ではないことに注意してください。たとえば、実装で自己ループがインリンクとしてカウントされると仮定すると、A の PR スコアは 1 になります。B には、それに寄与する 1 つのサクセサ (A) があります。A には 2 つのアウトリンクがあります (ループの仮定と B へのリンク)。図 iii を参照してください。最終的に、B の PR は 0.5 になります。

PageRank の合計が 1 を超え、ランダムなサーファーの分布を表していないことに注意してください。それでも、それらはページの相対的な重要性を適切に見積もっています。*Ullman MMDS、172-173 ページ、9-10 ページの pdf。

参考図書 : http://infolab.stanford.edu/~ullman/mmds/ch5.pdf