Выбор узлов с вероятностью, пропорциональной доверию - PullRequest
Новая
       13

Выбор узлов с вероятностью, пропорциональной доверию

2 голосов
/ 07 февраля 2010

Кто-нибудь знает алгоритм или структуру данных, относящихся к выбору элементов, с вероятностью их выбора пропорционально некоторому приложенному значению? Другими словами: http://en.wikipedia.org/wiki/Sampling_%28statistics%29#Probability_proportional_to_size_sampling

Контекст здесь представляет собой децентрализованную систему репутации, и поэтому приложенное значение - это значение доверия, которое один пользователь оказывает другому. В этой системе все узлы либо начинаются как друзья, которым полностью доверяют, либо неизвестные, которым полностью не доверяют. Это само по себе бесполезно в большой сети P2P, потому что будет гораздо больше узлов, чем у вас есть друзья, и вам нужно знать, кому можно доверять в большой группе пользователей, которые не являются вашими прямыми друзьями, поэтому я реализовал динамическая система доверия, в которой неизвестные могут завоевать доверие посредством отношений друг-друг.

Время от времени каждый пользователь выбирает фиксированное число (ради скорости и пропускной способности) целевых узлов, чтобы пересчитать их доверие на основе того, насколько доверяет им другое выбранное фиксированное количество промежуточных узлов. Вероятность выбора целевого узла для пересчета будет обратно пропорциональна его текущему доверию, так что неизвестные имеют хороший шанс стать более известным. Промежуточные узлы будут выбраны таким же образом, за исключением того, что вероятность выбора посредника пропорциональна его текущему доверию.

Я сам написал простое решение, но оно довольно медленное, и я хотел бы найти библиотеку C ++, чтобы справиться с этим аспектом для меня. Конечно, я сделал свой собственный поиск, и мне удалось найти TRSL, который я сейчас копаю. Поскольку это кажется довольно простой и, возможно, распространенной проблемой, я ожидаю, что для этого будет гораздо больше библиотек C ++, поэтому я задаю этот вопрос в надежде, что кто-то здесь сможет пролить свет на это.

1 Ответ

3 голосов
/ 07 февраля 2010

Вот что я бы сделал: 

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, чтобы сгенерировать несколько выборок.

...