采用社會網絡能力發現的眾包服務節點選擇算法

彭振龍,桂小林

(1.西安交通大學電子與信息學部,710049,西安; 2.泉州師范學院陳守仁商學院,362000,福建泉州; 3.西安交通大學陜西省計算機網絡重點實驗室,710049,西安; 4.泉州師范學院云計算物聯網電子商務智能福建省高校工程研究中心,362000,福建泉州)

眾包系統的質量控制始終是一個嚴峻挑戰[1-2]。一個眾包系統一般包括平臺、網絡、任務的發布者和任務的接受者。眾包平臺通常通過一定的激勵機制,吸引任務接受者參與眾包任務[3-5]。由于眾包系統的開放性、匿名性,導致可能存在很多的參與者不認真執行任務,而僅僅為了獲得獎勵,這一現象嚴重影響了眾包系統的效率和可信度[6-8]。控制眾包服務質量的基本策略主要有兩個:一是事后控制,即對眾包服務的結果進行篩查處理;二是事前控制,即對參與者的能力和誠信度進行評估,選擇更可靠更合適的參與者。本文從社會關系角度出發,選擇更合適、更可靠的參與者,從而提升眾包服務質量,屬于事前控制策略。

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

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

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

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

1 基于社會網絡的能力發現與任務傳播

1.1 社會網絡

社會網絡是由許多節點構成的一種社會關系結構,節點通常是指個人或組織,社會網絡代表各種社會關系,這些社會關系可以把從偶然相識的泛泛之交到緊密結合的家庭關系的各種人們或組織串連起來[24]。社會網絡內個體成員之間以任何形式進行的聯系稱為交互。交互能幫助社會網絡中的節點之間形成相對穩定的關系體系,進而影響節點的社會行為。

1.2 基本定義

每個節點都有其自身的屬性,如興趣愛好、專業特長等,并且對他的所有朋友都會有能力區分和認識,如認為某個朋友適合干什么、某個朋友對什么感興趣等。社會網絡中的一個節點用p表示,p的朋友數用m表示。眾包系統約定的能力類別數用n表示。任務參與者既包括任務發布者,又包括任務接受者。

定義1:能力。能力是完成一個項目或者任務所需要的基本技能或素質,用a表示。

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

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

(1)

(2)

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

(3)

定義6:朋友能力向量。社會網絡中的節點對其每個朋友在能力集合中對應的能力大小,構成該節點的一個朋友能力向量。如節點p與朋友pj之間的能力向量ep,pj可表示為

(4)

定義7:朋友能力矩陣。社會網絡中的某一節點的所有朋友能力向量,構成了該節點的朋友能力矩陣。節點p的朋友能力矩陣Ep可表示為

(5)

2 社會關系中基于內容的能力發現

2.1 參與者社會關系重構

結合式(1)(3)(5),可以將社會網絡中的節點p重新定義為一個三元組

p=〈hp,Cp,Ep〉

(6)

2.2 能力值的計算與更新

在能力值計算上,主要統計節點p與其朋友之間就某個關鍵詞的出現次數。如果某個關鍵詞出現在其朋友圈中,則以更大的權重計算。含加權朋友圈的能力值動態更新算法的偽代碼如下。

1:k=1;

2:Do whilek<=n

∥動態更新節點p的ak能力的能力值

5:k=k+1;

6:End Do;

2.3 含加權朋友圈能力的能力矩陣計算與更新

2.2節主要對節點p的能力值進行計算和更新,更新后可以生成一個1×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)和能力值與能力矩陣的計算與更新,節點p完成了對自己社會關系的重構,可重寫式(5)為

p=

(7)

3 仿真實驗及結果分析

微信是中國最流行的一款移動即時聊天工具,根據最近騰訊公布的2019年第一季度財報,微信月活躍用戶數量已正式突破了11億,同比增長達6.9%,2018年微信日均發送信息450億條。微信為用戶構建了一個龐大的社會關系。本文系統主要以微信交互數據為基礎,為了避免隱私泄漏,本文系統只允許在使用者授權同意的情況下,分析自己的聊天記錄和內容,對自己的朋友按主題類別進行能力區分,重構自己的社會關系。本文實驗模擬微信交互并進行數據分析。

3.1 數據準備

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

表1 能力分類及部分關鍵詞

3.2 能力發現

設定節點p有100個朋友,編號分別為1～100,本節重點介紹該節點的朋友能力矩陣Ep的生成過程。

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

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

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

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

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

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

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

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

圖1 部分節點1次采樣下不同主題的交互次數

圖2 部分節點5次采樣下不同主題的交互次數

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

圖4 5次采樣下加入朋友圈權重后不同主題的交互次數

3.3 候選傳播節點選擇

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

根據表6中數據,如果節點p想要發布能力編號為2的眾包任務,則應該在其好友列表中選擇編號為57、28、31、50……的朋友,這是因為這些朋友的能力屬性最為匹配。如果眾包任務需要多種能力,只需要對不同的能力設計相應的權重,即可找到最合適的朋友。實驗中,選擇了不同的能力要求,并設置了相應的權重,具體選擇的結果如表7所示。

表6 1次實驗得到的單能力候選節點排序表(以5次采樣數據為基礎)

表7 多能力及不同權重下的節點選擇結果

3.4 任務分發的時效性分析

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

第3節仿真實驗表明:本文系統能順利地按主題計算各個朋友的能力值大小,并進行采樣與更新,同時可以對朋友的誠信指數進行采集與計算更新,形成能力矩陣;對任意一個在能力集合內的眾包任務,都能正確選擇出最匹配的朋友,據此找到傳播候選節點并進行任務分發或數據回傳。

任何一個候選節點都可以重復以上步驟,經過若干次迭代,任務能在朋友圈中快速擴展,且朋友圈中的信任關系能被充分利用,在一定程度上增加了眾包參與者的可信度,從而提升了眾包的數據質量。

圖5 不同分發策略下完成任務的平均時間

4 結束語

眾包服務節點的選擇應綜合考慮其背景知識、社會關系、信譽度等多種屬性。本文方法首先需要對參與者進行能力發現,即從參與者日常在社交網絡中的交互內容、交互次數、交互頻率、朋友圈、加入的群、在群里的活躍度等信息中,對朋友的能力進行提煉,形成能力集合并對能力進行量化分級。通過評估參與者的社會關系和社區歸屬特性,利用參與者社會關系中隱含的天然信任關系,有針對性地完成任務的分發和后續數據的路由轉發。因為人們總是更愿意轉發與自己有社會關系的人的信息,所以通過社會關系找到的參與者候選集,比隨機選擇的參與者具有更高的精準性,仿真實驗驗證了本文方法的有效性。未來還需要在以下方面開展研究。

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

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

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