اختيار العقد مع احتمال تتناسب مع الثقة

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 في كل مرة، لتوليد عينات متعددة.