Sélectionner des noeuds avec une probabilité proportionnelle à la confiance

Question

Quelqu'un sait-il d'une structure de l'algorithme ou des données relatives à la sélection des éléments, avec une probabilité d'entre eux étant choisi proportionnel à une valeur fixée? En d'autres termes: http://en.wikipedia.org/wiki/Sampling_% 28statistics% 29 # Probability_proportional_to_size_sampling

Le contexte ici est un système de réputation décentralisée et la valeur attachée est donc la valeur de confiance d'un utilisateur dans un autre. Dans ce système, tous les nœuds soit commencent comme des amis qui sont tout à fait confiance ou inconnues qui sont complètement non fiables. Ce n'est pas utile par lui-même dans un grand réseau P2P, car il y aura beaucoup plus de nœuds que vous avez des amis et que vous devez savoir à qui faire confiance dans le grand groupe d'utilisateurs qui ne sont pas vos amis directs, donc je l'ai mis en œuvre un système de confiance dynamique dans lequel des inconnus peuvent gagner la confiance par ami-de-un-ami des relations.

Chaque si souvent chaque utilisateur choisira un nombre fixe (à cause de la vitesse et la bande passante) des noeuds cibles à recalculer leur confiance basée sur combien un nombre fixe choisi de noeuds intermédiaires confiance en eux. La probabilité de sélection d'un noeud cible pour recalcul sera inversement proportionnelle à sa confiance actuelle afin que les inconnues ont une bonne chance de devenir plus connu. Les noeuds intermédiaires seront choisis de la même manière, sauf que la probabilité de sélection d'un intermédiaire est proportionnelle à sa confiance actuelle.

J'ai écrit une solution simple moi-même, mais il est assez lent et je voudrais trouver une bibliothèque C ++ pour gérer cet aspect pour moi. J'ai bien sûr fait ma propre recherche et je réussi à trouver TRSL que je suis creuser en ce moment. Comme il semble un problème assez simple et peut-être commun, je me attends d'être beaucoup plus bibliothèques C ++ que je pourrais utiliser pour cela, donc je pose cette question dans l'espoir que quelqu'un ici peut faire la lumière sur ce point.

Answer 1

Voici ce que je ferais:

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];
    }
}

Vous pouvez bien sûr répéter la deuxième boucle autant de fois que vous le souhaitez, le choix d'un nouveau r chaque fois, pour générer plusieurs échantillons.