python - 在图形结构中传播评级

Question

我有以下问题:

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)

如何在一个节点上传播一个新的评级？
我认为这应该是一个标准算法，但是哪一个？

这是一个一般性问题，但实际上我使用的是 Python ;)

谢谢

[编辑]
评级是一个介于 0 到 1 之间的简单浮点值:[0.0,1.0]
肯定存在收敛问题:我只想将传播限制为几次迭代...

Answer 1

有一个简单的标准方法如下:

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. 假设 E 中的每个 (u,v) rating'(v) = sum(rating(u) * w(u,v))，您会得到 Page Rank 的变体，如果图是强连通的(Perron-Forbenius theorem)，它保证收敛到主特征向量，因此计算最终值很简单。
2. 假设 rating'(v) = max{ rating(u) |对于 E} 中的每个 (u,v)，那么它也可以保证收敛并且可以使用强连通分量线性求解。 This thread讨论这个案例。