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)

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

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

谢谢

[编辑]
评级是 0 到 1 之间的简单浮点值：[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，你得到一个Page Rank的变体，如果图是强连通的（ Perron-Forbenius 定理），它保证收敛到主特征向量，所以计算最终值很简单。
  2. 假设rating'(v) = max{ rating(u) | for each (u,v) in E}，那么它也保证收敛并且可以使用强连通分量线性求解。这个线程讨论了这个案例。
于 2012-12-14T10:20:14.197 回答