选择概率与信任成正比的节点

Question

有谁知道与选择项目相关的算法或数据结构，它们被选择的概率与某些附加值成比例？换句话说： http://en.wikipedia.org/wiki/Sampling_%28statistics%29#Probability_proportional_to_size_sampling

这里的背景是一个去中心化的声誉系统，因此附加价值是一个用户对另一个用户的信任值。在这个系统中，所有节点要么以完全信任的朋友身份开始，要么以完全不信任的未知身份开始。这在大型 P2P 网络中本身并没有什么用处，因为节点数量比你的朋友多得多，并且你需要知道在不是你直接朋友的一大群用户中该信任谁，所以我实现了一个动态的信任系统，未知者可以通过朋友的朋友关系获得信任。

每个用户经常会选择固定数量（为了速度和带宽）的目标节点，根据另一个选定的固定数量的中间节点对他们的信任程度来重新计算他​​们的信任。选择目标节点进行重新计算的概率将与其当前的信任度成反比，因此未知的节点有很大的机会变得更加为人所知。中间节点将以相同的方式被选择，只不过中间节点被选择的概率与其当前的信任成正比。

我自己编写了一个简单的解决方案，但它相当慢，我想找到一个 C++ 库来为我处理这方面的问题。当然，我已经完成了自己的搜索，并设法找到了我现在正在挖掘的 TRSL。因为这似乎是一个相当简单且可能是常见的问题，所以我希望有更多的 C++ 库可以用于此目的，所以我问这个问题是希望这里有人能对此有所了解。

Answer 1

这就是我要做的：

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 每次，生成多个样本。