1

次の問題があります。 

Consider a weighted direct graph. 
Each node has a rating and the weighted edges represents 
      the "influence" of a node on its neighbors.
When a node rating change, the neighbors will see their own rating modified (positively or negatively)

1 つのノードで新しい評価を伝播する方法は?
これは標準のアルゴリズムであるべきだと思いますが、どのアルゴリズムですか?

これは一般的な質問ですが、実際には Python を使用しています ;)

ありがとう

[編集]
評価は 0 から 1 の間の単純な float 値です: [0.0,1.0]
確かに収束の問題があります: 伝播を数回の反復に制限したいだけです...

4

1 に答える 1

2

次のような簡単な標準的な方法があります。

let G=(V,E) be the graph
let w:E->R be a weight function such that w(e) = weight of edge e
let A be an array such that A[v] = rating(v)
let n be the required number of iterations

for i from 1 to n (inclusive) do:
    for each vertex v in V:
          A'[v] = calculateNewRating(v,A,w) #use the array A for the old values and w
    A <- A' #assign A with the new values which are stored in A'
return A

ただし、場合によっては、グラフの機能と各ノードの評価の再計算方法に基づいて、より優れたアルゴリズムを使用できる場合があります。例えば：

  1. を仮定すると、ページ ランクrating'(v) = sum(rating(u) * w(u,v)) for each (u,v) in Eの変動が得られます。これは、グラフが強く接続されている場合 (ペロン-フォーベニウスの定理)、主固有ベクトルに収束することが保証されているため、最終的な値の計算は簡単です。
  2. と仮定するとrating'(v) = max{ rating(u) | for each (u,v) in E}、収束も保証され、強連結成分を使用して線形に解くことができます。このスレッドでは、このケースについて説明します。
于 2012-12-14T10:20:14.197 に答える