Skip to content
検索結果に戻る

重み付きPageRank

提唱者
Xing, W. & Ghorbani, A.
年
2004
種類
Centrality measure / ranking algorithm
系統
Network science

この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む

文字サイズ

何をする手法か?

重み付きPageRankは、エッジが異なる強度または頻度を持つネットワークに古典的なPageRankアルゴリズムを拡張したもので、すべてのリンクを平等に扱うのではなく、着信および発信エッジの重みに比例して重要度を分散させます。これにより、接続強度が重要となるあらゆるネットワークにおいて、バイナリPageRankよりも実質的に多くの情報を提供します。

手法の背後にある直感

古典的なPageRankは、すべてのハイパーリンクまたはつながりを同一に扱います。ノードは、弱い接続から得られる名声と同じだけ強い接続から名声を得ます。重み付きPageRankは、各投票をエッジの相対的な重みでスケーリングすることにより、これを修正します。既に重要なノードからの多くの重い着信接続を受けるノードはランキングで最も高くなりますが、多数の弱い接続を持つノードは控えめなままです。これは、相互作用の頻度や取引量などが真の重要性を示す、ほとんどの現実世界のネットワークで影響力が実際にどのように蓄積されるかを反映しています。

歴史学

PageRankは、1998年にBrinとPageによってGoogle検索の基盤として導入され、すべてのハイパーリンクを同等の投票として扱いました。重み付きPageRankは、2004年にXingとGhorbaniによって形式化され、アルゴリズムを拡張して、着信重みと発信重みの分数に基づいて、エッジ重みに比例したランク分布を割り当てました。それ以来、リンク強度が影響力の意味のある代理となる引用分析、バイオインフォマティクス、ソーシャルネットワーク分析、およびレコメンデーションシステム全体に適用されています。

使うべき場面

ネットワークに意味のあるエッジ重みがあり、ノードのグローバルでフローを意識した重要度ランキングが必要な場合に重み付きPageRankを使用します。共引用数を持つ引用ネットワーク、トラフィック量を持つウェブグラフ、発現レベルを持つ生物学的相互作用ネットワーク、相互作用頻度を持つソーシャルネットワーク、および取引量を持つ金融取引ネットワークに最適です。エッジ強度を無視すると影響力の流れを誤って表現する可能性がある場合は、バイナリPageRankよりも重み付きPageRankを優先します。エッジ重みが信頼できない、または任意に割り当てられている場合、ネットワークが非常に疎で重みがほとんどバイナリ(通常のPageRankで十分)である場合、または重み付き次数などの純粋にローカルな中心性尺度が必要な場合は避けてください。フロー方向が概念的に無意味な無向ネットワークには適していません。

限界と注意点

  • エッジ重みが意味のあるものであり、信頼できる測定値であることを要求します。ノイズが多い、または任意のエッジ重みはランキングの質を低下させます。
  • 減衰係数(d)は自由パラメータです。従来の0.85は、ウェブ以外のネットワークでは最適でない場合があります。
  • 選択された重み正規化スキームに敏感です。着信重みと発信重みの組み合わせ方が異なると結果が異なる場合があります。
  • 異なる種類の_エッジを区別しません。単一重みモデルは重要な構造的区別を潰してしまう可能性があります。
  • 効率的な疎行列実装がない場合、非常に大規模で密なネットワークでは収束が遅くなる可能性があります。

出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。

強み

  • 重要度の伝播にエッジ強度を直接組み込み、バイナリPageRankよりも重み付きネットワークでより現実的なランキングを提供します。
  • ローカルな接続性だけでなく、グローバルでネットワーク全体の威信を捉えます。
  • PageRankのテレポートメカニズムを維持し、補正されれば末端ノードや切断されたコンポーネントに対して堅牢です。
  • 効率的な反復計算により大規模ネットワークにスケーリング可能。疎行列演算によりメモリ使用量を管理可能。
  • 容易に解釈可能:高いスコアは、他の高スコアノードからの重い、重み付けされた支持を受けていることを意味します。

応用

  • 重み付き引用および共著ネットワークにおける影響力のある論文または著者の特定。
  • ハイパーリンクのトラフィック量またはクリック率が利用可能な場合のウェブページまたはドキュメントのランキング。
  • 重み付き生物学的相互作用ネットワークにおける主要なタンパク質または遺伝子の検出。
  • 取引量フローによる金融取引ネットワークにおけるノードの優先順位付け。
  • 重み付きソーシャルメディア相互作用グラフにおけるユーザーまたはコンテンツのランキング。
  • アイテムの共起頻度がエッジ重みとして機能するレコメンデーションシステムの構築。

使い方

使い方

1

エッジ強度を反映する数値的重み(相互作用の頻度、取引量、共著数、または類似性スコアなど)を持つグラフとしてネットワークを表します。アルゴリズムはこれらの重みが非負であることを要求します。負の重みは分析前に変換する必要があります。

2

ノードvからノードuへの各有向エッジについて、2つの重み係数を計算します。1つはuへの総着信重みでエッジ重みを正規化する着信重み係数、もう1つはvからの総発信重みで正規化する発信重み係数です。これらの分数により、vのランクがこの特定のエッジを通じてuにどれだけ分散されるかが決まります。

数式
W_{in}(v,u) = \frac{w(v,u)}{\sum_{k \in In(u)} w(k,u)}, \quad W_{out}(v,u) = \frac{w(v,u)}{\sum_{k \in Out(v)} w(v,k)}
3

重み付きPageRankの公式を繰り返し適用します。各ノードのランクは、基本のテレポート項(減衰係数d、通常0.85)に、dを掛けた、すべての着信近傍からのランク(2つの重み係数でスケーリングされた)の合計を加えたものに等しくなります。これにより、ランクは均一ではなく、エッジ強度に比例して分散されます。

数式
WPR(u) = (1-d) + d \sum_{v \in In(u)} WPR(v) \cdot W_{in}(v,u) \cdot W_{out}(v,u)
4

各ノードのスコアの変化が小さな許容誤差(一般的に1e-6)を下回るまで、ランク更新を繰り返します。強連結グラフでは収束が保証されます。末端ノードや孤立したコンポーネントを持つグラフでは、反復処理の前に標準的な末端ノード補正を適用します。

5

スコアが収束したら、すべてのノードを重み付きPageRankスコアの降順に並べ替えます。これらのランクは、ネットワークトポロジーとエッジ強度の両方を考慮した、各ノードのグローバルな構造的重要性_を反映します。

よくある落とし穴

  • スケールをチェックせずに、生の正規化されていないエッジ重みを使用すること。数十のカウントと数百万の値の混合は、ランク伝播を歪めます。
  • 末端ノード(発信エッジのないノード)の処理を忘れること。これは、補正されない場合、ネットワーク全体からランクを奪う可能性があります。
  • デフォルトの減衰係数0.85が普遍的に適切であると仮定すること。引用ネットワークや生物学的ネットワークでは、異なる値がそのドメインをよりよく反映する場合があります。
  • 重み付きPageRankスコアを相対的なランキングではなく絶対的な確率として解釈すること。異なる実行間で安定しているのは順序のみです。
  • 正規化なしで、異なるサイズのネットワーク間の重み付きPageRankスコアを比較すること。

よくある質問

重み付きPageRankは標準的なPageRankとどう異なりますか?

標準的なPageRankは、エッジの強度に関係なく、ノードのランクをすべての発信近傍に均等に分散します。重み付きPageRankは、各エッジの相対的な着信重みと発信重みでこの分散をスケーリングするため、より強い接続は比例してより多くのランクを運びます。

どのような減衰係数を使用すべきですか?

従来の_値は0.85で、ランダムサーフィンに関するウェブグラフの仮定から導き出されます。ソーシャル、生物学的、または引用ネットワークの場合、0.5から0.9の間の値が文献で探求されています。減衰値の範囲に対する感度分析が推奨されます。

重み付きPageRankは無向ネットワークに適用できますか?

はい、各無向エッジを同じ重みを持つ有向エッジのペアとして表現することで可能です。アルゴリズムは対称的な着信重みと発信重み係数を生成し、エッジ強度を尊重する_式に_簡略化されます。

ゼロ重みエッジをどのように扱いますか?

ゼロ重みのエッジはランク伝播に寄与しないため、分析前に削除できます。ゼロ重みが構造的に意味がある場合(欠如対欠損データ)、削除する前にその区別を明確に文書化してください。

重み付きPageRankは重み付き次数中心性よりも優れていますか?

研究の質問によります。重み付き次数中心性は直接接続のみを捉えますが、重み付きPageRankはネットワーク全体に伝播するグローバルな威信を捉えます。ローカルな影響力には重み付き次数を、ネットワーク全体の重要度には重み付きPageRankを使用してください。

関連する手法

参考文献

  1. Xing, W., & Ghorbani, A. (2004). Weighted PageRank algorithm. Proceedings of the Second Annual Conference on Communication Networks and Services Research (CNSR '04), pp. 305–314. IEEE.

    DOI 文献を開く
    コピーしました。
  2. PageRank. Wikipedia.

    出版物の文献を開く
    コピーしました。