采用社會網(wǎng)絡(luò)能力發(fā)現(xiàn)的眾包服務(wù)節(jié)點(diǎn)選擇算法

彭振龍,桂小林

(1.西安交通大學(xué)電子與信息學(xué)部,710049,西安; 2.泉州師范學(xué)院陳守仁商學(xué)院,362000,福建泉州; 3.西安交通大學(xué)陜西省計算機(jī)網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室,710049,西安; 4.泉州師范學(xué)院云計算物聯(lián)網(wǎng)電子商務(wù)智能福建省高校工程研究中心,362000,福建泉州)

眾包系統(tǒng)的質(zhì)量控制始終是一個嚴(yán)峻挑戰(zhàn)[1-2]。一個眾包系統(tǒng)一般包括平臺、網(wǎng)絡(luò)、任務(wù)的發(fā)布者和任務(wù)的接受者。眾包平臺通常通過一定的激勵機(jī)制,吸引任務(wù)接受者參與眾包任務(wù)[3-5]。由于眾包系統(tǒng)的開放性、匿名性,導(dǎo)致可能存在很多的參與者不認(rèn)真執(zhí)行任務(wù),而僅僅為了獲得獎勵,這一現(xiàn)象嚴(yán)重影響了眾包系統(tǒng)的效率和可信度[6-8]?？刂票姲?wù)質(zhì)量的基本策略主要有兩個:一是事后控制,即對眾包服務(wù)的結(jié)果進(jìn)行篩查處理;二是事前控制,即對參與者的能力和誠信度進(jìn)行評估,選擇更可靠更合適的參與者。本文從社會關(guān)系角度出發(fā),選擇更合適、更可靠的參與者,從而提升眾包服務(wù)質(zhì)量,屬于事前控制策略。

在質(zhì)量控制方面:Howe提出了golden standard data模式,即在眾包任務(wù)中隨機(jī)插入一些具有標(biāo)準(zhǔn)答案的任務(wù),根據(jù)參與者對這些任務(wù)的應(yīng)答,判斷參與者對其他任務(wù)的完成質(zhì)量[1];Peng等將激勵機(jī)制與參與者完成眾包任務(wù)的結(jié)果質(zhì)量相結(jié)合,根據(jù)眾包任務(wù)參與者的有效貢獻(xiàn)來決定獎勵大小,與統(tǒng)一定價方案相比,該方法具有較好的性能[3];Tong等采用了simple majority voting方法,即根據(jù)多個參與者對同一個任務(wù)的應(yīng)答,采用簡單的多數(shù)投票方法確定最終的結(jié)果[9]。此外,一種稱為historical performance-based methods的方法被廣泛使用,該方法根據(jù)參與者的歷史任務(wù)完成情況和評價,對其執(zhí)行結(jié)果賦予一定的權(quán)值。但是,以上這些方法沒有考慮任務(wù)需求與參與者能力之間的匹配,而且存在冷啟動問題,即剛開始的時候無法對該參與者進(jìn)行評價[7,10-11]。另外,Zhang等提出了一個簡單有效的稱為MacroWiz的框架,并利用MSN進(jìn)行眾包活動,當(dāng)收到一個眾包任務(wù)后,MacroWiz可以激勵在線MSN用戶貢獻(xiàn)他們的知識或建議,協(xié)助任務(wù)請求者選擇可靠答案并作出最終決策[12]。Eickhoff等提出了一個反作弊策略,并且得出2條結(jié)論:①過濾惡意的參與者可以減少低質(zhì)量的數(shù)據(jù),但是會延長任務(wù)的完成時間;②參與者的可靠性無法由其歷史任務(wù)完成率進(jìn)行保證[13]。Qin等針對圖片的易修改性,提出了一個簡單有效的輕量級的圖片修改檢測方法,用于保證基于手機(jī)的圖片版權(quán)[14]。Shamir等分析了人工分類和標(biāo)注的一致性,提出了一種基于監(jiān)督機(jī)器學(xué)習(xí)的眾包質(zhì)量控制方法[15]。

在參與者選擇方面,考慮到終端的移動性會導(dǎo)致收集數(shù)據(jù)的路由發(fā)生變化,Zhao等提出了一個無中心化的路由策略,即利用服務(wù)節(jié)點(diǎn)之間的機(jī)會相遇來轉(zhuǎn)發(fā)任務(wù)、收集數(shù)據(jù)[16-18]。眾包任務(wù)一般可分為時間敏感任務(wù)和可容忍延時的任務(wù),基于此,Guo等提出了一個適用于多任務(wù)的移動用戶選擇和大范圍的眾包服務(wù)場景的ActiveCrowd的框架,并利用greedy enhanced genetic algorithm為參與者實(shí)現(xiàn)總距離或總開銷的最優(yōu)或近似最優(yōu)[19]。張君濤等將子道路和任務(wù)綁定在一起,提出了一種基于矢量任務(wù)地圖的漸進(jìn)式的任務(wù)分發(fā)方法,并提高了任務(wù)地圖的分辨率[20]。Peng等提出了一種基于泰森多邊形的參與者節(jié)點(diǎn)選擇方法,將傳統(tǒng)的基于標(biāo)準(zhǔn)柵格的參與者區(qū)域覆蓋變成基于任務(wù)特征的不規(guī)則區(qū)域覆蓋,提升了參與者的執(zhí)行效率,降低了平臺或任務(wù)發(fā)布者的總體成本[21]。安健等利用城市中公交載體的軌跡可預(yù)測、活動覆蓋范圍大、乘客節(jié)點(diǎn)自主聚集且交互時間有保證等優(yōu)勢,提出了一種基于公交系統(tǒng)的眾包任務(wù)差異化分發(fā)方法[22]。張文東等利用社會關(guān)系的多維要素,構(gòu)造多維語義分級樹和空間索引編碼,引入交互信息熵等相關(guān)概念,提出了一種社會屬性親密度量化方法,對社會關(guān)系的不對稱性進(jìn)行分析和比較,從而提高了親密度量化方法的客觀性[23]。

這些方法通過選擇更優(yōu)質(zhì)的服務(wù)節(jié)點(diǎn),在一定程度上提升了眾包的服務(wù)質(zhì)量,但是通常需要所有的參與者都事先在平臺上注冊,而且他們的信息(興趣、愛好、專長等)是固定不變的,任務(wù)發(fā)布者或者平臺能夠獲得他們的所有信息。但是,實(shí)踐中參與者的位置屬性、專長都有可能隨著時間而變化,即使是眾包服務(wù)平臺,也不可能獲知那些在平臺上注冊用戶的全部信息,更不可能獲知那些未在平臺上注冊的潛在參與者的全部信息。

基于此,本文提出了基于社會關(guān)系的眾包服務(wù)節(jié)點(diǎn)選擇算法,任務(wù)發(fā)布者不需要獲得全部參與者的信息,算法即會根據(jù)任務(wù)發(fā)布者與其朋友的社會關(guān)系、聊天信息等,對朋友能力進(jìn)行動態(tài)、精準(zhǔn)地分類與刻畫,將任務(wù)與朋友的能力值進(jìn)行匹配,從而選擇最合適的參與者參與眾包任務(wù)。當(dāng)朋友接受任務(wù)后,以同樣的方式在自己的朋友圈里發(fā)布該任務(wù)。如此循環(huán)迭代,能夠更高效、準(zhǔn)確地完成眾包任務(wù)。本文算法充分利用了社會關(guān)系中的天然信任關(guān)系,構(gòu)建了眾包任務(wù)參與者之間的信任鏈條,并且可以由社會關(guān)系中的六度分隔理論保證任務(wù)傳輸?shù)臅r間效率[24-25]。

1 基于社會網(wǎng)絡(luò)的能力發(fā)現(xiàn)與任務(wù)傳播

1.1 社會網(wǎng)絡(luò)

社會網(wǎng)絡(luò)是由許多節(jié)點(diǎn)構(gòu)成的一種社會關(guān)系結(jié)構(gòu),節(jié)點(diǎn)通常是指個人或組織,社會網(wǎng)絡(luò)代表各種社會關(guān)系,這些社會關(guān)系可以把從偶然相識的泛泛之交到緊密結(jié)合的家庭關(guān)系的各種人們或組織串連起來[24]。社會網(wǎng)絡(luò)內(nèi)個體成員之間以任何形式進(jìn)行的聯(lián)系稱為交互。交互能幫助社會網(wǎng)絡(luò)中的節(jié)點(diǎn)之間形成相對穩(wěn)定的關(guān)系體系,進(jìn)而影響節(jié)點(diǎn)的社會行為。

1.2 基本定義

每個節(jié)點(diǎn)都有其自身的屬性,如興趣愛好、專業(yè)特長等,并且對他的所有朋友都會有能力區(qū)分和認(rèn)識,如認(rèn)為某個朋友適合干什么、某個朋友對什么感興趣等。社會網(wǎng)絡(luò)中的一個節(jié)點(diǎn)用p表示,p的朋友數(shù)用m表示。眾包系統(tǒng)約定的能力類別數(shù)用n表示。任務(wù)參與者既包括任務(wù)發(fā)布者,又包括任務(wù)接受者。

定義1:能力。能力是完成一個項(xiàng)目或者任務(wù)所需要的基本技能或素質(zhì),用a表示。

定義2:能力集合。能力集合是完成一個眾包任務(wù)需要的所有能力的集合。平臺能力集合表示為A={a1,a2,…,an},共n種能力。

定義3:能力值。眾包任務(wù)參與者的能力值是該參與者對應(yīng)能力集合中各個能力的數(shù)值。由于一個節(jié)點(diǎn)的能力值在其不同朋友中會有不同認(rèn)知,因此即使是同一種能力,也可能會有不同的能力值。能力值的初始值Cp是由節(jié)點(diǎn)p的朋友根據(jù)其各自的認(rèn)知設(shè)定的,沒有設(shè)定的默認(rèn)為0。Cp具體表示為

(1)

(2)

定義5:誠信指數(shù)。誠信指數(shù)是指某個眾包參與者的所有朋友對該參與者質(zhì)量因子的加權(quán)平均。p的所有朋友對p總體評價可用誠信指數(shù)hp表示,表達(dá)式為

(3)

定義6:朋友能力向量。社會網(wǎng)絡(luò)中的節(jié)點(diǎn)對其每個朋友在能力集合中對應(yīng)的能力大小,構(gòu)成該節(jié)點(diǎn)的一個朋友能力向量。如節(jié)點(diǎn)p與朋友pj之間的能力向量ep,pj可表示為

(4)

定義7:朋友能力矩陣。社會網(wǎng)絡(luò)中的某一節(jié)點(diǎn)的所有朋友能力向量,構(gòu)成了該節(jié)點(diǎn)的朋友能力矩陣。節(jié)點(diǎn)p的朋友能力矩陣Ep可表示為

(5)

2 社會關(guān)系中基于內(nèi)容的能力發(fā)現(xiàn)

2.1 參與者社會關(guān)系重構(gòu)

結(jié)合式(1)(3)(5),可以將社會網(wǎng)絡(luò)中的節(jié)點(diǎn)p重新定義為一個三元組

p=〈hp,Cp,Ep〉

(6)

2.2 能力值的計算與更新

在能力值計算上,主要統(tǒng)計節(jié)點(diǎn)p與其朋友之間就某個關(guān)鍵詞的出現(xiàn)次數(shù)。如果某個關(guān)鍵詞出現(xiàn)在其朋友圈中,則以更大的權(quán)重計算。含加權(quán)朋友圈的能力值動態(tài)更新算法的偽代碼如下。

1:k=1;

2:Do whilek<=n

∥動態(tài)更新節(jié)點(diǎn)p的ak能力的能力值

5:k=k+1;

6:End Do;

2.3 含加權(quán)朋友圈能力的能力矩陣計算與更新

2.2節(jié)主要對節(jié)點(diǎn)p的能力值進(jìn)行計算和更新,更新后可以生成一個1×n的行向量。在此基礎(chǔ)之上,還需要對所有的朋友進(jìn)行能力計算,最后生成一個朋友能力矩陣,算法偽代碼如下。

1:k=1;j=1;

2:Do whilej<=m

3: Do whilek<=n

5:k=k+1;

6: End Do;

7:j=j+1;

8:End Do;

通過式(2)和能力值與能力矩陣的計算與更新,節(jié)點(diǎn)p完成了對自己社會關(guān)系的重構(gòu),可重寫式(5)為

p=

(7)

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

微信是中國最流行的一款移動即時聊天工具,根據(jù)最近騰訊公布的2019年第一季度財報,微信月活躍用戶數(shù)量已正式突破了11億,同比增長達(dá)6.9%,2018年微信日均發(fā)送信息450億條。微信為用戶構(gòu)建了一個龐大的社會關(guān)系。本文系統(tǒng)主要以微信交互數(shù)據(jù)為基礎(chǔ),為了避免隱私泄漏,本文系統(tǒng)只允許在使用者授權(quán)同意的情況下,分析自己的聊天記錄和內(nèi)容,對自己的朋友按主題類別進(jìn)行能力區(qū)分,重構(gòu)自己的社會關(guān)系。本文實(shí)驗(yàn)?zāi)M微信交互并進(jìn)行數(shù)據(jù)分析。

3.1 數(shù)據(jù)準(zhǔn)備

豬八戒網(wǎng)[26]是中國著名的眾包服務(wù)網(wǎng)站之一,通過對其網(wǎng)站內(nèi)容進(jìn)行分析發(fā)現(xiàn),眾包項(xiàng)目可以分成20個類目,分別是:知識產(chǎn)權(quán)、品牌設(shè)計、IT/軟件、營銷傳播、工商財稅、科技服務(wù)、電商服務(wù)等。不失一般性,選擇其中的10個類目進(jìn)行數(shù)據(jù)分析。由第1節(jié)分析可知,每種類目都代表一種能力或主題。10種能力的編號分別為1～10,代表了平臺能力集合為A={1,2,…,10}。對每種能力提煉了部分關(guān)鍵詞,如表1所示。

表1 能力分類及部分關(guān)鍵詞

3.2 能力發(fā)現(xiàn)

設(shè)定節(jié)點(diǎn)p有100個朋友,編號分別為1～100,本節(jié)重點(diǎn)介紹該節(jié)點(diǎn)的朋友能力矩陣Ep的生成過程。

設(shè)定一次采樣周期為1個月,隨機(jī)從10個主題中選擇若干個交互主題,交互主題的概率密度呈泊松分布,與每個朋友的交互次數(shù)在5～500之間。

根據(jù)表1,分別統(tǒng)計了1次采樣周期與5次采樣周期下,100個朋友中前10個朋友的能力值(交互次數(shù)),分別如表2和表3所示。

表2 1次采樣下前10個朋友10種主題的交互次數(shù)

表3 5次采樣下前10個朋友10種主題的交互次數(shù)

表4則顯示了5次采樣周期下,前10個朋友的朋友圈中出現(xiàn)各類關(guān)鍵詞的次數(shù),該值表明了該朋友在不同能力類別的朋友圈能力大小。假設(shè)朋友圈能力的權(quán)重為2,綜合表3和表4,可得到最終的朋友綜合能力矩陣,如表5所示。

根據(jù)表2中的初始能力,隨機(jī)選取了編號為5、8、69的朋友進(jìn)行研究,圖1和圖2分別顯示了在1次采樣下和5次采樣下,節(jié)點(diǎn)p與所有朋友在不同主題(能力)下的交互次數(shù)(能力值)。圖3為1次采樣與5次采樣(標(biāo)準(zhǔn)化后)下節(jié)點(diǎn)p與所有朋友的總交互次數(shù)的對比圖?？梢钥闯?兩條線的趨勢基本保持一致,說明1次采樣與5次采樣的結(jié)果相對穩(wěn)定。圖4為加入加權(quán)朋友圈能力后,節(jié)點(diǎn)p與朋友的交互次數(shù)。從圖1、2、4可以看出,總體而言,交互次數(shù)具有相對穩(wěn)定性,說明節(jié)點(diǎn)p的能力具有相對穩(wěn)定性,且與某個朋友在某種能力上的交互次數(shù)越多,則該能力值越大,反之亦然。

表4 朋友圈5次采樣下前10個朋友10種主題的交互次數(shù)

表5 計算朋友圈能力值后前10個朋友的最終綜合能力矩陣

圖1 部分節(jié)點(diǎn)1次采樣下不同主題的交互次數(shù)

圖2 部分節(jié)點(diǎn)5次采樣下不同主題的交互次數(shù)

圖3 1次采樣與5次采樣下不同主題所有朋友的總交互次數(shù)

圖4 5次采樣下加入朋友圈權(quán)重后不同主題的交互次數(shù)

3.3 候選傳播節(jié)點(diǎn)選擇

當(dāng)一個任務(wù)發(fā)布者想發(fā)布任務(wù)時,需要選擇任務(wù)的類目或者所需的能力關(guān)鍵詞,系統(tǒng)將從他自己的朋友中選擇匹配度最高的若干用戶做第1次任務(wù)分發(fā)。表6所示為1次仿真實(shí)驗(yàn)中得到的單能力候選節(jié)點(diǎn)排序表,以5次采樣數(shù)據(jù)得到的最終綜合能力矩陣(表5)為基礎(chǔ),將候選節(jié)點(diǎn)編號按照能力值從大到小進(jìn)行順序,只顯示能力值最高的前10個節(jié)點(diǎn)。

根據(jù)表6中數(shù)據(jù),如果節(jié)點(diǎn)p想要發(fā)布能力編號為2的眾包任務(wù),則應(yīng)該在其好友列表中選擇編號為57、28、31、50……的朋友,這是因?yàn)檫@些朋友的能力屬性最為匹配。如果眾包任務(wù)需要多種能力,只需要對不同的能力設(shè)計相應(yīng)的權(quán)重,即可找到最合適的朋友。實(shí)驗(yàn)中,選擇了不同的能力要求,并設(shè)置了相應(yīng)的權(quán)重,具體選擇的結(jié)果如表7所示。

表6 1次實(shí)驗(yàn)得到的單能力候選節(jié)點(diǎn)排序表(以5次采樣數(shù)據(jù)為基礎(chǔ))

表7 多能力及不同權(quán)重下的節(jié)點(diǎn)選擇結(jié)果

3.4 任務(wù)分發(fā)的時效性分析

眾包系統(tǒng)中任務(wù)分發(fā)的時間效率是很重要的,特別是對于那些延遲敏感的任務(wù)。因此,隨機(jī)選擇了4種任務(wù)類目:兼職、品牌創(chuàng)意、軟件開發(fā)、個人生活,即表1中編號為3、4、6、8的4種能力。本文采用了3種仿真實(shí)驗(yàn),即隨機(jī)分發(fā)方法、全分發(fā)方法、本文方法。假設(shè)節(jié)點(diǎn)p有2 000個朋友,并設(shè)定任務(wù)發(fā)布成功的標(biāo)準(zhǔn)是收到50個有效的任務(wù)轉(zhuǎn)發(fā)或執(zhí)行結(jié)果數(shù)據(jù)。在本文方法和隨機(jī)分發(fā)方法中,都選擇200個朋友進(jìn)行,全分發(fā)則意味著任務(wù)發(fā)送給所有朋友。在實(shí)驗(yàn)中,還假設(shè)當(dāng)任務(wù)能力需求落在朋友能力矩陣Ep中各能力主題的前50個朋友內(nèi)時,意味著該朋友將執(zhí)行任務(wù),任務(wù)完成時間是50個朋友完成任務(wù)的平均時間。不同分發(fā)策略下的完成任務(wù)平均時間如圖5所示,可以看出:隨機(jī)分發(fā)方法需要花費(fèi)最長的時間,這是因?yàn)槠洳荒芫_地發(fā)現(xiàn)最合適的參與者;本文方法比隨機(jī)分發(fā)平均節(jié)省了約64.5%的時間。進(jìn)一步地,本文方法和全分發(fā)方法的結(jié)果基本相似,表明本文方法可以精準(zhǔn)地發(fā)現(xiàn)合適的工作者,但是本文方法選擇的樣本數(shù)只有全分發(fā)方法的1/10,意味著本文方法給無關(guān)朋友帶來的信息干擾要比全分發(fā)策略少得多。此外,大多數(shù)任務(wù)分配都伴隨著一定的激勵機(jī)制,更少的樣本空間意味著能夠節(jié)約更多的成本。

第3節(jié)仿真實(shí)驗(yàn)表明:本文系統(tǒng)能順利地按主題計算各個朋友的能力值大小,并進(jìn)行采樣與更新,同時可以對朋友的誠信指數(shù)進(jìn)行采集與計算更新,形成能力矩陣;對任意一個在能力集合內(nèi)的眾包任務(wù),都能正確選擇出最匹配的朋友,據(jù)此找到傳播候選節(jié)點(diǎn)并進(jìn)行任務(wù)分發(fā)或數(shù)據(jù)回傳。

任何一個候選節(jié)點(diǎn)都可以重復(fù)以上步驟,經(jīng)過若干次迭代,任務(wù)能在朋友圈中快速擴(kuò)展,且朋友圈中的信任關(guān)系能被充分利用,在一定程度上增加了眾包參與者的可信度,從而提升了眾包的數(shù)據(jù)質(zhì)量。

圖5 不同分發(fā)策略下完成任務(wù)的平均時間

4 結(jié)束語

眾包服務(wù)節(jié)點(diǎn)的選擇應(yīng)綜合考慮其背景知識、社會關(guān)系、信譽(yù)度等多種屬性。本文方法首先需要對參與者進(jìn)行能力發(fā)現(xiàn),即從參與者日常在社交網(wǎng)絡(luò)中的交互內(nèi)容、交互次數(shù)、交互頻率、朋友圈、加入的群、在群里的活躍度等信息中,對朋友的能力進(jìn)行提煉,形成能力集合并對能力進(jìn)行量化分級。通過評估參與者的社會關(guān)系和社區(qū)歸屬特性,利用參與者社會關(guān)系中隱含的天然信任關(guān)系,有針對性地完成任務(wù)的分發(fā)和后續(xù)數(shù)據(jù)的路由轉(zhuǎn)發(fā)。因?yàn)槿藗兛偸歉敢廪D(zhuǎn)發(fā)與自己有社會關(guān)系的人的信息,所以通過社會關(guān)系找到的參與者候選集,比隨機(jī)選擇的參與者具有更高的精準(zhǔn)性,仿真實(shí)驗(yàn)驗(yàn)證了本文方法的有效性。未來還需要在以下方面開展研究。

一是客戶信息的隱私保護(hù)。未來需要開發(fā)基于智能終端的輕量級的隱私保護(hù)方法,確保感知者的通信錄、社交信息、軌跡與位置信息等不被泄漏。

二是交互信息的多樣化。本文中僅僅考慮了文本數(shù)據(jù)。實(shí)際上,聲音、圖片、視頻、表情等超文本元素在社交網(wǎng)絡(luò)中使用非常頻繁,這些元素在朋友間的表達(dá)感情方面越來越重要。這需要通過AI、語音識別、圖像理解等技術(shù),融合社交網(wǎng)絡(luò)中的全媒體信息,以便更精準(zhǔn)地刻畫朋友信息。

三是交互的時間維度。本文在分析交互內(nèi)容時,沒有考慮交互發(fā)生的時間因素,而時間因素往往具有重要意義。例如同樣的交互內(nèi)容,一個星期內(nèi)發(fā)生的可能比6個月前發(fā)生的更準(zhǔn)確。如果加入交互內(nèi)容的時間因素,方法會變得更加復(fù)雜,此時可以通過折中方法,給不同的采樣階段設(shè)置不同的權(quán)重。