概率比例選擇節點信任

有誰知道有關選擇項目，其中有一個概率的算法和數據結構的被選比例的一些附加價值？換句話說：http://en.wikipedia.org/wiki/Sampling_%28statistics%29#Probability_proportional_to_size_sampling 概率比例選擇節點信任

這裏的上下文是一個分散的信譽系統，因此附加值是一個用戶對另一個用戶的信任值。在這個系統中，所有節點或者以完全信任的朋友或者完全不信任的未知者開始。這在大型P2P網絡中本身並不實用，因爲節點數量比您的朋友多得多，您需要知道誰是不是您的直接朋友的大量用戶的信任，所以我已經實施一個動態的信任系統，未知者可以通過朋友之間的朋友關係獲得信任。

每隔一段時間每個用戶將選擇固定數量（對於速度和帶寬的緣故）目標節點的基於中間節點的另一選定固定數量的多少信任他們重新計算他們的信任。選擇目標節點進行重新計算的概率將與其當前的信任成反比，這樣未知數就很有可能變得更爲人知。中間節點將以相同的方式選擇，除了選擇中介的概率與其當前信任成比例。

我已經寫了一個簡單的解決方案自己，但它是相當緩慢的，我想找到一個C++庫來處理這方面我。我當然做了我自己的搜索，我設法找到了我正在挖掘的TRSL。既然它看起來像是一個相當簡單的也許是常見的問題，我希望能有更多的C++庫可供我使用，所以我在問這個問題，希望這裏的某個人能夠對此有所瞭解。

來源

2010-02-06 Stephen Cross

這不是特徵函數算法的用途嗎？ http://en.wikipedia.org/wiki/EigenTrust – 2010-02-06 23:43:54

謝謝，這很有趣，但不完全一樣，我在做什麼 – 2010-02-07 09:15:19

這是我會怎麼做：

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每次生成多個樣本。

來源

2010-02-06 23:59:53

如果所有的OP是後加權選擇，然後隨機從TR1庫已經提供有效創建離散分佈的手段。 – 2010-02-07 00:28:49

要退出第一個循環，需要'unsigned int n'。而且由於你的第二個循環似乎計算了一些類似於累積概率分佈的東西，你不應該正確地將「總和（權重）」和「回合（i）」歸一化？ – 2010-02-07 00:35:13

@darid：我不知道那個庫，你應該在一個單獨的答案中提及！ – 2010-02-07 00:45:50

概率比例選擇節點信任

回答

相關問題