李 方，付曉東，2，岳 昆，劉 驪，劉利軍，馮 勇

1(昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院，昆明 650500) 2(昆明理工大學(xué) 云南省計(jì)算機(jī)技術(shù)應(yīng)用重點(diǎn)實(shí)驗(yàn)室，昆明 650500) 3(云南大學(xué) 信息學(xué)院，昆明 650091)

1 引 言

隨著互聯(lián)網(wǎng)應(yīng)用的飛速發(fā)展與進(jìn)步，傳統(tǒng)商業(yè)環(huán)境發(fā)生了巨大的改變，以互聯(lián)網(wǎng)為媒介向用戶提供在線服務(wù)在企業(yè)中得到快速普及，成為企業(yè)運(yùn)行的發(fā)展趨勢(shì)和必然選擇[1].在線服務(wù)是指利用互聯(lián)網(wǎng)技術(shù)，向用戶提供線上服務(wù)的方式.在線服務(wù)給人們的日常工作生活帶來(lái)了巨大的便利，利用這種技術(shù)，用戶可以進(jìn)行數(shù)據(jù)共享、完成信息交換、購(gòu)買商品和服務(wù)等[2].用戶與在線服務(wù)進(jìn)行交互后，依照主觀感受對(duì)服務(wù)做出評(píng)價(jià)，表達(dá)他們的偏好及滿意程度[3].通過(guò)聚合用戶群體的偏好信息獲得服務(wù)信譽(yù)，可幫助用戶群體在具有相似功能的在線服務(wù)中選擇出滿足用戶需求的服務(wù).

在線服務(wù)信譽(yù)是用戶對(duì)在線服務(wù)的信任程度，對(duì)于在線服務(wù)選擇起著重要的作用[4].客觀、有效的在線服務(wù)信譽(yù)度量方法在幫助用戶選擇優(yōu)質(zhì)的在線服務(wù)和提升在線服務(wù)質(zhì)量方面具有重要的應(yīng)用價(jià)值[5].為了提高自身影響力或者降低對(duì)手影響力，惡意用戶或者在線服務(wù)提供商可能操縱、攻擊信譽(yù)系統(tǒng)，扭曲在線服務(wù)的信譽(yù)，致使用戶利用這種信譽(yù)進(jìn)行服務(wù)選擇時(shí)會(huì)產(chǎn)生不客觀的結(jié)果，從而使用戶面臨無(wú)法選擇到滿足需求服務(wù)的風(fēng)險(xiǎn)[6].惡意用戶對(duì)信譽(yù)系統(tǒng)的攻擊通常具有欺騙性、合謀性或戰(zhàn)略性，誤導(dǎo)買家與服務(wù)進(jìn)行交易[7，8].這其中有一類特殊的群體，就是信譽(yù)系統(tǒng)的管理者，他們掌握了普通用戶的偏好，為獲取不當(dāng)利益，可以通過(guò)刪除或者增加用戶、服務(wù)以使特定服務(wù)成為信譽(yù)最高的服務(wù).

現(xiàn)有工作重點(diǎn)關(guān)注普通用戶或者在線服務(wù)提供者對(duì)信譽(yù)的操縱，而缺少通過(guò)技術(shù)手段防范信譽(yù)系統(tǒng)管理者對(duì)服務(wù)信譽(yù)進(jìn)行控制的措施.為此，本文提出利用Fallback的在線服務(wù)信譽(yù)防控制機(jī)制.該機(jī)制通過(guò)提高控制用戶偏好策略的計(jì)算復(fù)雜性，將在線服務(wù)信譽(yù)控制建模為判斷某一服務(wù)是否能通過(guò)控制成為信譽(yù)最高的服務(wù)的問(wèn)題.理論證明利用Fallback的在線服務(wù)信譽(yù)控制的問(wèn)題是固定參數(shù)不可解的，即利用Fallback的用戶偏好控制問(wèn)題是具有抵抗力的(Resistance)[9]，從而利用Fallback的信譽(yù)系統(tǒng)難以被控制.

2 相關(guān)工作

隨著電子商務(wù)的快速發(fā)展，用戶獲取線上服務(wù)變得越來(lái)越方便，但信用缺失問(wèn)題也越來(lái)越嚴(yán)重.雖然電子商務(wù)系統(tǒng)設(shè)置了信譽(yù)排名和推薦機(jī)制，為用戶在選擇誠(chéng)信服務(wù)方面提供輔助的決策支持.然而，一些惡意用戶、在線服務(wù)提供商不斷采取欺騙、偽裝、漂白、共謀、歧視等策略控制用戶偏好，進(jìn)而誤導(dǎo)用戶進(jìn)行服務(wù)選擇[10，11].

總結(jié)現(xiàn)有的在線服務(wù)信譽(yù)系統(tǒng)防控制機(jī)制，主要包括4方面：減輕通過(guò)虛假信息進(jìn)行操縱的影響；識(shí)別惡意用戶，對(duì)他們做出懲罰或者進(jìn)行隔離；激勵(lì)用戶表達(dá)真實(shí)偏好；增加控制者的控制成本(成本可能是金錢、時(shí)間等).

減輕通過(guò)虛假信息進(jìn)行操縱的影響來(lái)防控制比較常見(jiàn).Anupama Aggarwal建立了檢測(cè)用戶對(duì)信譽(yù)系統(tǒng)操縱行為的機(jī)制，利用可疑用戶的時(shí)間行為和網(wǎng)絡(luò)特征，可以從合法用戶中檢測(cè)出虛假操縱行為，減輕操縱信譽(yù)對(duì)在線社交網(wǎng)絡(luò)的影響[12].Jaehong Ahn等提出從存儲(chǔ)在基于區(qū)塊鏈的在線支付系統(tǒng)交易的原始評(píng)價(jià)中獲取信譽(yù)[13]，防止信息被惡意操縱.

識(shí)別惡意用戶，對(duì)他們做出懲罰或隔離方面，Xin Wang等基于印象理論，提出了一種由最近鄰搜索算法及分類算法組成的無(wú)監(jiān)督策略，隔離誠(chéng)實(shí)和不誠(chéng)實(shí)的用戶及服務(wù)[14].Nitin Kumar Saini等提出了一種針對(duì)共謀檢測(cè)的反應(yīng)性解決方案，并針對(duì)檢測(cè)到的惡意用戶提出了降低其聲譽(yù)的懲罰策略[15]；馬述忠等基于網(wǎng)絡(luò)店鋪銷售假冒行為，構(gòu)建了不完全信息的動(dòng)態(tài)博弈模型，考察了懲罰機(jī)制和信譽(yù)機(jī)制的治理效果[16].

激勵(lì)用戶表達(dá)真實(shí)偏好方面，Junsheng Chang等提出了一種基于政策的公平差別化服務(wù)激勵(lì)機(jī)制，定義了參與水平和推薦可信度這兩個(gè)參數(shù)，識(shí)別了信譽(yù)系統(tǒng)中用戶的行為特征[17].基于上述兩個(gè)參數(shù)，還提出了一個(gè)簡(jiǎn)單而有效的信譽(yù)信息交換協(xié)議，以激勵(lì)用戶誠(chéng)實(shí)的表達(dá)真實(shí)偏好；Ali Ghaffarinejad等針對(duì)面向服務(wù)的環(huán)境，提出了一種基于多個(gè)特殊信譽(yù)中心的分布式信譽(yù)機(jī)制[18].該機(jī)制具有抗共謀的能力，并激勵(lì)企業(yè)資信管理人員嘗試全面收集信譽(yù)信息并如實(shí)報(bào)告；Yingtao Xu等基于信譽(yù)評(píng)價(jià)的動(dòng)態(tài)特性，提出了一種基于最優(yōu)控制問(wèn)題的在線信譽(yù)動(dòng)態(tài)反饋激勵(lì)模型[19].

增加控制者的控制成本方面，Kevin Hoffman等提出的抗Sybil攻擊的解決方案分為集中式和分布式兩種[20].在集中式方法中，中央權(quán)威機(jī)構(gòu)發(fā)出和驗(yàn)證每個(gè)實(shí)體唯一的憑證.為了增加獲得多個(gè)身份的成本，中央權(quán)威可能需要為每個(gè)身份支付貨幣或計(jì)算費(fèi)用；Bhupender Kumar等通過(guò)設(shè)置身份節(jié)點(diǎn)在網(wǎng)絡(luò)中保持可信的全局信任閾值，增加控制成本來(lái)阻止攻擊[21].

上述研究中對(duì)于信譽(yù)系統(tǒng)的防控制對(duì)象都是使用信譽(yù)系統(tǒng)的普通用戶或在線服務(wù)提供者.然而對(duì)信譽(yù)系統(tǒng)內(nèi)部的管理者來(lái)說(shuō)，他們更容易掌握用戶信息，可以根據(jù)掌握到的用戶偏好對(duì)當(dāng)前的用戶、在線服務(wù)進(jìn)行增加、刪除等操作對(duì)服務(wù)信譽(yù)進(jìn)行有針對(duì)性的操縱，使信譽(yù)系統(tǒng)面臨被其管理者操縱的道德風(fēng)險(xiǎn).為此，本文考慮了掌握所有用戶偏好的信譽(yù)系統(tǒng)管理者的易控制性，利用了社會(huì)選擇理論中的方法，提出了一種利用Fallback的在線服務(wù)信譽(yù)防控制機(jī)制.最后通過(guò)理論分析和實(shí)驗(yàn)驗(yàn)證了方法的合理性和有效性.

3 問(wèn)題描述

3.1 問(wèn)題定義

對(duì)信譽(yù)系統(tǒng)的控制可分為構(gòu)造性控制和破壞性控制，并且兩種控制類型都通過(guò)增加和刪除用戶或服務(wù)進(jìn)行控制.構(gòu)造性控制作為一種最經(jīng)典且最常見(jiàn)的控制[22]，不失一般性，本文重點(diǎn)闡述構(gòu)造性控制問(wèn)題.為了更好地闡述利用Fallback的在線服務(wù)信譽(yù)防控制的問(wèn)題，本文首先給出相關(guān)定義如下：

定義1.集合U={ui|i=1，2，…，n}為所有用戶集合；集合S={sj|j=1，2，…，m}為用戶產(chǎn)生交互的所有服務(wù)集合.其中，n為用戶的個(gè)數(shù)，m為在線服務(wù)的個(gè)數(shù).

定義2.評(píng)分向量ri=(ri1，ri2，…rij，…，rim)表示用戶ui對(duì)所有服務(wù)的評(píng)分信息，rij表示用戶ui對(duì)服務(wù)sj的評(píng)分，說(shuō)明用戶ui對(duì)服務(wù)sj的滿意程度.評(píng)分采用電子商務(wù)評(píng)價(jià)機(jī)制中常用的5個(gè)評(píng)分等級(jí)，1-5分別表示很不滿意、不滿意、一般、滿意和很滿意.所有用戶對(duì)服務(wù)的評(píng)分信息用矩陣R=[rij]m×n表示.

由于在線服務(wù)規(guī)模非常龐大，用戶不可能對(duì)所有服務(wù)進(jìn)行評(píng)分.目前，協(xié)同過(guò)濾方法已被廣泛地用于信譽(yù)系統(tǒng)，該方法通過(guò)尋找與自己偏好相似的用戶進(jìn)行評(píng)分預(yù)測(cè).為此，可采用Fernández-Tobías I等人提出的協(xié)同過(guò)濾方法[23]對(duì)評(píng)分進(jìn)行填充.

定義3.服務(wù)集S的信譽(yù)用信譽(yù)向量rp=(rp1，rp2，…rpj，…，rpm)表示，rpj為服務(wù)sj的信譽(yù)值.根據(jù)用戶對(duì)在線服務(wù)的評(píng)分R采用不同的信譽(yù)度量方法可以得到在線服務(wù)的信譽(yù)rp.

定義4.管理者對(duì)在線服務(wù)信譽(yù)控制的問(wèn)題可表述為f：O→sj，sj∈S，其中sj為信譽(yù)最高的服務(wù)，集合O為所有用戶的序數(shù)偏好.即管理者通過(guò)對(duì)所有用戶對(duì)在線服務(wù)的偏好O實(shí)施控制使服務(wù)sj成為信譽(yù)最高的服務(wù).

管理者對(duì)在線服務(wù)信譽(yù)控制問(wèn)題具體可分為增加用戶構(gòu)造性控制問(wèn)題、刪除用戶構(gòu)造性控制問(wèn)題、增加服務(wù)構(gòu)造性控制問(wèn)題和刪除服務(wù)構(gòu)造性控制問(wèn)題.

定義5.增加用戶構(gòu)造性控制問(wèn)題：給定用戶偏好集合O，實(shí)施控制前的初始用戶集合U1、增加的干擾用戶集合U2(U=U1∪U2，U1∩U2=?)，控制后信譽(yù)最高的服務(wù)sj∈S，基于用戶群體偏好O通過(guò)增加干擾用戶U2使得服務(wù)sj成為信譽(yù)最高的服務(wù).

即信譽(yù)系統(tǒng)管理者利用掌握到的用戶偏好，通過(guò)增加干擾用戶使得實(shí)施控制前的某一特定服務(wù)成為信譽(yù)最高的服務(wù).

定義6.刪除用戶構(gòu)造性控制問(wèn)題：給定用戶偏好集合O，實(shí)施控制后信譽(yù)最高的服務(wù)sj∈S，基于用戶群體偏好O通過(guò)刪除用戶集U中k個(gè)用戶使得服務(wù)sj成為信譽(yù)最高的服務(wù).

即信譽(yù)系統(tǒng)管理者利用掌握到的用戶偏好，通過(guò)刪除用戶使得某一特定服務(wù)成為信譽(yù)最高的服務(wù).

定義7.增加服務(wù)構(gòu)造性控制問(wèn)題：給定用戶偏好集合O，實(shí)施控制前的初始服務(wù)集合S1、增加的干擾服務(wù)集合S2(S=S1∪S2，S1∩S2=?)，控制后信譽(yù)最高的服務(wù)sj∈S1，基于用戶群體偏好O通過(guò)增加干擾服務(wù)S2使得服務(wù)sj成為信譽(yù)最高的服務(wù).

即信譽(yù)系統(tǒng)管理者利用掌握到的用戶偏好，通過(guò)增加干擾服務(wù)使得實(shí)施控制前的某一特定服務(wù)成為信譽(yù)最高的服務(wù).

定義8.刪除服務(wù)構(gòu)造性控制問(wèn)題：給定用戶偏好集合O，實(shí)施控制后信譽(yù)最高的服務(wù)sj∈S，基于用戶群體偏好O通過(guò)刪除服務(wù)集S中k個(gè)服務(wù)使得服務(wù)sj成為信譽(yù)最高的服務(wù).

即信譽(yù)系統(tǒng)管理者利用掌握到的用戶偏好，通過(guò)刪除服務(wù)使得某一特定服務(wù)成為信譽(yù)最高的服務(wù).

因此，本文旨在解決通過(guò)增加、刪除用戶或服務(wù)的構(gòu)造性控制問(wèn)題，防止信譽(yù)系統(tǒng)內(nèi)部的管理者將某特定服務(wù)控制為信譽(yù)最高的服務(wù)，干擾用戶的選擇.

3.2 舉例說(shuō)明

例.以常見(jiàn)的均值法增加用戶的構(gòu)造性控制問(wèn)題為例.假設(shè)有用戶集U={u1，u2，u3，u4，u5}，u5是增加的干擾用戶，服務(wù)集S={s1，s2，s3，s4}，用戶-服務(wù)的評(píng)分矩陣R如表1所示，需解決基于用戶對(duì)服務(wù)的偏好信息通過(guò)增加用戶使得服務(wù)s2成為信譽(yù)最高服務(wù)的問(wèn)題：

表1 用戶-服務(wù)評(píng)分表Table 1 User-service score sheet

由表1可見(jiàn)，通過(guò)計(jì)算所有用戶對(duì)服務(wù)評(píng)分的平均值得到其服務(wù)信譽(yù)，得到的信譽(yù)向量為rp=(3，2.75，2.25，2.5)，s1為當(dāng)前信譽(yù)最高的服務(wù).通過(guò)增加干擾用戶u5后的用戶-服務(wù)評(píng)分表如表2所示.

表2 用戶-服務(wù)評(píng)分矩陣表Table 2 User-service score sheet

增加干擾用戶u5后得到的信譽(yù)向量為rp=(2.8，3.2，2.4，2.8).通過(guò)增加用戶控制，使得服務(wù)s2成為了信譽(yù)最高的服務(wù).因此通過(guò)增加用戶可以很容易地對(duì)均值法實(shí)施構(gòu)造性控制.本文提出Fallback方法進(jìn)行在線服務(wù)信譽(yù)度量，以解決信譽(yù)系統(tǒng)內(nèi)部的管理者利用掌握到的用戶偏好，對(duì)服務(wù)信譽(yù)進(jìn)行控制的問(wèn)題.

4 利用Fallback的在線服務(wù)信譽(yù)防控制機(jī)制

Fallback方法是Bucklin與Approal混合的社會(huì)選擇方法[24].Bucklin方法中每個(gè)用戶要根據(jù)他的偏好對(duì)所有的服務(wù)進(jìn)行嚴(yán)格的線性排序；Approal方法中用戶通過(guò)批準(zhǔn)向量(0，1)表達(dá)偏好，0代表不贊同，1代表贊同.Fallback將Bucklin和Approal結(jié)合起來(lái)，每個(gè)用戶提供對(duì)他所認(rèn)可服務(wù)的嚴(yán)格偏好排序.目前已知的社會(huì)選擇方法中，F(xiàn)allback方法顯示了最廣泛的控制抵抗力[9].因此，本文利用Fallback，設(shè)計(jì)了一種在線服務(wù)信譽(yù)防控制機(jī)制，利用Fallback控制用戶偏好問(wèn)題的計(jì)算復(fù)雜性高的特性來(lái)防止管理者控制信譽(yù).

4.1 利用Fallback的在線服務(wù)信譽(yù)度量

本文信譽(yù)度量方法的核心是根據(jù)所有用戶對(duì)在線服務(wù)的偏好獲取滿足Fallback絕對(duì)多數(shù)閾值條件的在線服務(wù)信譽(yù)向量.

定義9.用戶ui對(duì)在線服務(wù)的評(píng)分rij越大表示ui對(duì)sj越滿意，rij>rik表示用戶ui認(rèn)為服務(wù)sj優(yōu)于服務(wù)sk(記作sj?isk)；rij

首先根據(jù)用戶ui對(duì)在線服務(wù)的評(píng)分信息ri，將每個(gè)用戶對(duì)在線服務(wù)的評(píng)分按大小進(jìn)行排序，若在線服務(wù)對(duì)應(yīng)的評(píng)分相同則采用隨機(jī)法對(duì)評(píng)分相同的服務(wù)進(jìn)行排序，獲取所有用戶的序數(shù)偏好集合.例如，對(duì)于表1中用戶u1的評(píng)分信息為r1=(4，2，3，1)，對(duì)4個(gè)服務(wù)分?jǐn)?shù)進(jìn)行排序可以得到用戶u1對(duì)在線服務(wù)的偏好序β1：s1?1s3?1s2?1s4.

若用戶提供了對(duì)在線服務(wù)的偏好排序，則可直接使用該排序作為用戶偏好O.由于用戶不可能對(duì)所有服務(wù)進(jìn)行偏好排序，即用戶偏好序是不完全序.為此，可采用William Webber[6]、Riku Togashi等提出[25]的概率用戶模型，處理不完整偏好排序，從而得到一個(gè)完整偏好排序.

獲取所有用戶對(duì)在線服務(wù)的偏好排序后利用Fallback方法計(jì)算信譽(yù)向量，得到最終所有用戶對(duì)服務(wù)的信譽(yù)度及最終的用戶群體偏好.首先需要得到在線服務(wù)在偏好排序中的l級(jí)分?jǐn)?shù).基于所有用戶的序數(shù)偏好集合O，計(jì)算每一個(gè)在線服務(wù)sj∈S在偏好排序中的l級(jí)分?jǐn)?shù)scorel(sj)，其表示將在線服務(wù)sj排在前l(fā)位的用戶的數(shù)量，l=1，2，…，n.

定義10.函數(shù)Di的取值為0、1：若用戶ui認(rèn)為服務(wù)sj優(yōu)于sk，即sj?isk則Di(sj?isk)=1、Di(sk?isj)=0；認(rèn)為sk優(yōu)于sj，則Di(sk?isj)=1、Di(sj?isk)=0.

定義11.函數(shù)Mi的取值為0、1，可以表示為：

(1)

最終服務(wù)sj在偏好排序中的l級(jí)分?jǐn)?shù)scorel(sj)為：

(2)

比如，根據(jù)表1的評(píng)分信息得出偏好排序，沒(méi)有用戶將在線服務(wù)s3排在第1位，所以服務(wù)s3的1級(jí)分?jǐn)?shù)為0；用戶u1、u2將在線服務(wù)s3排在前2位，所以服務(wù)s3的2級(jí)分?jǐn)?shù)為2；用戶u1、u2、u3將在線服務(wù)s3排在前3位，所以服務(wù)s3的3級(jí)分?jǐn)?shù)為3.同理我們也可以分別計(jì)算出其余在線服務(wù)的l級(jí)分?jǐn)?shù)，最終得到l級(jí)分?jǐn)?shù)scorel(sj)如表3所示.

表3 服務(wù)的l級(jí)分?jǐn)?shù)表Table 3 Level l score of services sheet

得到在線服務(wù)在偏好排序中的l級(jí)分?jǐn)?shù)后，需要判斷這些分?jǐn)?shù)是否滿足絕對(duì)多數(shù)閾值條件.用戶集U中的用戶的絕對(duì)多數(shù)閾值為：

maj(U)=|U|/2+1

(3)

1)根據(jù)在線服務(wù)在偏好排序中的l級(jí)分?jǐn)?shù)，判斷第一級(jí)中是否有達(dá)到scorel(sj)≥maj(U)條件的服務(wù)；

2)若有，則該服務(wù)的信譽(yù)值即為當(dāng)前滿足絕對(duì)多數(shù)閾值條件的一級(jí)分?jǐn)?shù)；

3)若沒(méi)有達(dá)到條件，判斷下一級(jí)分?jǐn)?shù)中是否存在滿足條件的服務(wù)，直到得到每個(gè)服務(wù)的信譽(yù)值.

最先達(dá)到絕對(duì)多數(shù)閾值條件的服務(wù)是用戶群體偏好排名第1的服務(wù)，若在同一級(jí)分?jǐn)?shù)中存在幾個(gè)滿足條件的服務(wù)，則對(duì)這些服務(wù)的分?jǐn)?shù)進(jìn)行排序從而得到最終的用戶群體偏好.比如，表3中在第2級(jí)中服務(wù)s1的信譽(yù)是最先達(dá)到閾值3的，服務(wù)s2、s3的信譽(yù)都在第3級(jí)達(dá)到閾值3，服務(wù)s2的信譽(yù)4大于服務(wù)s3的信譽(yù)3，最終得到的信譽(yù)向量為rp=(3，4，3，4)，最終的偏好排序?yàn)閟1?s2?s3?s4.

基于以上分析，最后確定出利用Fallback的在線服務(wù)信譽(yù)度量函數(shù)：

f(sj)=scorel(sj)，scorel(sj)≥maj(U)

(4)

算法1給出了利用Fallback的在線服務(wù)信譽(yù)度量算法.其中Mi(sj)由公式(1)計(jì)算得出.

算法1.利用Fallback的在線服務(wù)信譽(yù)度量算法

輸入：所有用戶的序數(shù)偏好集合O

輸出：在線服務(wù)信譽(yù)向量rp

2.fori=1 tondo

3.forj=1 tomdo

4.fork=1 tomdo

6.endfor

7.endfor

8.endfor

10.ifscorel(sj)≥maj(U) then

11.rpj=scorel(sj);

12.else if

13.l+1;

14. goto to (10);

15.fill the vectorrpbyrpj;

16.returnrp;

從上面描述可以看出，算法1中第2行-第4行的for循環(huán)表示每個(gè)用戶都對(duì)服務(wù)sj與除sj以外的其他服務(wù)逐一進(jìn)行比較，其時(shí)間復(fù)雜度為O(nm2)，最終算法1的時(shí)間復(fù)雜度為O(nm2).

4.2 理論分析

為了通過(guò)理論驗(yàn)證本方法防控制的有效性，下面對(duì)利用Fallback的在線服務(wù)信譽(yù)度量方法的防控制性進(jìn)行證明.

防控制性表明Fallback控制用戶偏好問(wèn)題的計(jì)算復(fù)雜性高，即證明構(gòu)造性控制問(wèn)題是固定參數(shù)不可解的.本文以利用Fallback的刪除服務(wù)構(gòu)造性控制問(wèn)題為例，證明該控制問(wèn)題固定參數(shù)不可解，首先給出參數(shù)化問(wèn)題[26]相關(guān)定義如下：

定義12.參數(shù)化問(wèn)題分為固定參數(shù)可解(fixed- parameter tractability，F(xiàn)PT)和固定參數(shù)不可解.FPT：給定利用Fallback的刪除服務(wù)構(gòu)造性控制問(wèn)題Π′，如果有一個(gè)算法在運(yùn)行時(shí)間O(g(k′)|I|O(1))內(nèi)可以解決該問(wèn)題，則該問(wèn)題稱為固定參數(shù)可解，其中k′為最多刪除服務(wù)的個(gè)數(shù)，g是任意函數(shù)，(I′，k′)是刪除服務(wù)構(gòu)造性控制問(wèn)題的實(shí)例即利用Fallback的在線服務(wù)集S中服務(wù)的信譽(yù)度量.否則利用Fallback的刪除服務(wù)構(gòu)造性控制問(wèn)題Π′被稱為固定參數(shù)不可解.

FPT-歸約：如果存在一種算法，可以在時(shí)間O(g(k)|I|O(1))內(nèi)，把k-支配集問(wèn)題Π的實(shí)例(I，k)轉(zhuǎn)換為利用Fallback的刪除服務(wù)構(gòu)造性控制問(wèn)題Π′的實(shí)例(I′，k′)，則k-支配集問(wèn)題Π可FPT-歸約到刪除服務(wù)構(gòu)造性控制問(wèn)題Π′.其中k為k-支配集的參數(shù)k，k′為最多刪除服務(wù)的個(gè)數(shù)，在定理1中k=k′，g是任意函數(shù).

定義13.參數(shù)化問(wèn)題Π可FPT-歸約到WCNF-2SAT問(wèn)題，那么稱Π屬于W[1]；參數(shù)化問(wèn)題Π可FPT-歸約到WCS[t]問(wèn)題，那么稱Π屬于W[t].WCS[2]問(wèn)題是WCNF-2SAT問(wèn)題的拓展.W[1]?W[2].一個(gè)問(wèn)題如果是W[t]-hard問(wèn)題，則被認(rèn)為是固定參數(shù)不可解的.

即只需要找到一個(gè)已知的W[2]-complete問(wèn)題k-支配集Π的實(shí)例可以轉(zhuǎn)換到利用Fallback的刪除服務(wù)構(gòu)造性控制問(wèn)題Π′的實(shí)例則可證明該構(gòu)造性控制問(wèn)題是W[2]-hard問(wèn)題即固定參數(shù)不可解問(wèn)題.

定理.利用Fallback的刪除服務(wù)構(gòu)造性控制問(wèn)題是W[2]-hard問(wèn)題.

證明：已知的W[2]-complete問(wèn)題k-支配集問(wèn)題：在一個(gè)無(wú)向圖G=(B，E)中，對(duì)于子集B′?B，若每一個(gè)節(jié)點(diǎn)bi，bi∈B′或鄰接B′中至少一個(gè)點(diǎn)，則稱子集B′為支配集.

給定k-支配集問(wèn)題的實(shí)例I=(G，k)，其中G=(S1，E)，k

構(gòu)造利用Fallback的刪除服務(wù)構(gòu)造性控制問(wèn)題的實(shí)例I′：給定用戶集U、服務(wù)集S，其中S=S1∪S2∪{sj}∪S3∪S4，sj是控制后信譽(yù)最高的服務(wù).

S2：S2是一組k+1個(gè)服務(wù)，這些服務(wù)防止刪除最多k個(gè)服務(wù)使服務(wù)sj成為唯一的信譽(yù)最高的服務(wù).

S4：S4是一組n(k+1)個(gè)服務(wù)，對(duì)于每個(gè)j，1≤j≤k+1，可以找到具有n個(gè)元素的子集S4j?S4，這些子集確保每個(gè)服務(wù)s2j∈S2總是位于表4的第2個(gè)偏好排序的第(n+k+1)個(gè)位置.

U是2n+1個(gè)用戶集合，因此n+1為絕對(duì)多數(shù)閾值.用戶集U中的用戶對(duì)服務(wù)集S中服務(wù)的偏好排序如表4所示.

表4 用戶-服務(wù)偏好排序表Table 4 User-service preference ranking sheet

服務(wù)的l級(jí)分?jǐn)?shù)如表5所示：

表5 服務(wù)的l級(jí)分?jǐn)?shù)表Table 5 Level l score of services sheet

證明實(shí)例I可以轉(zhuǎn)換到實(shí)例I′，即需要證明下面結(jié)果是成立的：實(shí)例I存在大小為k的支配集當(dāng)且僅當(dāng)實(shí)例I′中通過(guò)刪除k個(gè)服務(wù)使sj成為唯一的信譽(yù)最高的服務(wù)(這里k-支配集的參數(shù)k與最多刪除k個(gè)服務(wù)的k相同).

從右到左：假設(shè)sj可以通過(guò)刪除最多k個(gè)服務(wù)而成為唯一的信譽(yù)最高的服務(wù).由于除了sj之外(即S2中的服務(wù))，還有k+1個(gè)服務(wù)在第n+k+1級(jí)達(dá)到絕對(duì)多數(shù)，從S2中刪除k個(gè)服務(wù)不足以使sj成為最終的唯一的信譽(yù)最高的服務(wù).因此sj必須在低于或等于n+k級(jí)上才能成為唯一的信譽(yù)最高的服務(wù)，那么在表4中sj在第一個(gè)偏好排序中的排名至少向前一個(gè)位置才有可能，這說(shuō)明k′≤k個(gè)被刪除的服務(wù)可能：

1.全被包含在S1中并且對(duì)應(yīng)G中的一個(gè)k′大小的支配集.

2.都在S1∪S3中.

證明過(guò)程表明已知的W[2]-complete問(wèn)題k-支配集可以FPT-歸約到利用Fallback的刪除服務(wù)構(gòu)造性控制問(wèn)題，因此利用Fallback的刪除服務(wù)的構(gòu)造性控制問(wèn)題是W[2]-hard問(wèn)題即該控制問(wèn)題是固定參數(shù)不可解的，說(shuō)明Fallback的刪除服務(wù)的構(gòu)造性控制問(wèn)題的計(jì)算復(fù)雜性高.同理，要證明其余構(gòu)造性控制類型問(wèn)題是NP-hard/W[2]-hard問(wèn)題也可以通過(guò)找到已知的NP-complete/W[2]-complete問(wèn)題歸約到控制問(wèn)題來(lái)證明.

5 實(shí)驗(yàn)結(jié)果及分析

為驗(yàn)證Fallback的防控制性，設(shè)計(jì)實(shí)現(xiàn)相關(guān)實(shí)驗(yàn)并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析.實(shí)驗(yàn)環(huán)境為Intel Core i7 處理器，8G內(nèi)存，64位Windows 10操作系統(tǒng)，開(kāi)發(fā)環(huán)境為pyCharm 2019.1，開(kāi)發(fā)語(yǔ)言為 Python 3.7.

5.1 數(shù)據(jù)集

為了避免實(shí)驗(yàn)的偏向性，使實(shí)驗(yàn)更加真實(shí)和可靠，實(shí)驗(yàn)同時(shí)采用合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集.合成數(shù)據(jù)集使用Mallows模型生成[27]；真實(shí)數(shù)據(jù)集為MovieLens數(shù)據(jù)集[28].

Mallows模型在序數(shù)偏好研究中被廣泛認(rèn)可并應(yīng)用[27]，其合成的偏好數(shù)據(jù)集用ML表示.在Mallows模型中設(shè)置兩個(gè)參數(shù)：中心偏好序σ和離散參數(shù)θ.其中，σ為由m個(gè)在線服務(wù)構(gòu)成的完整偏好排序，離散參數(shù)θ用于控制合成的偏好序與中心偏好序σ的離散程度.本文隨機(jī)生成中心偏好序σ，離散參數(shù)θ設(shè)置為0.5，設(shè)置較大數(shù)量的用戶量n及在線服務(wù)量m，合成不同的偏好數(shù)據(jù)集.

MovieLens數(shù)據(jù)集在服務(wù)研究的相關(guān)領(lǐng)域內(nèi)得到普遍應(yīng)用[28]，該數(shù)據(jù)集包含了1682部電影，943個(gè)用戶，以及 100000 條左右的評(píng)分(1～5)，每個(gè)用戶至少對(duì) 20 部電影進(jìn)行過(guò)評(píng)分，用MV表示.由于MV中用戶對(duì)服務(wù)的評(píng)分非常稀疏，首先采用協(xié)同過(guò)濾方法對(duì)評(píng)分進(jìn)行填充，然后根據(jù)每個(gè)用戶對(duì)服務(wù)的評(píng)分進(jìn)行排序，若評(píng)分相同則采用隨機(jī)法對(duì)其進(jìn)行排序，最終獲得用戶-服務(wù)完整偏好排序.

5.2 防控制性實(shí)驗(yàn)

為了在最容易控制的情況下測(cè)試各個(gè)方法的防控制性，實(shí)驗(yàn)通過(guò)使用預(yù)先排序，找到控制的最優(yōu)策略.即對(duì)增加用戶構(gòu)造性控制來(lái)說(shuō)，先增加將想控制服務(wù)排在最好位置的用戶；對(duì)刪除用戶構(gòu)造性控制來(lái)說(shuō)，先刪除將想控制服務(wù)排在最差位置的用戶；對(duì)增加服務(wù)構(gòu)造性控制來(lái)說(shuō)，先增加對(duì)想控制服務(wù)威脅最小的服務(wù)；對(duì)刪除服務(wù)構(gòu)造性控制來(lái)說(shuō)，先刪除對(duì)想控制服務(wù)最具威脅的服務(wù).在最能滿足控制要求的情況下，測(cè)試控制成功所需的時(shí)間.控制成功所需的時(shí)間越長(zhǎng)，說(shuō)明方法的防操縱性越強(qiáng).

Felix Brandt等指出Copeland方法是已知的第一個(gè)完全抵制所有類型的構(gòu)造性控制的方法[22]；Condorcet方法是控制用戶偏好問(wèn)題研究的第1個(gè)方法，所以在Mallows模型中本文使用Copeland和Condorcet方法作為與Fallback的對(duì)比方法.基于Mallows模型的實(shí)驗(yàn)對(duì)4種控制類型進(jìn)行實(shí)驗(yàn)，增加/刪除用戶的構(gòu)造性控制、增加/刪除服務(wù)的構(gòu)造性控制.

由于均值法(Average)易于理解并且被廣泛的應(yīng)用于在線服務(wù)信譽(yù)系統(tǒng)中[4]，所以在MovieLens數(shù)據(jù)集上的實(shí)驗(yàn)對(duì)比方法除了Copeland和Condorcet方法之外多增加了均值法(Average).基于MovieLens數(shù)據(jù)集的實(shí)驗(yàn)同樣對(duì)上述4種控制類型進(jìn)行實(shí)驗(yàn).

在增加/刪除用戶或服務(wù)的場(chǎng)景中，設(shè)置增加/刪除用戶或服務(wù)的數(shù)量與初始用戶或服務(wù)的數(shù)量相同大小[9].

5.2.1 增加用戶和刪除用戶的構(gòu)造性控制

在增加用戶的構(gòu)造性控制中，實(shí)驗(yàn)對(duì)新增用戶進(jìn)行預(yù)排序，找到增加用戶的構(gòu)造性控制的最優(yōu)策略，在最易控制的情況下測(cè)試各個(gè)方法的防控制性.首先增加的用戶是將想控制的服務(wù)排在最好位置的用戶，最后增加的用戶是將服務(wù)排在最差位置的用戶.刪除用戶的預(yù)排序過(guò)程與增加用戶的預(yù)排序過(guò)程相反.由于ML數(shù)據(jù)集中的用戶直接提供對(duì)在線服務(wù)的偏好排序，而均值法需要根據(jù)用戶的評(píng)分信息得到服務(wù)的信譽(yù)，所以在基于ML數(shù)據(jù)集的實(shí)驗(yàn)中未使用均值法(Average)作為對(duì)比方法.

基于ML數(shù)據(jù)集的增加用戶構(gòu)造性控制實(shí)驗(yàn)?zāi)M了控制前的50-500個(gè)初始用戶、50-500個(gè)增加的干擾用戶和10個(gè)在線服務(wù).由于MV數(shù)據(jù)集的用戶總量為943個(gè)，基于MV數(shù)據(jù)集的增加用戶實(shí)驗(yàn)?zāi)M了50-450個(gè)初始用戶、50-450個(gè)增加的干擾用戶和10個(gè)在線服務(wù)，兩個(gè)實(shí)驗(yàn)增加用戶量與初始用戶量相同.實(shí)驗(yàn)記錄Fallback方法及對(duì)比方法的控制成功所需的時(shí)間.ML增加用戶構(gòu)造性控制成功所需的時(shí)間如表6所示，MV控制成功所需的時(shí)間如圖1所示.

表6 ML數(shù)據(jù)集增加用戶構(gòu)造性控制時(shí)間表Table 6 Time of constructive control by adding users in ML data sets sheet

圖1 MV數(shù)據(jù)集增加用戶構(gòu)造性控制時(shí)間Fig.1 Time of constructive control by adding users in MV data sets

在刪除用戶的構(gòu)造性控制中，基于ML、MV的實(shí)驗(yàn)?zāi)M了50-500個(gè)用戶和10個(gè)在線服務(wù)，最多可以刪除的用戶量與初始用戶量相同.ML刪除用戶構(gòu)造性控制成功所需的時(shí)間如表7所示，MV控制成功所需的時(shí)間如圖2所示.

表7 ML數(shù)據(jù)集刪除用戶構(gòu)造性控制時(shí)間表Table 7 Time of constructive control by deleting users in ML data sets sheet

由表6、表7、圖1、圖2可見(jiàn)，隨著增加的干擾用戶或刪除用戶的數(shù)量增加，F(xiàn)allback方法、Copeland方法、Condorcet方法、均值法(Average)的控制成功所需的時(shí)間均增加，F(xiàn)allback方法控制時(shí)間比另外3種方法更長(zhǎng)，Copeland方法、Condorcet方法控制時(shí)間比較接近，均值法(Average)控制時(shí)間最短.對(duì)

圖2 MV數(shù)據(jù)集刪除用戶構(gòu)造性控制時(shí)間Fig.2 Time of constructive control by deleting users in MV data sets

于較大數(shù)量級(jí)的用戶來(lái)說(shuō)，F(xiàn)allback方法的防控制性優(yōu)勢(shì)更明顯，通過(guò)增加用戶或刪除用戶的構(gòu)造性控制更為困難.

5.2.2 增加服務(wù)和刪除服務(wù)的構(gòu)造性控制

增加服務(wù)的構(gòu)造性控制中，實(shí)驗(yàn)對(duì)新增服務(wù)進(jìn)行預(yù)排序，找到增加服務(wù)的構(gòu)造性控制的最優(yōu)策略，預(yù)排序首先增加的第1個(gè)服務(wù)為：有最少的用戶將該服務(wù)排在想控制的服務(wù)之前；最后增加的服務(wù)為：有最多的用戶將該服務(wù)排在想控制的服務(wù)之前，即通過(guò)將服務(wù)升序排序之后，首先增加了對(duì)控制服務(wù)威脅最小的服務(wù)，找到了當(dāng)前控制的最優(yōu)策略.刪除服務(wù)構(gòu)造性控制的預(yù)排序過(guò)程與增加服務(wù)構(gòu)造性控制的預(yù)排序過(guò)程相反，需要首先刪除對(duì)控制服務(wù)成為唯一贏家最具威脅的服務(wù).基于ML、MV數(shù)據(jù)集的增加服務(wù)構(gòu)造性控制實(shí)驗(yàn)?zāi)M了控制前10-100個(gè)初始服務(wù)、10-100個(gè)增加的干擾服務(wù)和10個(gè)用戶，兩個(gè)數(shù)據(jù)集的實(shí)驗(yàn)增加服務(wù)量與初始服務(wù)量相同.實(shí)驗(yàn)記錄Fallback方法及對(duì)比方法的控制成功所需的時(shí)間.ML數(shù)據(jù)集增加服務(wù)構(gòu)造性控制成功所需時(shí)間如圖3所示，MV數(shù)據(jù)集控制成功所需時(shí)間如圖4所示.

圖3 ML數(shù)據(jù)集增加服務(wù)構(gòu)造性控制時(shí)間Fig.3 Time of constructive control by adding services in ML data sets

圖4 MV數(shù)據(jù)集增加服務(wù)構(gòu)造性控制時(shí)間Fig.4 Time of constructive control by adding services in MV data sets

刪除服務(wù)的構(gòu)造性控制中，基于ML、MV的實(shí)驗(yàn)?zāi)M了10-100個(gè)服務(wù)和10個(gè)用戶.ML數(shù)據(jù)集刪除服務(wù)構(gòu)造性控制成功所需時(shí)間如圖5所示，MV數(shù)據(jù)集控制成功所需時(shí)間如圖6所示.

圖5 ML數(shù)據(jù)集刪除服務(wù)構(gòu)造性控制時(shí)間Fig.5 Time of constructive control by deleting services in ML data sets

圖6 MV數(shù)據(jù)集刪除服務(wù)構(gòu)造性控制時(shí)間Fig.6 Time of constructive control by deleting services in MV data sets

由圖3-圖6可見(jiàn)，隨著增加的干擾服務(wù)或刪除服務(wù)的數(shù)量增加，F(xiàn)allback方法控制成功所需的時(shí)間呈指數(shù)型增長(zhǎng)，當(dāng)服務(wù)數(shù)量達(dá)到70個(gè)以上時(shí)，與其他方法的對(duì)比更加明顯.Copeland方法、Condorcet方法控制成功時(shí)間比較接近，均值法(Average)控制成功時(shí)間最短.兩種數(shù)據(jù)集的實(shí)驗(yàn)均表明，增加服務(wù)或刪除服務(wù)構(gòu)造性控制中，F(xiàn)allback方法控制成功所需的時(shí)間最長(zhǎng)，F(xiàn)allback方法具有更強(qiáng)的防控制性.

6 結(jié) 語(yǔ)

本文提出了利用Fallback的在線服務(wù)信譽(yù)防控制機(jī)制，以解決信譽(yù)系統(tǒng)內(nèi)部能夠掌握用戶偏好的管理者的控制問(wèn)題.該機(jī)制通過(guò)Fallback方法集結(jié)所有用戶的評(píng)分信息或偏好排序得到最終服務(wù)的信譽(yù)及用戶群體偏好，利用Fallback方法提高控制用戶偏好問(wèn)題的計(jì)算復(fù)雜性，增加管理者的攻擊時(shí)間成本以達(dá)到防控制的目的，為在線服務(wù)的防控制提供了一種新的思路.理論分析表明了該方法的防控制性，實(shí)驗(yàn)進(jìn)一步驗(yàn)證了該方法防控制的有效性.

本方法在增加或者刪除用戶、服務(wù)的控制類型中驗(yàn)證了Fallback方法對(duì)指定服務(wù)的防控制性，但未對(duì)控制用戶群體偏好序的防控制性進(jìn)行驗(yàn)證.因此下一步的工作將針對(duì)各類控制的偏好序的防控制性進(jìn)一步開(kāi)展研究.