Өзіндік сенім - EigenTrust

Өзіндік сенім алгоритм Бұл беделді басқару үшін алгоритм пиринг жүйесі дамыған желілер Сеп Камвар, Марио Шлоссер және Гектор Гарсия-Молина.^[1] Алгоритм желідегі әрбір теңдестірушілердің жүктеу тарихына негізделген бірегей ғаламдық сенімділік мәнін ұсынады және осылайша аутентификацияланған файлдардың санын азайтуға бағытталған P2P желі. Google Scholar-қа сәйкес шамамен 3853 басқа мақалалар келтірілген.^[2]

Шолу

Пиринг жүйесі бүгінгі таңда қол жетімді жүйелер (мысалы Гнутелла ) ашық, көбінесе жасырын және жауапсыз. Демек, зиянды ниеті бар пайдаланушы бір деңгейлі желіге шынайы емес, бүлінген немесе зиянды болуы мүмкін ресурстарды енгізе алады (Зиянды бағдарлама ). Бұл қазіргі тең-теңімен жүйенің сенімділігі туралы нашар көрінеді. Бастап зерттеу тобы Стэнфорд беделді басқару жүйесін ұсынады, мұнда жүйеде әр теңдестірулер жүктеу тарихына негізделген бірегей жаһандық сенім мәніне ие болады. Ресурстар сұрайтын кез-келген теңдестірімнің сенімді мәніне қол жеткізе алады және сенімсіз құрдастардан файлдарды жүктеуден аулақ болады.

Алгоритм

Eigentrust алгоритмі транзитивті сенім ұғымына негізделген: Егер құрдас болса мен кез-келген құрдасына сенеді j, бұл сондай-ақ сенетін құрдастарына сенеді j. Әрқайсысы мен жергілікті сенім мәнін есептейді с_иж оны қанағаттанарлық немесе қанағаттанарлықсыз транзакциялар негізінде шынайы немесе жалған жүктеулермен қамтамасыз еткен барлық құрдастар үшін.

${displaystyle s_ {ij} = оператор атауы {sat} (i, j) -оператордың аты {unsat} (i, j)}$

қайда отырды (мен, j) бір-бірімен қанағаттанарлық жауаптардың санына жатады мен құрдасынан алды j, және қанықпаған (мен, j) теңдессіз жауаптардың санына жатады мен құрдасынан алды j.

Жергілікті мән зиянды құрдастардың зиянды құрдастармен келісу үшін ерікті түрде жоғары жергілікті сенім мәндерін және жақсы құрдастармен ерікті түрде төмен жергілікті сенім мәндерін беруіне жол бермеу үшін қалыпқа келтірілген. Нормаланған жергілікті сенім мәні c_иж сол кезде

${displaystyle c_ {ij} = {frac {max (s_ {ij}, 0)} {sum _ {j} max (s_ {ij}, 0)}}}$

Жергілікті сенім мәндері орталық желіде немесе бүкіл желі үшін сенім векторын құру үшін үлестірілген тәртіпте жинақталған. Өтпелі сенім идеясына негізделген, құрдас мен басқа құрдастарынан құрдасының сенімділігі туралы есеп беруін сұрар еді к және сенімді құрдасының осы құрдастарының жауаптарын өлшеу мен олардағы орындар.

${displaystyle t_ {ik} = sum _ {j} c_ {ij} c_ {jk}}$

Егер пайдаланушы білетін деп ойласақ c_иж а түрінде бүкіл желі үшін мәндер матрица C, содан кейін сенімді вектор ${displaystyle {ar {t}} _ {i}}$ үшін сенім мәнін анықтайды ${displaystyle t_ {ik}}$ арқылы беріледі

${displaystyle {ar {t}} _ {i} = C ^ {T} {ar {c}} _ {i}.,}$

Жоғарыда көрсетілген теңдеуде, егер С апериодты және қатты байланысты деп қабылданса, С матрицасының қуаттары белгілі бір сәтте тұрақты мәнге ауысады.

${displaystyle {ar {t}} = (C ^ {T}) ^ {x} {ar {c}} _ {i}.,}$

Бұл үлкен мәнге ұқсайды х, сенім векторы ${displaystyle {ar {t}} _ {i}}$ желінің барлық құрдастары үшін бірдей векторға жақындайды. Вектор ${displaystyle {ar {t}} _ {i}}$ сол жақтағы директор ретінде белгілі меншікті вектор матрицаның C. Бастап біз де атап өтеміз ${displaystyle {ar {t}} _ {i}}$ желідегі барлық түйіндер үшін бірдей, ол ғаламдық сенім мәнін білдіреді.

Жоғарыда келтірілген нәтижелер негізінде есептеудің қарапайым орталықтандырылған алгоритмін жазуға болады. Матрицада бүкіл желі үшін барлық жергілікті сенім мәндері қол жетімді және бар деп ойлаймыз C. Сондай-ақ, егер жоғарыда көрсетілген теңдеу бір-біріне жақындаса, біз бастапқы векторды алмастыра аламыз ${displaystyle {ar {c}} _ {i}}$ вектор бойынша ${displaystyle {ar {e}}}$ бұл m-векторы, барлық m қатарластары бойынша ықтималдықтың біркелкі үлестірілуін білдіреді. Негізгі EigenTrust алгоритмі төменде көрсетілген:

${displaystyle {ar {t}} _ {0} = {ar {e}};}$

қайталау

${displaystyle {ar {t}} ^ {(k + 1)} = C ^ {T} {ar {t}} ^ {(k)};}$

${displaystyle {delta} = | t ^ {(k + 1)} - t ^ {(k)} |;}$

дейін ${displaystyle {delta}$

Сондай-ақ қараңыз

• Марков тізбегі
• Меншікті мәндер және меншікті векторлар математика мен физикада
• Айген (C ++ кітапханасы), матрицалық және сызықтық алгебра операцияларына арналған компьютерлік бағдарламалау кітапханасы

Әдебиеттер тізімі