概率比例选择节点信任

有谁知道有关选择项目，其中有一个概率的算法和数据结构的被选比例的一些附加价值？换句话说：http://en.wikipedia.org/wiki/Sampling_%28statistics%29#Probability_proportional_to_size_sampling 概率比例选择节点信任

这里的上下文是一个分散的信誉系统，因此附加值是一个用户对另一个用户的信任值。在这个系统中，所有节点或者以完全信任的朋友或者完全不信任的未知者开始。这在大型P2P网络中本身并不实用，因为节点数量比您的朋友多得多，您需要知道谁是不是您的直接朋友的大量用户的信任，所以我已经实施一个动态的信任系统，未知者可以通过朋友之间的朋友关系获得信任。

每隔一段时间每个用户将选择固定数量（对于速度和带宽的缘故）目标节点的基于中间节点的另一选定固定数量的多少信任他们重新计算他们的信任。选择目标节点进行重新计算的概率将与其当前的信任成反比，这样未知数就很有可能变得更为人知。中间节点将以相同的方式选择，除了选择中介的概率与其当前信任成比例。

我已经写了一个简单的解决方案自己，但它是相当缓慢的，我想找到一个C++库来处理这方面我。我当然做了我自己的搜索，我设法找到了我正在挖掘的TRSL。既然它看起来像是一个相当简单的也许是常见的问题，我希望能有更多的C++库可供我使用，所以我在问这个问题，希望这里的某个人能够对此有所了解。

来源

2010-02-06 Stephen Cross

这不是特征函数算法的用途吗？ http://en.wikipedia.org/wiki/EigenTrust – 2010-02-06 23:43:54

谢谢，这很有趣，但不完全一样，我在做什么 – 2010-02-07 09:15:19

这是我会怎么做：

int select(double *weights, int n) { 
    // This step only necessary if weights can be arbitrary 
    // (we know total = 1.0 for probabilities) 
    double total = 0; 
    for (int i = 0; i < n; ++i) { 
     total += weights[i]; 
    } 

    // Cast RAND_MAX to avoid overflow 
    double r = (double) rand() * total/((double) RAND_MAX + 1); 
    total = 0; 
    for (int i = 0; i < n; ++i) { 
     // Guaranteed to fire before loop exit 
     if (total <= r && total + weights[i] > r) { 
      return i; 
     } 

     total += weights[i]; 
    } 
}

当然，你可以重复多次，只要你想在第二循环中，选择一个新r每次生成多个样本。

来源

2010-02-06 23:59:53

如果所有的OP是后加权选择，然后随机从TR1库已经提供有效创建离散分布的手段。 – 2010-02-07 00:28:49

要退出第一个循环，需要'unsigned int n'。而且由于你的第二个循环似乎计算了一些类似于累积概率分布的东西，你不应该正确地将“总和（权重）”和“回合（i）”归一化？ – 2010-02-07 00:35:13

@darid：我不知道那个库，你应该在一个单独的答案中提及！ – 2010-02-07 00:45:50

概率比例选择节点信任

回答

相关问题