陽 雨,胡亞洲,郭 勇,鄧 波

(北京系統(tǒng)工程研究所,北京 100101)

0 概述

隨著移動互聯網的發(fā)展,在線社交網絡[1]在人們生活中扮演著重要的角色。人們通過在線社交平臺(如微博、微信、QQ等),不僅能夠維護社交網絡中的好友關系,而且可以更加便捷地獲取感興趣的信息。在社交網絡中,人們不僅傾向于關注已認識的朋友,而且希望與興趣相似的新朋友建立聯系[2]。因此,在線社交網絡平臺相繼推出好友推薦服務,例如,QQ推出“可能認識的人”服務,微博推出“可能感興趣的人”“可能喜歡的大咖”等推薦服務。社交網絡好友推薦主要有基于鏈接和基于內容2種基本推薦形式?；阪溄拥耐扑]方式是根據用戶之間的網絡鏈接關系,利用基于鏈接的用戶權威度排序算法(例如PageRank[3]、HITS[4]、TrustRank[5]等)或其變形進行好友推薦;基于內容的推薦方式則是根據標簽、關鍵詞、地理位置等信息進行相似性推薦[6-7]。

盡管在線社交平臺提供不同的推薦服務,但是普遍缺乏對推薦好友信任度和實時性的分析,時常存在推薦的好友并不是用戶最希望建立鏈接的情況。同時,用戶的互動和轉發(fā)行為是在線社交平臺信息傳播的重要途徑,用戶之間的信任度是影響互動和轉發(fā)行為的重要因素。因此,在線社交網絡中用戶信任成為需要關注的重要問題。但是,目前針對用戶信任度的研究大多是直接對用戶信任度量化,缺乏對于用戶信任度傳遞的建模和分析。

針對上述問題,本文建立在線社交網絡的用戶信任傳遞模型。首先通過分析鄰接用戶之間的共同好友、互動關系、互動時間等因素對鄰接用戶信任度進行量化,將量化結果作為鏈接邊權值;然后根據鏈接關系計算2個用戶之間的信任值;最后結合好友鏈接的建立和互動情況對構建的信任傳遞模型進行評估。

1 相關工作

目前,在線社交平臺中的用戶可信度引起了學術界的廣泛關注。文獻[8]提出了基于局部信息的信任推薦系統(tǒng),該系統(tǒng)通過計算朋友之間的信任度進行推薦,能夠有效解決冷啟動等問題;文獻[9]對資源層和屬性層的信任進行研究,驗證了信任對于推薦準確度的影響;文獻[10]提出基于信任的個性化推薦方法;文獻[11]利用微博內容的可信度來描述用戶的可信度;文獻[12]分析了Tweet可信度感知結果,同時對特征用戶對可信度評估的影響進行分析;文獻[13]通過人工評估的方法對Tweet信息的可信度進行評估分析;文獻[14]提出一種基于信任隱私保護的好友推薦方法,該方法通過研究用戶和推薦者之間的鏈接信任關系,同時考慮略去用戶的隱私信息進行好友推薦;文獻[15]提出基于信任概率的推薦模型,該模型將用戶之間興趣的相似程度作為轉移到目標節(jié)點的轉移概率,以驅動商品推薦;文獻[16]則將用戶間的相似性和可信度納入社區(qū)演化的分析研究中。

此外,文獻[17]將用戶間的好友關系強度定義為信任度并引入到相鄰邊拓撲信息相似性計算中,結合用戶興趣模型導出用戶社交圈,提出一種好友推薦算法;文獻[18]利用用戶之間信息的相似度進行用戶聚類,提出了一種基于用戶信息的社交網絡信任評估方法;文獻[19]針對當前社交網絡中基于用戶信任的Web服務推薦算法覆蓋率不足的問題,提出了一種新的混合信任度算法,用以解決因單一信任度算法數據稀疏性造成推薦結果不佳的問題;文獻[20]針對數據稀疏問題和聯系不可靠現象對傳統(tǒng)社交網絡推薦帶來的影響,提出一種基于信任關系重建和社交網絡傳遞的推薦算法。

通過分析可知,當前研究工作存在以下問題:1)研究重點關注信任的分析、度量,缺乏對于信任在鏈接網絡中傳遞的考慮;2)未考慮信任度會隨著時間的變化而衰減變化的特性,從而影響用戶的行為和好友推薦的準確度;3)未將用戶間的互動性納入到用戶間信任度量中。

2 建模分析

為建立用戶信任傳遞模型,本節(jié)從用戶鏈接、用戶信任和信任傳遞3個方面對信任傳遞中的基本問題和概念進行分析。

2.1 用戶鏈接

在線社交網絡平臺中的眾多不同用戶通過用戶之間好友關系建立鏈接。如果2個用戶是好友關系,則兩者之間有一條邊。因此,在線社交網絡平臺的用戶鏈接網絡可以用G=(N,E)表示,其中,N為鏈接網絡中所有用戶節(jié)點集合,E為鏈接網絡中所有邊的集合。為形式化描述鏈接網絡,以圖1中用戶節(jié)點A為例,A的好友集合為{B,C,D,E}。

圖1 用戶鏈接網絡

為方便下文描述,本文定義k跳好友和陌生人的概念。

定義1(k跳好友) 從原始用戶節(jié)點經過最短k條邊到達的目標用戶節(jié)點,稱為原始用戶節(jié)點的k跳好友。如圖1中,用戶節(jié)點B為A的1跳好友,用戶節(jié)點I為A的3跳好友。

定義2(陌生人) 從原始用戶節(jié)點不能經過有限條邊到達目標用戶節(jié)點的用戶,稱為原始用戶節(jié)點的陌生人。如圖1中,用戶節(jié)點J為A的陌生人。

本文使用鄰接矩陣T來描述用戶社交網絡的鏈接關系,如果用戶1加用戶2為好友(或是用戶1關注用戶2),則鄰接矩陣元素T12=1且T21=1,否則T12=0。圖1中所示用戶鏈接網絡的鄰接矩陣如下:

可以看出上述矩陣是對稱矩陣,即對于用戶i和用戶j,有Tij=Tji。

2.2 用戶信任

信任是指相信對方是誠實、可信賴的,通常用于描述2個用戶之間的特征,在社交網絡平臺中,用戶之間的信任很難被直觀量化。文獻[21]針對單一用戶的可信值進行分析研究,但是沒有考慮到用戶信任是2個用戶之間的關系特征。本文將用戶信任作為2個用戶之間關系好壞的評價指標,用戶信任會影響用戶之間的互動行為和用戶鏈接網絡的改變,將T1→2記作用戶1對于用戶2的信任值。

類比真實社交網絡可以發(fā)現,當兩用戶間的共同好友越多、互動越多、興趣點越相似時,可以認為兩用戶是越親密、越信任的。以圖1中用戶A、B為例,當A和B擁有較多共同好友和共同興趣,且A和B經常相互轉發(fā)、評論、點贊時,可以認為A、B之間信任值TA→B和TB→A較高。同時,兩用戶之間的信任會隨著時間的變化而變化。例如,當A、B之間長時間沒有互動,則可以認為A、B的信任值TA→B和TB→A比A、B經常互動時低。

2.3 信任傳遞

在社交網絡中,人與人之間的信任具有傳遞性,以圖1中A、E、G為例,A與E是好友,E與G是好友,則A對E的信任值TA→E經E和G的鏈接傳遞到給G,形式化表述為:

TA→G=TA→E?TE→G

(1)

其中,TA→G、TA→E、TE→G分別為AG、AE和EG之間的信任值,?是信任傳遞運算符。

信任值具有可合并特征,以圖1中A、B、C、H節(jié)點為例,A與H的信任值可以表述為:

TA→H=TA→B?TB→H⊕TA→C?TC→H

(2)

其中,⊕是信任合并運算符。

3 信任傳遞模型

本節(jié)提出一種信任傳遞模型,該模型基于用戶鏈接網絡和用戶社交信息,通過用戶之間的信任和衰減因子,對源用戶和目標用戶之間的信任值進行評估。

3.1 模型流程

如圖2所示,信任傳遞模型主要包括用戶信任計算和信任傳遞分析兩部分內容。

1)用戶信任計算是通過分析用戶鏈接網絡和用戶社交信息,對具有好友關系(1跳好友)的用戶之間信任值進行度量分析。

2)信任傳遞分析是通過分析信任值在鏈接網絡中的傳播規(guī)律,計算源用戶節(jié)點對目標用戶節(jié)點的信任值。

信任傳遞分析的結果同時可以反饋給用戶鏈接網絡和用戶社交信息。例如,計算出源用戶節(jié)點到目標用戶節(jié)點之間的信任值之后,可以給源用戶節(jié)點進行好友和熱門信息的推送,從而影響用戶鏈接網絡的結構和用戶社交信息的內容。

圖2 信任傳遞模型框圖

3.2 用戶信任計算

用戶信任計算是對具有好友關系(1跳好友)的用戶之間信任值進行度量評估,是信任傳遞模型中重要的部分。

用戶之間的信任值可以從親密度、互動情況和時間衰減三方面考慮,表示為:

Trustij=(Siij,Inij,Atij)

(3)

其中,Trustij是用戶i對用戶j的信任值,Siij是用戶i、j之間的親密度,Inij反映了用戶i、j之間的互動情況,Atij是用戶i、j之間的時間衰減因素。下面對這三方面進行詳細介紹。

1)用戶親密度

用戶親密度用于描述用戶i、j之間的社交關系中的親密性和相似程度,包括用戶之間的共同好友和共同興趣。通過分析可知:當用戶之間的共同好友越多時,用戶之間的社交重疊越大,用戶之間的社交信任值越高;當用戶之間的共同興趣越多時,用戶相似度越高,用戶之間的信任值越高。

假設用戶i的所有好友集合為Fi,關注的興趣集合為Ii,用戶j的所有好友集合為Fj,關注的興趣集合為Ij,則用戶i、j之間的共同好友為Fi∩Fj,用戶i、j之間的共同興趣為Ii∩Ij。因此,用戶i對用戶j的親密度可以表述為:

(4)

2)用戶互動情況

用戶之間的互動情況是用戶信任程度的重要體現,在其他條件相同的情況下,用戶之間互動越密切,可以認為用戶之間信任程度越高。

在線社交網絡之間常見的用戶互動行為包括轉發(fā)、評論和點贊。轉發(fā)是指用戶將別人發(fā)布的內容轉載成自己的內容;評論是指對別人的內容發(fā)表自己的看法;點贊是指對別人發(fā)布的內容表示贊同、贊許。文獻[21]對微博用戶的轉發(fā)行為進行了分析,指出用戶的轉發(fā)行為與轉發(fā)來源的關系。

假設用戶i從好友處轉發(fā)的狀態(tài)數目總和為Ni,從好友j處轉發(fā)的狀態(tài)數目為Nij,用戶i給所有好友評論次數總和為Ci,給好友j評論次數為Cij,用戶i給所有好友點贊次數總和為Pi,給好友j點贊次數為Pij,則用戶i對用戶j的互動情況可以表述為:

(5)

其中,α、β、λ代表轉發(fā)、評論和點贊在互動情況中重要性的比例。根據對真實社交網絡的研究可以發(fā)現,轉發(fā)、評論和點贊行為對用戶互動情況重要性的影響是依次遞減的,因此,實驗中設定轉發(fā)、評論和點贊行為的重要性比例為α=0.5,β=0.3,λ=0.2。

3)時間衰減

時間衰減因素是指用戶之間的信任關系會隨近期交互時間而衰減變化。如果2個用戶近期經常有互動行為(轉發(fā)、評論和點贊),則2個用戶的信任程度較高;反之,如果2個用戶之間很久沒有交互,則其間信任程度會降低。因此,本文引入時間衰減因素Atij來描述用戶信任程度隨時間而變化的規(guī)律,如下式所示:

Atij=e-kt

(6)

其中,k是參數,t是用戶i和用戶j之間最后一次交互距信任值計算時刻的時間間隔(單位為d)。根據實驗結果分析,當實驗中設置k=-1/1000時,可以較好地反映時間衰減因素Atij相對時間的變化規(guī)律。

為量化用戶i對用戶j的信任值Trustij,同時考慮到用戶i和用戶j之間的親密度、互動情況和時間衰減因素均會對用戶i、j產生影響,本文使用量化公式如下:

Trustij=Siij·Inij·Atij

(7)

3.3 信任傳遞分析

信任傳遞分析主要包括3個步驟:信任值歸一化,鏈接路徑搜索和信任值計算。

2)鏈接路徑搜索:在用戶鏈接網絡中搜索從源用戶到目標用戶的所有無環(huán)路徑,路徑集合為EE。鏈接路徑搜索是后續(xù)信任值計算的基礎。本文使用改進的廣度優(yōu)先搜索算法,即從源節(jié)點搜索到目標節(jié)點時不直接返回,而是遍歷所有無環(huán)鏈路之后返回所有路徑集合EE。

3)信任值計算:依據鏈接路徑搜索結果和鏈接傳播規(guī)律,計算從源用戶到目標用戶之間的信任值。

用戶信任值計算具體過程如算法1所示。

算法1用戶信任值計算算法

輸入用戶社交網絡G和參數α、β、λ、k、αa

輸出用戶信任值矩陣Ts

1.Initialize α,β,λ,k,αa

2.for?Tij∈T//計算鄰接好友間信任值

3.if Tij==1

4.calculate Trustij

5.end if

6.end for

7.for?Tij∈T //信任值歸一化

9.end for

10.if Tij==1//用戶i、j為1跳好友

12.else

13.find EEij//鏈接路徑搜索

14.for eek∈EEij//信任計算

16.end for

17.end if

18.return Ts

4 實驗與結果分析

4.1 實驗設置

由于微博數據相對開放并易于獲取,本文基于微博數據開展用戶信任傳遞建模研究。

實驗首先通過新浪微博的API接口,選取10個活躍的用戶作為種子節(jié)點,以用戶的鏈接關系共計爬取12 648個用戶數據。由于大V用戶在信任傳遞中具有意見領袖作用,同時微博好友和粉絲數嚴重不對等,因此在實驗中不對大V用戶的信任傳遞進行分析。同時,根據以下條件篩選出不活躍用戶:1)好友總數和關注好友總數均小于20;2)用戶轉發(fā)、評論和點贊微博數均小于20;3)用戶超過1個月沒有微博或好友數據更新。最后得到2 034個用戶,共計486 921條微博數據。

實驗采用文獻[21]中提出的微博分析方法,對用戶微博數據的轉發(fā)、評論和點贊進行處理,以對用戶互動情況進行量化分析。

實驗采用交叉驗證的方法,將數據集分為訓練集(Train)和測試集(Test)兩部分,比例分別為80%和20%。針對從新浪微博獲取的數據集中的好友數據和微博數據,對于單個用戶來說,可以將該數據集分為好友數據集和微博數據集,使用全部好友和微博數據的前80%作為訓練集,后20%數據作為測試數據集。

4.2 評價指標

為評價用戶信任傳遞模型的有效性,本文使用的評價指標包括準確率Precision、召回率Recall、F1值F1-score和平均逆序數Invave。這4種評價指標的定義如下:

(8)

(9)

(10)

(11)

其中,Trustk為信任值排序集合,Inve是逆序對數。

準確率、召回率和F1值是為了分析信任傳遞模型對用戶好友添加、互動行為預測而引入的評價指標。

平均逆序數是為了評價信任傳遞中信任值大小排序問題而引入的評價混亂度的指標。當平均逆序數較小時,一定程度上反映信任傳遞中信任排名的正確程度較高;反之則反映信任排名的正確程度較低。

4.3 結果分析

圖3為信任值傳遞結果,從圖3中可以看出,隨著好友跳數的增加,用戶信任值會迅速下降,當好友跳數為3時,好友信任值總和會下降到0.4以下。實驗結果也驗證了用戶對好友以及好友的好友信任度較高,對跳數較遠的人信任度較低的現象。同時可以發(fā)現,隨著衰減因子的增加,相同跳數的用戶信任值也相應降低。由此可知,信任衰減因子越大,用戶的信任值傳遞下降得越快。

圖3 信任值傳遞結果

表1給出了在不同測試集中用戶信任值傳遞的分析結果,下文將針對好友數據集和微博數據集分別開展分析。

表1 數據集分析結果

針對好友數據集,如圖4所示,隨著數據量的增大,用戶信任傳遞分析的添加好友準確率逐漸下降,召回率不斷升高,F1值在兩者之間,呈現先增加后減少的趨勢,平均逆序對數則呈現逐漸增大的趨勢。由此可知,當取測試集中前一部分好友時,用戶信任傳遞分析的結果準確率較高,同時對于好友添加順序的分析準確度也越高。

圖4 好友數據集分析結果

針對微博數據集,如圖5所示,隨著數據集數據量的增大,用戶信任值傳遞分析的用戶互動行為的準確率、召回率和F1值變化規(guī)律和好友數據集類似,但是平均逆序數的變化規(guī)律和好友數據集的變化不同,隨著數據集增大,平均逆序數變化規(guī)律呈遞減趨勢。通過分析可知,由于用戶信任傳遞分析的是用戶互動行為,互動行為的排名隨數據集的增大而變得與測試集的規(guī)律更相近,因此,平均逆序數會呈現遞減的變化規(guī)律。

圖5 微博數據集分析結果

5 結束語

用戶信任值是用戶在社交網絡中行為的重要影響因素,然而目前針對在線社交網絡的研究,缺乏對用戶信任及其傳遞規(guī)律的研究分析。為此,本文建立了在線社交網絡的用戶信任傳遞模型。首先通過分析用戶信任值影響因素,量化用戶信任值;然后根據鏈接關系,建立信任傳遞模型并進行評估分析?；趯ξ⒉祿姆治隹芍?信任傳遞模型能夠準確描述好友之間的信任傳遞,對好友互動和好友建立具有較好的預測和推薦意義。

本文建立的信任值量化模型主要依據用戶親密度、互動行為和時間衰減因素,然而在實際在線社交網絡中,信任值的影響因素可能不止這3種,未來將研究如何科學、合理地對用戶信任值進行量化分析。同時,信任傳遞模型基于圖搜索算法,當用戶數量增大時,算法執(zhí)行時間會迅速增長。因此,優(yōu)化、改進信任傳遞算法也是下一步的研究方向。