신뢰에 비례하여 확률로 노드를 선택합니다

Question

누구든지 항목 선택과 관련된 알고리즘 또는 데이터 구조를 알고 있는데, 일부 첨부 된 값에 비례하여 항목을 선택할 확률이 있습니까? 다시 말해: http://en.wikipedia.org/wiki/sampling_%28statistics%29#probability_proportion_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 매번 여러 샘플을 생성합니다.