一種面向符號社交網(wǎng)絡(luò)的負鏈路預(yù)測方法

王 偉,薛苗苗,劉沫萌

(西安工程大學(xué) 計算機科學(xué)學(xué)院,陜西 西安 710048)

0 引 言

在現(xiàn)實社交網(wǎng)絡(luò)中,用戶之間的關(guān)系大致分為正面和負面,即節(jié)點之間的鏈路可以用正負號標(biāo)識,這種既有正鏈路又有負鏈路的社會網(wǎng)絡(luò)被稱為符號社交網(wǎng)絡(luò)。其中正鏈路表示正關(guān)系,如朋友、信任等關(guān)系;而負鏈路與正鏈路剛好相反,負鏈路表示負關(guān)系,如敵人、不信任關(guān)系等。目前,關(guān)于符號社交網(wǎng)絡(luò)的負鏈路預(yù)測研究相對較少。其主要原因在于:第一,大多數(shù)社交網(wǎng)絡(luò)更傾向于對用戶表達正面評價,而負面預(yù)測的數(shù)據(jù)集因涉及隱私等原因往往來源有限,這使得負鏈路的預(yù)測未得到足夠重視;第二,正面關(guān)系在網(wǎng)絡(luò)中具有傳遞性,而負面關(guān)系無法在網(wǎng)絡(luò)中進行傳遞,這給負鏈路預(yù)測的研究帶來很大的挑戰(zhàn)。盡管如此,負關(guān)系的挖掘及預(yù)測在許多現(xiàn)實應(yīng)用中具有極其重要的意義。例如,負面鏈接的預(yù)測可以提高推薦系統(tǒng)的性能[1-2],有助于在社交網(wǎng)絡(luò)平臺上尋找可信的用戶,還可幫助用戶避免欺詐或者矛盾爆發(fā)[3]等。

近年來,國內(nèi)外學(xué)者主要從基于結(jié)構(gòu)平衡理論和基于社會地位理論2個層面展開研究。在2種基本理論中,結(jié)構(gòu)平衡理論是人們對事物態(tài)度的平衡模型,該理論認為[4]:①我的朋友的朋友是我的朋友;②我的朋友的敵人是我的敵人;③我的敵人的朋友是我的敵人;④我的敵人的敵人是我的朋友。其中包括4種可能有的三元組關(guān)系,分為2種平衡關(guān)系和2種不平衡關(guān)系。而社會地位理論反映的是正負號的地位高低關(guān)系,即地位低的指向地位高的屬于正方向,而地位高的指向地位低的屬于負方向[5]。

針對上述2種理論,文獻[6-7]通過網(wǎng)絡(luò)拓撲分析了符號關(guān)系,并提供了有用的見解。在文獻[8]將2種理論結(jié)合起來在網(wǎng)絡(luò)結(jié)構(gòu)中進行符號預(yù)測,通過提取出23個特征來預(yù)測社交網(wǎng)絡(luò)中可能存在的正面和負面鏈接,其中包括基于度的7個特征和基于三角關(guān)系的16個特征,這是最早的基礎(chǔ)預(yù)測方法,但只是利用了局部信息[9]。在CHIANG等探索了提取網(wǎng)絡(luò)全局結(jié)構(gòu)特征的方法之后[10],YE等也從全局的角度并提供了新的遷移學(xué)習(xí)的網(wǎng)絡(luò)結(jié)構(gòu)信息提取方法[11]。張維玉等對連邊符號機理進行了深入分析,融合出一組最能反映連邊符號的特征,實驗表明較已有模型有了更好的預(yù)測效果[12]。上述研究都是使用了網(wǎng)絡(luò)結(jié)構(gòu)特征進行預(yù)測的,但僅利用這些網(wǎng)絡(luò)結(jié)構(gòu)信息仍存在一定的局限性[13]。例如,根據(jù)網(wǎng)絡(luò)上下文也可挖掘出不同的特征信息[14],故應(yīng)結(jié)合網(wǎng)絡(luò)上下文的信息綜合起來進行預(yù)測。ZOLFAGHAR 等將4個關(guān)鍵因素映射到相應(yīng)的可評估特征中進行符號預(yù)測,并根據(jù)結(jié)果發(fā)現(xiàn)了基于結(jié)構(gòu)的特征比上下文更重要[2]。BORZYMEK等結(jié)合網(wǎng)絡(luò)上下文的信息將特征分為2類,一類是基于圖的特征,一類是基于評述的特征,兩者結(jié)合達到了較好的效果[15]。

為克服現(xiàn)有負面數(shù)據(jù)集信息較少的問題,文獻[16]提出了負鏈路預(yù)測的NELP框架,利用網(wǎng)絡(luò)中的正鏈接信息和以內(nèi)容為中心的交互信息來預(yù)測負鏈接。文獻[17]提出基于元路徑特征的方法,考慮路徑長度對鏈路預(yù)測問題的影響,從而提升了負鏈路預(yù)測的效果。

本文以文獻[8]提出的負面預(yù)測方法為基礎(chǔ),結(jié)合現(xiàn)有的負鏈路預(yù)測方法,從改進預(yù)測性能的角度,考慮符號不同方面的屬性,抽取出更能反映節(jié)點和邊之間的符號特征組合,該方法可以歸類出4種與負符號相關(guān)的特征,將這4類特征進行融合并利用邏輯回歸算法進行實驗,提高了負鏈路預(yù)測的性能。

1 方法的提出

1.1 問題描述

給定一個有向圖G(V,E,P),其中V表示節(jié)點集,E表示邊集,P表示中邊對應(yīng)的符號集。P(i,j)∈P且P(i,j)={+1,-1,0}。用ei,j表示從i到j(luò)的邊,其中ei,j∈E,當(dāng)ei,j=1時,節(jié)點i到j(luò)之間存在鏈接;當(dāng)ej,i=1時,節(jié)點j到i之間存在鏈接;當(dāng)ei,j=ej,i=0時,節(jié)點i和j之間不存在鏈接。P(i,j)=+1表示邊ei,j的符號為正,P(i,j)=-1表示邊ei,j的符號為負,P(i,j)=0表示邊ei,j的符號未知。若其中一條邊符號未知,則可根據(jù)周邊的網(wǎng)絡(luò)鏈接狀態(tài)來進行預(yù)測。本文目標(biāo)就是要預(yù)測出P(i,j)=-1,即節(jié)點i到j(luò)之間存在負鏈接。

1.2 系統(tǒng)框架

負鏈路預(yù)測主要是預(yù)測未來哪些邊存在負面的關(guān)系,本文利用機器學(xué)習(xí)的技術(shù)將其看作有監(jiān)督學(xué)習(xí)的任務(wù)進行研究。所提出的鏈路預(yù)測框架如圖1所示。

圖 1 鏈路預(yù)測框架圖Fig.1 Link prediction framework diagram

圖1中,系統(tǒng)首先對用戶的節(jié)點特征、結(jié)構(gòu)特征、相似性特征和評分特征等4類特征進行提取;然后對特征進行融合,最后將問題看作為二分類問題來判別2個用戶是否存在負面關(guān)系[18],即預(yù)測社交網(wǎng)絡(luò)中存在負面鏈接的可能性。

2 特征構(gòu)造

特征提取與構(gòu)造是鏈路預(yù)測重要的部分之一[19]。本文抽取4大類特征，如下所述。

2.1 節(jié)點特征

依據(jù)文獻[20]對節(jié)點特征的描述,本文對于節(jié)點i不信任的節(jié)點集合(負出度)和不信任節(jié)點j的節(jié)點集合(負入度)定義如下:

O-(i)={j:(i,j)∈E,P(i,j)=-1}

(1)

I-(i)={j:(j,i)∈E,P(j,i)=-1}

(2)

O+(i)={j:(i,j)∈E,P(i,j)=1}

(3)

I+(i)={j:(j,i)∈E,P(j,i)=1}

(4)

式中:O-(i)和I-(i)分別為節(jié)點i不信任的節(jié)點集合,不信任節(jié)點i的節(jié)點集合;O+(i)和I+(i)為節(jié)點i信任的節(jié)點集合,信任節(jié)點i的集合。進一步地,通過特征變換構(gòu)造出以下節(jié)點度的特征。

1) 節(jié)點i的負出度占比C1(i)。C1(i)表示節(jié)點i出發(fā)的鏈接中負鏈接的比例,當(dāng)節(jié)點i出發(fā)的正負鏈接總數(shù)相同時,負鏈接的出度數(shù)越大,越有可能形成負鏈接,可表示為

(5)

2) 節(jié)點j的負入度占比C2(j)。C2(j)表示指向節(jié)點j的鏈接中負鏈接的比例,當(dāng)指向節(jié)點j的正負鏈接總數(shù)相同時,負入度越大,越有可能形成負鏈接，可表示為

(6)

2.2 結(jié)構(gòu)特征

根據(jù)2種基本理論,鏈接的結(jié)構(gòu)信息影響著符號預(yù)測。因此,本文使用三元組比率來表示鏈接的結(jié)構(gòu)信息。由于文獻[8]證明了不平衡的三元組將會導(dǎo)致符號社交網(wǎng)絡(luò)的不平衡,故本文采用負三元組特征。若節(jié)點i和j與共同鄰居持相反的態(tài)度,用社會心理學(xué)結(jié)構(gòu)平衡理論解釋就是“我敵人的朋友是我的敵人”,或者“我的朋友的敵人是我的敵人”。從該理論說明三元組關(guān)系中至少有一正一負2種邊的符號。為了在現(xiàn)實符號社交網(wǎng)絡(luò)中能保持平衡,則三元組就應(yīng)當(dāng)保持平衡。對于節(jié)點i、節(jié)點j和節(jié)點k之間的三元組關(guān)系(i,j,k),如果(i,k)的符號與(j,k)的符號不同,為了保持三元組(i,j,k)平衡,符號應(yīng)為負,但該三元組為正三元組;否則,三元組(i,j,k)不平衡,稱為負三元組。(i,j)的負三元組比是指節(jié)點i、節(jié)點j及其公共鄰居m之間的所有三元組中節(jié)點i、節(jié)點j及其公共鄰居之間的負三元組的比率，可表示為

(7)

式中:m為節(jié)點i和節(jié)點j的公共鄰居；|M|是i和j的公共鄰居的數(shù)目；I(·)為負三元組的數(shù)目，這需要s(i,k)和s(j,k)的符號不同。

2.3 相似性特征

本文采用余弦相似性表示兩節(jié)點間的相似性程度,根據(jù)2種負相似度[21]和Salton指標(biāo)來衡量,具體如下所述。

(8)

(9)

(10)

式中：ri,o和rk,o分別為從節(jié)點k和節(jié)點i指向節(jié)點o的鏈路符號；Oout為i和j都給出鏈接的節(jié)點集。

(11)

式中:ro,j和ro,k分別為從節(jié)點o指向節(jié)點j和k的鏈路符號；Oin為j和k都接收到的鏈接的節(jié)點集。

2) Salton指標(biāo)。Salton指標(biāo)是度量節(jié)點x和y之間的余弦相似性的指標(biāo)[19],可表示為

(12)

式中:Γ(i)是節(jié)點i的鄰居集合,|Γ(i)|是節(jié)點i的鄰居數(shù)。

2.4 評分特征R(i)

根據(jù)用戶接收的負面意見和正面意見,如果負面意見所占的比例越大,則該用戶越容易與其他人產(chǎn)生負面鏈接。評分特征采用負面評分比R(i)，可表示為

(13)

式中:b(i)為節(jié)點i接收到的負面意見數(shù)；g(i)為節(jié)點i接收到的正面意見數(shù)。

基于上述4類特征,符號預(yù)測模塊采用Logistic回歸模型,將從節(jié)點i指向節(jié)點j的鏈路符號分為2類:正的或負的。符號預(yù)測函數(shù)可表示為

(14)

3 算法描述

本文采用的面向符號社交網(wǎng)絡(luò)的負鏈路預(yù)測算法描述如下:

1) 加載數(shù)據(jù)集N,在矩陣(N1,N2,…,Nn-1)上對數(shù)據(jù)進行處理,得到新的矩陣M;

2) 對特征進行提取,得到特征矩陣P(Mi,Nj);

3) 應(yīng)用邏輯回歸分類器生成訓(xùn)練集和測試集;

4) 根據(jù)訓(xùn)練集訓(xùn)練分類器,進行負鏈路預(yù)測。

在算法中,首先加載數(shù)據(jù)集,進行數(shù)據(jù)預(yù)處理步驟,包括對數(shù)據(jù)進行清洗以及標(biāo)準(zhǔn)化等。接下來,對特征進行提取,構(gòu)造節(jié)點對的特征向量;然后對給定的數(shù)據(jù)集利用交叉驗證法對數(shù)據(jù)集進行劃分,劃分為訓(xùn)練集和測試集(8∶2),反復(fù)進行訓(xùn)練與測試,根據(jù)訓(xùn)練集選擇邏輯回歸分類器進行預(yù)測,進行最終的負鏈路預(yù)測。算法從時間復(fù)雜度上來說,實際環(huán)境中,由于節(jié)點的度數(shù)遵循指數(shù)分布,所以網(wǎng)絡(luò)中的平均鏈接個數(shù)不多且不會迅速增加。

4 實 驗

4.1 數(shù)據(jù)描述

本文采用Epinions和Slashdot來驗證該方法的性能。數(shù)據(jù)來自符號網(wǎng)絡(luò)常用數(shù)據(jù)集Epinions和Slashdot且公開,Epinions數(shù)據(jù)集是一個典型的消費者評論網(wǎng)站,用戶可以在該網(wǎng)站中創(chuàng)建對其他用戶的信任和不信任鏈接,其中1表示信任,-1表示不信任[22]。Slashdot是一個技術(shù)新聞評論網(wǎng)站,用戶可以通過評論和回復(fù)帖子對用戶表達積極或消極的意見,從而建立朋友或敵人的關(guān)系。對這2種網(wǎng)絡(luò)數(shù)據(jù)集進行數(shù)據(jù)預(yù)處理,過濾掉沒有任何積極或消極的聯(lián)系,得到的基本數(shù)據(jù)集信息進行了統(tǒng)計。其中,Epinions數(shù)據(jù)集的節(jié)點數(shù)為131 828,正鏈接和負鏈接數(shù)分別為717 702和123 670,三角形數(shù)為4 910 076;Slashdot數(shù)據(jù)集的節(jié)點數(shù)為82 144,正鏈接和負鏈接數(shù)分別為425 072和124 130,三角形數(shù)為579 565。

4.2 系統(tǒng)評估指標(biāo)

本文采用的符號預(yù)測方法屬于二元分類,對于已有的真實符號社交網(wǎng)絡(luò)中負鏈接的數(shù)量要遠遠小于正鏈接的數(shù)量,采用綜合評價指標(biāo)F1分數(shù)和精確率、召回率以及準(zhǔn)確率來作為評價標(biāo)準(zhǔn),將負鏈接作為正元組。通常用一個混淆矩陣來表示分類器的性能。其中TP是被正確識別的正元組的數(shù)量,FN是被錯誤識別為負類的正元組的數(shù)量,FP是被錯誤識別為正類的負元組的數(shù)量,TN是被正確識別的負元組的數(shù)量[23]。常用的分類器性能評價指標(biāo)包括本文要采用的精確率P、召回率R、準(zhǔn)確率A以及F1分數(shù),分別用如下公式計算：

(15)

(16)

(17)

(18)

4.3 實驗結(jié)果與分析

為了驗證特征融合方法的有效性,本文考慮將文獻[8]經(jīng)典方法中最基本的23個特征向量(all23)與本文提出的7大特征向量(new7)組合進行對比,在Epinions和Slashdot上進行測試,利用十折交叉驗證的方法,進行10次訓(xùn)練-測試過程,最終以計算10次過程中性能指標(biāo)的平均值作為結(jié)果。需要注意的是,本文實驗所采用的特征與文獻[8]所采用的特征顯著不同,所以需要驗證本文特征的有效性。利用上述4種指標(biāo)進行評估,結(jié)果如圖2、3所示。

(a) 精確率

(b) F1分數(shù)圖 2 精確率和F1分數(shù)的預(yù)測結(jié)果對比Fig.2 Comparison of prediction results of precision and F1 score

(a) 準(zhǔn)確率

(b) 召回率圖 3 準(zhǔn)確率和召回率的預(yù)測結(jié)果對比Fig.3 Comparison of prediction results between accuracy and recall

在圖2、3中,比較了4種不同的評價指標(biāo)在2個不同的數(shù)據(jù)集上測試的效果。在本文構(gòu)造的特征向量組合new7的性能相比于最初的23個特征向量all23的性能都有了一定的提高,其中精確率和F1分數(shù)提高比較明顯。在Epinions和Slashodot數(shù)據(jù)集上，精確率由原來的0.910 8、0.786 7提高到0.951 6、0.868 3，精確率在2個數(shù)據(jù)集上分別提高了約4.5%和10.4%,F1分數(shù)由原來的0.670 4、0.589 4提高到0.853 4、0.775 3，分別提高了約27.3%和31.5%。這是因為與本文使用的特征向量有很大關(guān)系,在實際的符號社交網(wǎng)絡(luò)中,各個特征指標(biāo)對鏈接的形成做出的貢獻不同,最初的23個特征向量中并不是所有的特征都對鏈接的形成起著一定的作用,本文對特征的規(guī)模進行縮小,抽取出更能反映節(jié)點和邊的特征組合,可見對特征進行選擇是非常有必要的。

另外,為了分析評分特征對結(jié)果的影響,本文將準(zhǔn)確率和F1分數(shù)作為評價標(biāo)準(zhǔn),分別在數(shù)據(jù)集Epinions和Slashdot上進行評估,其結(jié)果如圖4所示。

由圖4可以看出,不管是準(zhǔn)確率還是F1分數(shù)值,在去掉評分特征之后,預(yù)測效果有所下降,這說明本文提出的評分特征可有效提升鏈路預(yù)測的效果。這是因為負面交互與負面鏈接大多有著相關(guān)性,用戶對彼此表達負面評分的數(shù)量越多,會促進負鏈接的形成。一方面說明了提取符號網(wǎng)絡(luò)中上下文信息特征是有效的；另一方面驗證了將網(wǎng)絡(luò)結(jié)構(gòu)和上下文信息進行融合能夠更好的進行預(yù)測。此外,缺少評分特征對應(yīng)的預(yù)測結(jié)果相比采用全部特征的預(yù)測結(jié)果降低的幅度較低,這可能是因為提供連邊信息具有重疊性,特征之間也存在著許多相似性。

(a) 準(zhǔn)確率

(b) F1分數(shù)圖 4 評分特征對準(zhǔn)確率和F1分數(shù)的影響Fig.4 The impact of scoring features on accuracy and F1 score

綜上所述,與已有的方法相比,該方法具有更好的預(yù)測效果,說明將網(wǎng)絡(luò)結(jié)構(gòu)和上下文信息融合在一起可獲得更多有利于符號預(yù)測的信息,預(yù)測結(jié)果顯著提高。

5 結(jié) 語

針對符號社交網(wǎng)絡(luò)的負鏈路預(yù)測研究中存在未充分利用各個特征的優(yōu)勢,以致預(yù)測性能較低的問題,本文在已有特征的基礎(chǔ)上進行融合,提出一種新的面向符號社交網(wǎng)絡(luò)負鏈路預(yù)測方法,并在2個真實的社交網(wǎng)絡(luò)數(shù)據(jù)集上進行了有效性驗證,達到了性能提升的效果。該方法挖掘出了符號形成的幾個關(guān)鍵因素,可明顯改善負鏈路預(yù)測的效果。由于在不同網(wǎng)絡(luò)中特征對鏈接信息形成所做的貢獻有所差異,在后續(xù)研究中,將把挖掘其他有效的特征以及對特征進行重要性排序作為重點。