选择概率与信任成比例的节点 [英] Selecting nodes with probability proportional to trust

问题描述

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

Does anyone know of an algorithm or data structure relating to selecting items, with a probability of them being selected proportional to some attached value? In other words: http://en.wikipedia.org/wiki/Sampling_%28statistics%29#Probability_proportional_to_size_sampling

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

The context here is a decentralized reputation system and the attached value is therefore the value of trust one user has in another. In this system all nodes either start as friends which are completely trusted or unknowns which are completely untrusted. This isn't useful by itself in a large P2P network because there will be many more nodes than you have friends and you need to know who to trust in the large group of users that aren't your direct friends, so I've implemented a dynamic trust system in which unknowns can gain trust via friend-of-a-friend relationships.

每个用户经常选择一个固定数字速度和带宽），以基于另一选定的固定数量的中间节点对它们的信任来重新计算它们的信任。选择用于重新计算的目标节点的概率将与其当前信任成反比，使得未知数具有变得更好已知的良好机会。中间节点将以相同的方式选择，除了中间选择的概率与其当前信任成比例。

Every so often each user will select a fixed number (for the sake of speed and bandwidth) of target nodes to recalculate their trust based on how much another selected fixed number of intermediate nodes trust them. The probability of selecting a target node for recalculation will be inversely proportional to its current trust so that unknowns have a good chance of becoming better known. The intermediate nodes will be selected in the same way, except that the probability of selection of an intermediary is proportional to its current trust.

我写了一个简单的解决方案我自己，但它是相当慢，我想找到一个C ++库来处理这方面为我。我当然做了我自己的搜索，我成功地找到了TRSL，我现在正在挖掘。因为它看起来像一个相当简单也许是常见的问题，我希望有更多的C ++库我可以用于这，所以我问这个问题，希望有人在这里可以阐明这一点。 p>

I've written up a simple solution myself but it is rather slow and I'd like to find a C++ library to handle this aspect for me. I have of course done my own search and I managed to find TRSL which I'm digging through right now. Since it seems like a fairly simple and perhaps common problem, I would expect there to be many more C++ libraries I could use for this, so I'm asking this question in the hope that someone here can shed some light on this.

推荐答案

这是我会做的：

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

You can of course repeat the second loop as many times as you want, choosing a new r each time, to generate multiple samples.

这篇关于选择概率与信任成比例的节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！