La selezione di nodi con probabilità proporzionale alla fiducia

Question

Qualcuno sa di una struttura di algoritmo o dati relativi a selezione delle voci, con una probabilità di loro che sono selezionati proporzionale a un valore fissato? In altre parole: http://en.wikipedia.org/wiki/Sampling_% 28statistics% 29 # Probability_proportional_to_size_sampling

Il contesto: ecco un sistema di reputazione decentralizzato e il valore attribuito è quindi il valore della fiducia un utente ha in un altro. In questo sistema tutti i nodi sia partono come amici che sono completamente attendibili o sconosciuti che sono completamente attendibile. Questo non è utile di per sé in una grande rete P2P, perché ci saranno molti più nodi di quello che hai amici e avete bisogno di sapere di chi fidarsi nel grande gruppo di utenti che non sono i tuoi amici diretti, così ho implementato un sistema dinamico in cui la fiducia incognite può guadagnare la fiducia attraverso relazioni amico-di-un-amico.

Ogni tanto ogni utente selezionerà un numero fisso (per il bene della velocità e larghezza di banda) di nodi di destinazione per ricalcolare la loro fiducia sulla base di quanto un altro numero fisso selezionato di nodi intermedi loro fidarsi. La probabilità di selezione di un nodo di destinazione per il ricalcolo sarà inversamente proporzionale alla sua fiducia corrente in modo che incognite hanno una buona probabilità di diventare più conosciuto. I nodi intermedi saranno selezionati nello stesso modo, tranne che la probabilità di selezione di un intermediario è proporzionale alla sua attendibilità corrente.

Ho scritto una soluzione semplice me stesso, ma è piuttosto lento e mi piacerebbe trovare una libreria C ++ per gestire questo aspetto per me. Ho ovviamente fatto la mia ricerca e sono riuscito a trovare TRSL che sto scavando attraversando in questo momento. Dal momento che sembra un problema abbastanza semplice e forse comune, mi aspetto che ci sia molte biblioteche più C ++ ho potuto utilizzare per questo, quindi sto facendo questa domanda, nella speranza che qualcuno qui può far luce su questo.

Answer 1

Questo è quello che farei:

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

È possibile ovviamente ripetere il secondo ciclo tutte le volte che si desidera, la scelta di un nuovo r di volta in volta, per generare campioni multipli.