Auswählen von Knoten mit einer Wahrscheinlichkeit proportional zu vertrauen

Question

Kennt jemand einen Algorithmus oder Datenstruktur beziehen Elemente der Auswahl, mit einer Wahrscheinlichkeit von ihnen ist proportional zu einem gewissen angebracht Wert ausgewählt? Mit anderen Worten: http://en.wikipedia.org/wiki/Sampling_% 28statistics% 29 # Probability_proportional_to_size_sampling

Der Kontext hier ist ein dezentrales Ruf-System und der angeschlossene Wert ist daher der Wert des Vertrauens einem Benutzer in einer anderen hat. In diesem System werden alle Knoten entweder als Freunde beginnen, die vollständig vertrauenswürdig oder Unbekannten sind, die vollständig nicht vertrauenswürdig sind. Dies ist für sich allein in einem großen P2P-Netzwerk nicht sinnvoll, weil es viel mehr Knoten als Sie Freunde haben, und Sie müssen wissen, wer in der großen Gruppe von Benutzern zu vertrauen, die nicht Ihre direkte Freunde sind, also habe ich umgesetzt ein dynamisches Vertrauenssystem, bei dem Unbekannten Vertrauen über Freund-of-a-friend Beziehungen gewinnen.

Jeder so oft jeder Benutzer eine feste Anzahl wählen (aus Gründen der Geschwindigkeit und Bandbreite) von Zielknoten ihr Vertrauen neu zu berechnen, basierend auf wie viel andere ausgewählte feste Anzahl von Zwischenknoten ihnen vertrauen. Die Wahrscheinlichkeit für einen Zielknoten für die Neuberechnung der Auswahl wird in umgekehrtem Verhältnis zu seinem aktuellen Vertrauen proportional sein, so dass Unbekannte eine gute Chance, immer besser kennen. Die Zwischenknoten werden in der gleichen Art und Weise gewählt werden, mit der Ausnahme, dass die Wahrscheinlichkeit der Auswahl eines Vermittlers ist proportional zu seinen aktuellen Vertrauen.

Ich habe eine einfache Lösung selbst geschrieben, aber es ist ziemlich langsam, und ich möchte eine C ++ Bibliothek finden, diesen Aspekt für mich zu handhaben. Ich habe natürlich meine eigene Suche gemacht und ich schaffte es TRSL zu finden, die ich durch im Moment bin zu graben. Da es wie ein ziemlich einfaches und vielleicht weit verbreitetes Problem scheint, würde ich erwarten, dass es viele weiteren C ++ Bibliotheken, die ich für diese verwenden könnte, so dass ich diese Frage in der Hoffnung, dass hier jemand etwas Licht in diesen Schuppen kann.

Answer 1

Das ist, was ich tun würde:

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

Sie können die zweite Schleife so oft natürlich wiederholen, wie Sie wollen, eine neue r jedes Mal wählen, um mehrere Proben zu erzeugen.