徐 娟，張 迪，錢文華

1.云南大學(xué) 檔案館·黨史校史研究室，昆明 650091

2.云南財經(jīng)大學(xué) 人事處，昆明 650221

3.云南大學(xué) 信息學(xué)院，昆明 650504

概率圖模型在社交網(wǎng)絡(luò)用戶相似性發(fā)現(xiàn)中的應(yīng)用*

徐 娟1，張 迪2，錢文華3+

1.云南大學(xué) 檔案館·黨史校史研究室，昆明 650091

2.云南財經(jīng)大學(xué) 人事處，昆明 650221

3.云南大學(xué) 信息學(xué)院，昆明 650504

+Corresponding autho author:r:E-mail:qwhua003@sina.com

XU Juan,ZHANG Di,QIANWenhua.Application of probabilistic graphicalmodel for discovering user sim ilarity in socialnetwork.Journalof Frontiersof Computer Scienceand Technology,2017,11(7)：1056-1067.

社交網(wǎng)絡(luò)中的用戶相似性發(fā)現(xiàn)作為社交媒體數(shù)據(jù)分析中的基礎(chǔ)研究，可以應(yīng)用于基于用戶的商品推薦以及社交網(wǎng)絡(luò)中推導(dǎo)用戶關(guān)系演化過程等。為了有效地描述社交網(wǎng)絡(luò)用戶間復(fù)雜的相關(guān)性及不確定性，并從理論上提高海量社交網(wǎng)絡(luò)用戶相似性發(fā)現(xiàn)的準(zhǔn)確度，研究了基于貝葉斯網(wǎng)這一重要的概率圖模型，結(jié)合網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和用戶之間的依賴程度，發(fā)現(xiàn)社交網(wǎng)絡(luò)用戶相似性的方法。為了提高算法的可擴(kuò)展性，解決海量數(shù)據(jù)帶來的存儲和計算問題，提出了基于Hadoop平臺的貝葉斯網(wǎng)分布式存儲以及并行推理方法。最后通過實驗結(jié)果驗證了算法的高效性和正確性。

社交網(wǎng)絡(luò)；貝葉斯網(wǎng)；用戶相似性；并行推理；Hadoop

1 引言

隨著社交網(wǎng)絡(luò)的迅速發(fā)展，規(guī)模急劇增大，社交網(wǎng)絡(luò)所包含的用戶基本數(shù)據(jù)信息劇增，使得社交網(wǎng)絡(luò)成為一個擁有海量數(shù)據(jù)的數(shù)據(jù)源。通過對海量社交網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行分析研究可以發(fā)現(xiàn)數(shù)據(jù)中潛在的價值，進(jìn)而可以幫助人們研究用戶間的交互行為以及相似用戶的共同行為。社交網(wǎng)絡(luò)用戶相似性發(fā)現(xiàn)作為一項基礎(chǔ)研究，有助于理解用戶之間的關(guān)系演化，同時提煉出一種尋找最優(yōu)商品推薦的方法等[1-3]。近幾年國內(nèi)外研究者為發(fā)現(xiàn)社交網(wǎng)絡(luò)中的相似用戶提出了多種方法。Pirasteh等人[3]提出了一種基于矩陣因子分解的用戶相似性度量方法，旨在為相似性評分?jǐn)?shù)量較少的用戶提供一種有效的非對稱的用戶相似性度量方法。Gan等人[4]首先基于用戶的歷史數(shù)據(jù)獲得一個用戶相似性矩陣用于表示用戶之間的直接相似性，然后通過冪率調(diào)整、最近鄰居構(gòu)建、閾值過濾3種策略對相似性矩陣進(jìn)行調(diào)整，降低了稀疏矩陣對算法準(zhǔn)確度的影響。Agarwal等人[5]首先根據(jù)進(jìn)化算法獲得反映用戶偏好的參數(shù)集合，以參數(shù)集合為數(shù)據(jù)基礎(chǔ)得到參數(shù)相似性，同時結(jié)合用戶交互強(qiáng)度提出了一種隱式評分模型計算用戶關(guān)系的相似性。Bhattacharyya等人[6]構(gòu)建了一種模型根據(jù)用戶檔案數(shù)據(jù)計算用戶之間的語義相似性關(guān)系，在此模型的基礎(chǔ)上定義了一種用戶相似性函數(shù)計算用戶之間的相似性。Nisgav等人[7]提出了基于協(xié)同過濾的方法發(fā)現(xiàn)社交網(wǎng)絡(luò)中的相似性用戶。Greene等人[8]提出了基于打分的相似性搜索方法進(jìn)而研究社區(qū)的演化。Scott等人[9]利用鏈接預(yù)測的方法實現(xiàn)了相似性搜索。

但以上方法只考慮了用戶之間直接相似性而忽略了間接相似性對用戶相似性的影響，然而在實際生活中這種間接相似性具有不可忽視的影響，這就導(dǎo)致了以上算法準(zhǔn)確度較低。為了提高用戶相似性發(fā)現(xiàn)的準(zhǔn)確度，提出一種能夠同時獲得直接相似性和間接相似性對用戶相似性影響的模型顯得尤為重要。幸運(yùn)的是，貝葉斯網(wǎng)（Bayesian network，BN）作為概率圖模型的典型代表，能夠有效地表示和推理不確定知識。BN是以隨機(jī)變量為節(jié)點的有向無環(huán)圖（directed acyclic graph，DAG），每個節(jié)點對應(yīng)一張反映變量間相互依賴關(guān)系的條件概率表（conditional probabilitytable，CPT）。通過構(gòu)建BN可以有效地描述數(shù)據(jù)之間的直接相關(guān)性和相互依賴關(guān)系，同時通過BN推理可以進(jìn)一步發(fā)現(xiàn)數(shù)據(jù)之間的間接聯(lián)系，為海量社交網(wǎng)絡(luò)數(shù)據(jù)中的用戶相似性發(fā)現(xiàn)提供了重要的工具。因此，為了提高算法的準(zhǔn)確度，本文以BN為模型發(fā)現(xiàn)社交網(wǎng)絡(luò)中的相似用戶。

近年來，BN作為一種不確定知識表示和推理的有效方法被應(yīng)用于用戶相似性發(fā)現(xiàn)領(lǐng)域，并取得了良好的效果。Abdo等人[10]基于BN推理提出了一種有效的用戶相似性度量算法。Nillius等人[11]基于貝葉斯網(wǎng)推理和圖約束定義了孤立目標(biāo)之間的相似性度量，有效地解決了多目標(biāo)追蹤中的標(biāo)記目標(biāo)身份問題。

然而以上提出的算法雖然對集中式單節(jié)點的運(yùn)行環(huán)境具有較好的適應(yīng)性，但無法很好地適應(yīng)海量社交網(wǎng)絡(luò)數(shù)據(jù)規(guī)模大及分布式存儲的需求。為了解決這一問題，提高算法的可擴(kuò)展性，本文基于Hadoop平臺實現(xiàn)了相應(yīng)的算法。本文的主要貢獻(xiàn)如下：

（1）基于MapReduce編程框架從海量社交網(wǎng)絡(luò)數(shù)據(jù)中構(gòu)建得到社交用戶貝葉斯網(wǎng)（socialuser Bayesian network，SUBN），發(fā)現(xiàn)社交網(wǎng)絡(luò)用戶之間的直接相似性關(guān)系，給出一種基于MapReduce的SUBN構(gòu)建算法。

（2）由海量社交網(wǎng)絡(luò)數(shù)據(jù)得到的社交用戶貝葉斯網(wǎng)本身也是大規(guī)模數(shù)據(jù)源，為更好地支持SUBN推理以及算法的高效性，本文提出了基于HBase存儲貝葉斯網(wǎng)的方法，基于這種合理的存儲結(jié)構(gòu)，準(zhǔn)確、高效地完成SUBN數(shù)據(jù)的查詢和計算工作。

（3）結(jié)合SUBN結(jié)構(gòu)和SUBN推理間接相似性，提出了一種社交網(wǎng)絡(luò)用戶間接相似性發(fā)現(xiàn)方法。該方法有效提高了社交網(wǎng)絡(luò)用戶相似性發(fā)現(xiàn)算法的準(zhǔn)確度，為海量社交網(wǎng)絡(luò)數(shù)據(jù)中的用戶相似性發(fā)現(xiàn)提供了必要的技術(shù)支撐。同時，基于MapReduce提出了一種在BN數(shù)據(jù)分布式存儲情況下實現(xiàn)BN并行推理的方法。該方法可以充分利用MapReduce所具備的良好的并行計算能力，在很大程度上提高了推理效率，同時也提高了基于BN的用戶相似性度量算法的可擴(kuò)展性。

本文組織結(jié)構(gòu)如下：第2章介紹了基于BN的社交網(wǎng)絡(luò)用戶建模方法；第3章詳細(xì)講述了基于BN的用戶相似性度量方法；第4章給出了實驗結(jié)果和性能分析；第5章總結(jié)全文，并對未來工作進(jìn)行了展望。

2 基于貝葉斯網(wǎng)的社交網(wǎng)絡(luò)用戶模型構(gòu)建及分布式存儲實現(xiàn)

2.1 相關(guān)定義

BN是一個有向無環(huán)圖DAG，記為G=(V,E)，其中V是節(jié)點的集合，每個節(jié)點代表一個隨機(jī)變量。E是有向邊的集合，若存在一條邊A→B，則稱A是B的父節(jié)點（A,B∈V且A≠B）。每個節(jié)點對應(yīng)一個CPT用來量化父節(jié)點對子節(jié)點的影響。假設(shè)U={A1,A2,…,Am}，T={t1,t2,…,tn}，ti={Ati1,Ati2,…,Atik}，Atik∈U ，1≤k≤m分別表示社交網(wǎng)絡(luò)中的用戶集合、實體集、與實體有交互行為的用戶集合，以用戶集合作為DAG的節(jié)點。根據(jù)BN的定義給出了SUBN的定義如下。

定義1（社交用戶貝葉斯網(wǎng)）用一個二元組R=(Gu,S)表示，其中：

（1）Gu=(U,E)為貝葉斯網(wǎng)的DAG結(jié)構(gòu)，其中U={A1,A2,…,Am}，每個Ai對應(yīng)一個社交網(wǎng)絡(luò)用戶，任一個用戶Ai的取值可以為1或0，分別表示用戶Ai是否與實體ti有交互行為，E表示用戶之間是否存在相似關(guān)系邊。

（2）S={p(Ai|Pa(Ai)),Ai∈U)}為條件概率值的集合，Pa(Ai)是Ai的父節(jié)點。S由各用戶節(jié)點對應(yīng)的CPT構(gòu)成，p(Ai|Pa(Ai))是指在Pa(Ai)發(fā)生的情況下Ai發(fā)生的概率。

2.2 基于MapReduce的社交用戶貝葉斯網(wǎng)模型的構(gòu)建

在SUBN的DAG構(gòu)建過程中需要解決兩個問題：（1）如何確定兩個用戶之間是否存在相似關(guān)系的邊；（2）如何確定相似關(guān)系的方向，即用戶之間邊的指向。針對問題（1），對于任意兩個用戶，通過考慮同時與兩個用戶有交互行為的實體數(shù)占其中與任何一個用戶有交互行為的實體數(shù)的比例值來確定用戶之間的相似度，若該值達(dá)到某個確定的閾值，則說明兩個用戶之間存在相似關(guān)系，即存在邊。Ai與Aj之間的直接相似度值用sim(Ai,Aj)表示：

其中，Num(Ai=1,Aj=1)表示同時與用戶 Ai和 Aj具有交互行為的實體的個數(shù)；分母表示與用戶Ai或用戶Aj具有交互行為的實體的個數(shù)。

設(shè)ε為給定的相似度閾值，則當(dāng)sim(Ai,Aj)＞ε時，表示用戶Ai與Aj具有相似性關(guān)系，即 Ai與 Aj之間存在邊。

針對問題（2），對于任意兩個有邊相連的用戶Ai、Aj，通過比較Ai在Aj出現(xiàn)的情況下出現(xiàn)的概率與Aj在Ai出現(xiàn)的情況下出現(xiàn)的概率來確定相似性邊的指向。Ai在Aj出現(xiàn)的情況下出現(xiàn)的概率用P(Ai|Aj)表示，反之用P(Aj|Ai)表示：

其中，N(Ai=1)、N(Aj=1)表示與Ai、Aj有交互行為的實體的個數(shù)。若P(Ai|Aj)＞P(Aj|Ai)，則表示Ai對Aj的影響大于Aj對Ai的影響，因此邊的方向由Aj指向Ai。通過以上方法可以得到SUBN的DAG結(jié)構(gòu)，接著基于MapReduce編程框架利用最大似然估計方法獲得SUBN的CPT。P(Ai|Pa(Ai))的計算公式如下：

其中，N(Ai,Pa(Aj))表示同時與Ai和Pa(Aj)有交互行為的實體個數(shù)；N(Pa(Ai))表示與Pa(Ai)有交互行為的實體個數(shù)。

根據(jù)以上分析得到基于MapReduce的SUBN模型構(gòu)建流程如圖1所示。

基于MapReduce的SUBN模型構(gòu)建算法由兩個Map函數(shù)和一個Reduce函數(shù)實現(xiàn)，具體算法實現(xiàn)如下。

算法1基于MapReduce的SUBN模型構(gòu)建算法

輸入：（1）實體集記錄，每行記錄的格式為T={t1,t2,…,tn},1≤n≤m；（2）用戶集合U={A1,A2,…,Am}。

步驟1獲得每行記錄中的N(Ai=1,Aj=1),N(Ai=1)，N(Aj=1)參數(shù)，并將其作為中間結(jié)果

Map(keyof record,record)

For each record do

Output＜key,value＞ pairs＜Ai,1＞ //用戶Ai出現(xiàn)的次數(shù)

Output＜key,value＞ pairs ＜AiAj,1＞ //用戶AiAj同時出現(xiàn)的次數(shù)

End for

步驟2獲取N(Ai=1,Aj=1),N(Ai=1),N(Aj=1)值

Reduce(Stringkey,Iteratorvalues)

//key為Ai或AiAj，迭代器values收集了所有相同key值＜AiAj,1＞或＜Ai,1＞鍵值對的value值

Result:=0

Fig.1 Flow chartof constructing SUBNmodel圖1 SUBN模型構(gòu)建流程圖

Foreach＜key,value＞ pair do

value:=Iterator.Next()//通過訪問迭代器獲得相應(yīng)的值

result:=result+value//對應(yīng)參數(shù)值累加

End for

Output＜key,value＞ pairs ＜key,result＞ //獲得所有＜AiAj,1＞ 或＜Ai,1＞的值

步驟3最終計算獲得DAG

Map(keyof pair,pair)

//pair為＜AiAj,rij＞,＜Ai,ri＞及＜Aj,rj＞的連接,其中rij是鍵值對＜AiAj,1＞的統(tǒng)計總數(shù)，ri是鍵值對＜Ai,1＞的統(tǒng)計總數(shù)

Foreach pair do

Ifsim(Ai,Aj)＞εthen //式（1）

IfP(Ai|Aj)≥P(Aj|Ai)then

Output＜key,value＞ pairs ＜Ai→Aj,P(Ai|Aj)＞//式（2）

Else

Output ＜key,value＞ pairs ＜Ai→Aj,P(Ai|Aj)＞//確定邊的方向

End if

End if

End for

根據(jù)式（3）可知N(Ai,Pa(Aj))、N(Pa(Aj))可以通過算法步驟1和步驟2獲得，進(jìn)而可以計算得到SUBN的條件概率參數(shù)表。

例1假設(shè)U={A1,A2,A3,A4}，T={T1={A1,A2,A5}，T2={A1,A2,A4}，T3={A1,A2,A3,A5}，T4={A1,A2,A3,A4}，T5={A2,A3,A6}，T6={A3,A4}，T7={A1,A4,A6}}。根據(jù)算法1中的第一個Map函數(shù)可以得到T1記錄中 ＜A1A2,1＞、＜A1,1＞及 ＜A2,1＞鍵值對的值，類似地可以獲得其他鍵值對的值。根據(jù)算法1中的Reduce函數(shù)可以得到 ＜A1A2,4＞、＜A1,5＞、＜A2,5＞。根據(jù)算法1的第二個Map函數(shù)以及式（1）即可獲得各用戶間的相似性值。假設(shè)ε=0.30，那么 (A1,A2)、(A2,A3)、(A1,A4)、(A3,A4)4條邊將被添加到E中。根據(jù)式（2）進(jìn)一步確定各邊的方向。例如P(A2|A3)=0.75,P(A3|A2)=0.6，因此邊(A2,A3)的方向為由A2指向A3。最后根據(jù)式（3）可以計算得到每個用戶對應(yīng)的CPT。最終得到的SUBN如圖2所示。

2.3 基于HBase的社交用戶貝葉斯網(wǎng)模型的分布式存儲

由SUBN的定義可知，它由有向無環(huán)圖和條件概率表兩部分組成。因此，SUBN的存儲即是對SUBN中的父子關(guān)系及各用戶對應(yīng)的CPT進(jìn)行存儲。基于HBase的SUBN分布式存儲就是將對應(yīng)的父子關(guān)系和CPT兩類數(shù)據(jù)按照HBase的存儲格式要求分布式地存儲到Hadoop平臺對應(yīng)的DataNode上，可以通過Hadoop上的namenode訪問HBase中的SUBN數(shù)據(jù)完成相關(guān)的查詢操作。

Fig.2 A simple SUBN obtained by Example1圖2 例1獲得的一個簡單SUBN

對于SUBN的每個用戶Ai，分別將Ai、Ai的父節(jié)點及Ai對應(yīng)的CPT以鍵值對的形式作為一行存儲到HBase數(shù)據(jù)庫對應(yīng)的TSUBN表中。其中Ai為行標(biāo)識，key的值為“列族名=列族成員”，AiPa(Ai)為列族名，aiPa(ai)為列族成員，value為對應(yīng)的條件概率值。對于每個用戶Ai利用Map函數(shù)并行地讀取其對應(yīng)的CPT表中的所有P(ai|Pa(ai))值，并將其以(Ai|AiPa(Ai)=aiPa(ai)|P(aiPa(ai))的邏輯表達(dá)形式并行存儲到TSUBN表中，其中行標(biāo)識、key、value的值通過“|”進(jìn)行分隔。最終，在進(jìn)行SUBN并行推理時可以通過Hadoop上的namenode來訪問HBase中SUBN數(shù)據(jù)實現(xiàn)高效推理?；贛apReduce實現(xiàn)SUBN存儲的流程如圖3所示。

3 基于社交用戶貝葉斯網(wǎng)的用戶相似性度量方法

3.1 基于概率推理的社交網(wǎng)絡(luò)用戶間接相似性

3.1.1 基于MapReduce的大規(guī)模貝葉斯網(wǎng)推理

貝葉斯推理就是以CPT數(shù)據(jù)為基礎(chǔ)，利用貝葉斯網(wǎng)中存在的條件獨立性來計算聯(lián)合概率的過程。貝葉斯網(wǎng)后驗概率計算是指在已知證據(jù)節(jié)點的前提下，計算獲得查詢節(jié)點的概率，即P(Q=q|E=e)，其中E為證據(jù)節(jié)點的集合，Q為查詢節(jié)點的集合。

Fig.3 Flow chartof SUBN storagebased on MapReduce圖3 基于M apReduce的SUBN存儲流程圖

通過構(gòu)建SUBN可以得到社交網(wǎng)絡(luò)用戶之間的直接相似性關(guān)系，然而現(xiàn)實中社交網(wǎng)絡(luò)用戶之間往往也存在大量的間接相似性關(guān)系，這種隱含的不確定關(guān)系可以通過SUBN的概率推理機(jī)制來獲得。

為了支持算法的高效性，本文根據(jù)已有的方法[12-13]給出了基于MapReduce的貝葉斯網(wǎng)并行推理方法，具體實現(xiàn)步驟為：（1）分解概率推理任務(wù)，由公式P(Q=q|E=e)=P(Q=q,E=e)/P(E=e)可知，可以將推理任務(wù)轉(zhuǎn)化為P(Q=q,E=e)和P(E=e)兩個邊緣概率值的計算。P(Q=q|E=e)是針對查詢節(jié)點、證據(jù)節(jié)點以及其他隱節(jié)點所構(gòu)成的所有可能組合的聯(lián)合概率值之和，P(E=e)是除證據(jù)節(jié)點和E之外的隱節(jié)點所有可能組合情況的聯(lián)合概率之和，根據(jù)條件獨立性將聯(lián)合概率的計算轉(zhuǎn)化為條件概率值的乘積，將以上所形成的所有組合情況存儲到HDFS中的TJDP文件中。（2）基于MapReduce查詢BN數(shù)據(jù)計算聯(lián)合概率。Map函數(shù)并行讀取TSUBN每一行記錄r，讀取數(shù)據(jù)與TJDP中的每行記錄進(jìn)行對比，最終比較結(jié)果以鍵值對形式寫入HDFS中的FJDP文件。Reduce函數(shù)將具有相同關(guān)鍵字的概率值累乘獲得各聯(lián)合概率值。（3）計算后驗概率值。根據(jù)所涉及的各種組合情況，對相應(yīng)的聯(lián)合概率值累加獲得邊緣概率值，進(jìn)而獲得所求概率值。通過該方法將大規(guī)模貝葉斯網(wǎng)上的概率推理任務(wù)轉(zhuǎn)化為海量數(shù)據(jù)之上的查詢?nèi)蝿?wù)，有效地利用了HBase海量數(shù)據(jù)存儲以及隨機(jī)訪問的優(yōu)勢，從而實現(xiàn)大規(guī)模貝葉斯網(wǎng)的高效推理?；贛apReduce的大規(guī)模BN推理實現(xiàn)過程如圖4所示。

3.1.2 基于概率推理的間接相似性度量

對于SUBN推理的相似性計算，其中查詢節(jié)點為目標(biāo)用戶A，證據(jù)節(jié)點為與A進(jìn)行相似性比較的用戶x(A∈Gu.U,x∈Gu.U)。因此，需要計算的后驗概率值為P(A=1|x=1)。根據(jù)3.1.1小節(jié)介紹的基于MapReduce的貝葉斯網(wǎng)并行推理方法，給出了基于SUBN推理的間接相似性度量算法具體實現(xiàn)如下。

算法2基于SUBN推理的間接相似性度量算法

輸入：（1）SUBN 的TSUBN；（2）SUBN 的TJDP；（3）SUBN推理所涉及的所有節(jié)點的集合，即V。

輸出:P(A=1,x=1)和P(x=1)的值。

步驟1獲得所有組合情況的概率值并將其作為中間結(jié)果

Map(Stringkey,Doublevalue)

//key為TSUBN中每一行的鍵值,即AiPa(Ai)=aiPa(ai)

//value為TSUBN中每一行的值，即P(ai|Pa(ai))

Foreach row do

S:={AiPa(Ai)}∩IS(A,x).V

Foreach rowrofTJDPdo

IfS.value=r.valuethen

//S.value是S在aiPa(ai)中對應(yīng)值的集合,r.value是第r行對應(yīng)的值

Generate＜key,value＞ pairs＜r.value,value＞

End if

End for

Fig.4 Processof large scale BN inferencebased on MapReduce圖4 基于M apReduce的大規(guī)模BN推理實現(xiàn)過程

End for

步驟2對具有相同鍵值的中間結(jié)果累乘，獲得所有聯(lián)合概率分布的值

Reduce(Stringkey,Iteratorvalues)

Result:=1

For each ＜key,value＞pair do

value:=Iterator:Next()

result:=result×value

Generate＜key,value＞ pairs＜PQ,value＞

IfA.valueinkey=1 then

Generate＜key,value＞ pairs＜PE,value＞

End if

End for

步驟3將具有相同鍵值的鍵值對的值累加最終得到P(A=1,x=1)和P(x=1)的值

Reduce(Stringkey,Iteratorvalues)

//key為PE或PQ

//values為具有相同鍵值的＜PQ,value＞或＜PE,value＞的＜key,value＞鍵值對

Result:=0

For each ＜key,value＞pair do

value:=Iterator.Next()

result:=result+value

End for

Generate＜key,value＞ pairs＜key,result＞

3.2 基于圖結(jié)構(gòu)的社交網(wǎng)絡(luò)用戶間接相似性

由McPherson等人[14]提出的同質(zhì)性理論，可以得到兩個重要的觀點：（1）人們更傾向于與自己相似的人做出相似的行為；（2）人們更傾向于與朋友的朋友建立朋友關(guān)系?；谝陨蟽蓚€觀點，借鑒已提出的網(wǎng)絡(luò)相似性方法[15]，通過考慮A和x的共同相似性用戶（m）提出了基于SUBN結(jié)構(gòu)的相似性。首先定義了兩種子圖SRG（sim ilarity relationship graph）和MSRG（mutualsim ilarity relationship graph）。

定義2給定一個SUBNG=(Gu,S)和兩個用戶A，x∈Gu.U，用戶A和x的MSRG(A,x)是滿足以下條件的SUBN子圖：

（1）MSRG(A,x).U={A,x}∪{u∈Gu.U|u≠x,u≠A,Pa(u)=A∩Pa(x)=u或Pa(u)=A∩Pa(u)=x或Pa(A)=u∩Pa(u)=x或Pa(u)=A∩Pa(u)=x}

（2）MSRG(A,x).E={＜u,u′＞∈Gu.E|u,u′∈MSRG(A,x).U}

由定義可知，MSRG是同時與目標(biāo)用戶A和用戶x具有直接相似性關(guān)系的用戶及他們之間的邊構(gòu)成的SUBN子圖，MSRG中邊的數(shù)量反映了兩個用戶之間聯(lián)系的緊密程度?？梢酝ㄟ^比較與用戶A直接相連的用戶構(gòu)成的子圖以及與用戶A、x同時相連的用戶構(gòu)成的子圖來確定用戶A、x之間的相似性。因此，給出了SRG的定義。

定義3給定一個SUBNG=(Gu,S)和一個用戶A∈Gu.U，用戶A的SRG(A)是滿足以下條件的SUBN子圖：

（1）SRG(A).U={A}∪{u∈Gu.U|u≠A,Pa(u)=A或Pa(A)=u}

（2）SRG(A).E={＜A,u＞ ∈Gu.E|u∈SRG(A).U}∪{＜u,u′＞ ∈Gu.E|u,u′∈SRG(A).U}

由以上定義可知，MSRG(A,x)和SRG(A)都是SUBN的子圖，因此可以通過查詢TSUBN來獲得?；赟UBN結(jié)構(gòu)的間接相似性可以通過比較MSRG(A,x)和SRG(A)邊的數(shù)量來獲得。具體定義如下。

定義4用戶A和x的網(wǎng)絡(luò)結(jié)構(gòu)相似性定義為：

其中，|MSRG(A,x).E|和|SRG(A).E|分別表示圖MSRG(A,x)及圖SRG(A)中邊的數(shù)量。該定義不僅考慮了用戶產(chǎn)生的影響，同時考慮了邊產(chǎn)生的影響。顯然，當(dāng)A、x之間沒有共同的相似性用戶時，MSRG僅包含兩個用戶而不包含邊，此時SS(A,x)的值為0。

例3假設(shè)SUBN結(jié)構(gòu)如圖5所示，計算A、x1的網(wǎng)絡(luò)相似性。SRG(A)含5個用戶(A,A1,A2,A3,A4)及5條邊(＜A,A1＞,＜A,A2＞,＜A,A3＞,＜A,A4＞,＜A1,A2＞)。MSRG(A,x1)中含有5條邊，即(＜A,A1＞,＜A,A2＞,＜A1,A2＞,＜A1,x1＞,＜A2,x1＞)。因此，SS(A,x1)=lg(5)/lg(2×5)=0.7。

Fig.5 A SUBN structurew ith 7 users圖5 含7個用戶的SUBN結(jié)構(gòu)

3.3 基于SUBN的社交網(wǎng)絡(luò)用戶相似性度量

結(jié)合以上基于SUBN推理的相似性及基于SUBN結(jié)構(gòu)的相似性，本文給出了最終的相似性度量公式：

sim(A,x)=a×SI(A,x)+b×SS(A,x),a,b∈[0,1] （5）其中，SI(A,x)是基于SUBN推理的相似性值；SS(A,x)是基于SUBN結(jié)構(gòu)的相似性值；a、b是二者所占的權(quán)重，a和b的值可以根據(jù)實際情況進(jìn)行調(diào)整。

基于該度量方法發(fā)現(xiàn)社交網(wǎng)絡(luò)相似性用戶時，x是A的n階馬爾科夫覆蓋中的用戶，n由用戶根據(jù)實際需要進(jìn)行設(shè)置，最終返回top-k用戶A的相似性用戶。

4 實驗結(jié)果

本文實驗所搭建的Hadoop平臺包含7臺機(jī)器，其中1臺為主節(jié)點，其余6臺為從屬節(jié)點。Hadoop版本為2.4.0，HBase版本為0.20.6，JDK版本為1.60，每臺機(jī)器的配置為Pentium?Dual-Core CPU E5700@3.00GHz@3.01GHz，2GB內(nèi)存。

本文采用的實驗數(shù)據(jù)為DBLP（http://dblp.uni-trier.de/xm l/）數(shù)據(jù)集，該數(shù)據(jù)集收錄了世界上最全面的計算機(jī)科學(xué)領(lǐng)域相關(guān)論文或著作元數(shù)據(jù)信息。首先從DBLP數(shù)據(jù)集中提取數(shù)據(jù)獲得一個以作者名為節(jié)點，以合著關(guān)系為邊的合著關(guān)系社交網(wǎng)絡(luò)。本文的實驗中實體集為合著關(guān)系社交網(wǎng)絡(luò)中的合著關(guān)系。

本文分別測試了算法1和算法2的執(zhí)行時間、加速比及并行效率。最后，驗證了算法的正確性和有效性。

4.1 算法執(zhí)行時間

為了驗證算法1的性能，分別測試了在不同從屬節(jié)點情況下，隨實體數(shù)據(jù)集增加SUBN的DAG構(gòu)建時間的變化以及隨SUBN用戶數(shù)量增加CPT計算時間的變化，如圖6、圖7所示（實驗圖中的n臺節(jié)點是指從屬節(jié)點數(shù)）。

由圖可以發(fā)現(xiàn)，實體數(shù)據(jù)集大小相同的情況下，隨著從屬節(jié)點數(shù)的增加算法執(zhí)行時間遞減；SUBN用戶節(jié)點數(shù)相同的情況下，隨著從屬節(jié)點數(shù)增加CPT計算時間遞減。另一方面，隨著實體集的增加DAG構(gòu)建算法的執(zhí)行時間變化相對緩慢，然而隨著SUBN用戶節(jié)點數(shù)的增加CPT計算時間急劇增加，由此可知算法1的性能主要取決于CPT的計算時間。

為了測試算法2的性能，測試了不同從屬節(jié)點下隨著SUBN用戶節(jié)點數(shù)的增加算法2執(zhí)行時間的變化，如圖8所示。由圖可知，在不同從屬節(jié)點情況下，隨著SUBN用戶節(jié)點數(shù)增加，算法執(zhí)行時間增加越來越慢；SUBN用戶節(jié)點數(shù)相同情況下，隨著從屬節(jié)點數(shù)的增加算法執(zhí)行時間遞減，這也就驗證了算法2可以在Hadoop框架下高效地執(zhí)行。

Fig.6 Timeof DAG constructionw ith the increaseof datasets圖6 隨著實體集數(shù)據(jù)量的增加SUBN的DAG構(gòu)建時間變化

Fig.7 Time of CPT calculationw ith the increase of SUBN nodes圖7 隨著SUBN中用戶節(jié)點數(shù)的增加CPT的計算時間變化

Fig.8 Timeof Algorithm 2w ith the increaseof SUBN nodes圖8 隨著SUBN中用戶節(jié)點數(shù)的增加算法2的執(zhí)行時間變化

4.2 算法加速比

加速比是指單個從屬節(jié)點情況下的算法順序執(zhí)行時間與多個從屬節(jié)點情況下的算法并行執(zhí)行時間的比值，加速比能夠很好地反映隨從屬節(jié)點的增加算法執(zhí)行效率的提升程度。為了驗證算法1和算法2的執(zhí)行效率提升程度，測試了在不同從屬節(jié)點情況下，隨實體集數(shù)據(jù)量增加算法1的加速比變化，以及隨SUBN用戶節(jié)點數(shù)增加算法2的加速比變化，如圖9、圖10所示。

Fig.9 Speedup of Algorithm 1w ith the increaseof datasets圖9 隨著實體集數(shù)據(jù)量的增加算法1的加速比變化

Fig.10 Speedup of Algorithm 2w ith the increaseof SUBN nodes圖10 隨著SUBN中用戶節(jié)點數(shù)的增加算法2的加速比變化

通過觀察圖9可以得到，在實體集較小時加速比變化幅度較小，實體集數(shù)據(jù)量增加時加速比變化幅度有了一定程度的增加。由此可知，算法1的加速比不僅取決于從屬節(jié)點數(shù)，更取決于實體集大小，實體集數(shù)據(jù)量越大加速比越大。類似地，通過觀察圖10可以得到，SUBN用戶節(jié)點數(shù)越多算法2的加速比越大。這也從某種程度上驗證了本文算法的高效性和良好的可擴(kuò)展性。

4.3 算法并行效率

并行效率是指加速比與處理器數(shù)量的比值，它可以很好地反映隨著實驗中處理器數(shù)量的增加并行算法的性能提升程度。分別測試了不同從屬節(jié)點情況下，隨實體集數(shù)據(jù)量增加算法1的并行效率變化情況，以及隨SUBN用戶節(jié)點數(shù)的增加算法2的并行效率變化情況，如圖11、圖12所示。

Fig.11 Parallelefficiency of A lgorithm 1 w ith the increase of datasets圖11 隨著實體集數(shù)據(jù)量的增加算法1的并行效率變化

Fig.12 Parallelefficiency of Algorithm 2w ith the increaseof SUBN nodes圖12 隨著SUBN中用戶節(jié)點數(shù)的增加算法2的并行效率變化

通過觀察圖11、圖12可以發(fā)現(xiàn)，不同從屬節(jié)點情況下，算法1的并行效率隨著實體集數(shù)據(jù)量的增加而提高，算法2的并行效率隨著SUBN用戶節(jié)點數(shù)的增加而提高。這表明本文算法隨著數(shù)據(jù)量的增加可以獲得更好的并行效率。另外，通過觀察圖12還可以發(fā)現(xiàn)，當(dāng)SUBN用戶節(jié)點數(shù)小于854 560時，從屬節(jié)點數(shù)越多算法的并行效率反而下降，而當(dāng)SUBN用戶節(jié)點數(shù)超過854 560后，6臺從屬節(jié)點情況下的并行效率超過4臺從屬節(jié)點情況下的并行效率。這表明要使本文算法在并行效率上達(dá)到最優(yōu)需要在SUBN用戶節(jié)點數(shù)、從屬節(jié)點數(shù)以及用戶需求上做適當(dāng)?shù)恼壑小?/p>

4.4 算法的正確性

為了測試算法的正確性，將本文算法與現(xiàn)有的L1Norm、Cosine兩種常用的用戶相似性度量方法進(jìn)行比較，二者定義如下：

其中，SA是SUBN中與用戶A直接相連的用戶集合；Sx是SUBN中與用戶x直接相連的用戶集合。

從SUBN中隨機(jī)地選取了一個目標(biāo)用戶A和6個潛在的相似用戶Axs1、Axs2、Axs3、Axs4、Axs5、Axs6。分別用基于SUBN的相似性度量方法、L1 Norm及Cosine計算相應(yīng)的相似性度量值，并根據(jù)得到的相似性度量值對用戶進(jìn)行相似性排序，如表1所示。

Table 1 Resultcomparison by 3 different sim ilaritymeasuresof 6 strangers表1 不同的相似性度量方法得到的結(jié)果比較

由以上結(jié)果可以得到，本文方法與其他兩種方法得到的結(jié)果基本一致。同時注意到對于用戶Axs3、Axs4，由其他兩種方法得到的兩個用戶相似度值相同，因此依據(jù)其他兩種方法無法確定兩個用戶的精確相似性排序，基于本文方法可以明確二者相似度排序，這也在一定程度上驗證了本文方法的正確性和準(zhǔn)確性。

5 總結(jié)與展望

基于貝葉斯網(wǎng)的用戶相似性發(fā)現(xiàn)方法較好地將社交網(wǎng)絡(luò)中的用戶行為分析與概率圖模型結(jié)合在一起，不僅可以發(fā)現(xiàn)用戶之間的直接相似性關(guān)系，還可以發(fā)現(xiàn)用戶之間的間接相似性關(guān)系，提高了用戶相似性發(fā)現(xiàn)算法的精確度。同時本文將算法擴(kuò)展到Hadoop平臺，提出了基于MapReduce的貝葉斯網(wǎng)構(gòu)建算法、基于MapReduce的貝葉斯網(wǎng)并行推理算法以及基于HBase的貝葉斯網(wǎng)分布式存儲方法，有效提高了算法的執(zhí)行效率，同時增強(qiáng)了算法的可擴(kuò)展性，為社交網(wǎng)絡(luò)數(shù)據(jù)分析提供了有力的技術(shù)支撐。考慮到社交網(wǎng)絡(luò)中用戶行為數(shù)據(jù)不斷增長以及信息的時效性，實時數(shù)據(jù)處理以及在原有模型基礎(chǔ)上的模型增量處理將會是接下來重點研究的工作。

[1]Han Xiao,Wang Leye,Farahbakhshb R,etal.CSD:amultiuser sim ilarity metric for community recommendation in online social networks[J].Journal of Expert Systems w ith Applications,2016,53(1):14-26.

[2]Wang Wei,Zhang Guangquan,Lu Jie.Collaborative filtering w ith entropy-driven user similarity in recommender systems[J].International Journal of Intelligent Systems,2015,30(8):854-870.

[3]Pirasteh P,Hwang D,Jung JJ.Exploitingmatrix factorization to asymmetric user sim ilarities in recommendation systems[J].Know ledge-Based Systems,2015,83(1):51-57.

[4]Gan M ingxin.Walking on a user sim ilarity network towards personalized recommendations[J].PLoS One,2014,9(12):e114662.

[5]Agarwal V,Bharadwaj K K.A collaborative filtering framework for friends recommendation in social networks based on interaction intensity and adaptive user similarity[J].SocialNetwork Analysisand M ining,2013,3(3):359-379.

[6]Bhattacharyya P,Grag A,Wu SF.Analysis of user keyword sim ilarity in online social networks[J].Social Network Analysisand M ining,2011,1(3):143-158.

[7]Nisgav A,Patt-Shamir B.Finding similarusers in socialnetworks:extended abstract[C]//Proceedings of the 21st Annual Symposium on Parallelism in A lgorithms and Architectures,Calgary,Canada,Aug 11-13,2009.New York:ACM,2009:169-177.

[8]Greene D,Doyle D,Cunningham P.Tracking the evolution of communities in dynamic social networks[C]//Proceedings of the 2010 International Conference on Advances in Social Networks Analysis and M ining,Odense,Denmark,Aug 9-11,2010.Washington:IEEEComputer Society,2010:176-183.

[9]Scott J.Social network analysis:developments,advances,and prospects[J].Social Network Analysis and M ining,2011,1(1):21-26.

[10]Abdo A,Salim N.Inference networks formolecular database sim ilarity searching international[J].Journal of Biometric and Bioinformatics,2008,2(1):1-16.

[11]Nillius P,Sullivan J,Carlsson S.Multi-target tracking-linking identities using Bayesian network inference[C]//Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition,New York,Jun 17-22,2006.Washington:IEEEComputer Society,2006:2187-2194.

[12]Yue Kun,Xu Juan,Fang Qiyu,etal.A large-scale Bayesian network parallel reasoning method based on MapReduce:China,CN201310709499.9[P].2014-04-23.

[13]Xu Juan.An approach for discovering user sim ilarity in social network based on Bayesian network[D].Kunm ing:Yunnan University,2015.

[14]McPherson M,Sm ith-Lovin L,Cook JM.Birds of a feather:homophily in social networks[J].Annual Review of Sociology,2001,27(8):415-444.

[15]Akcora CG,CarminatiB,FerrariE.User sim ilaritieson socialnetworks[J].Social Network Analysisand M ining,2013,3(3):475-495.

附中文參考文獻(xiàn)：

[12]岳昆,徐娟,方啟宇,等.一種基于MapReduce的大規(guī)模貝葉斯網(wǎng)并行推理方法:中國,CN201310709499.9[P].2014-04-23.

[13]徐娟.基于貝葉斯網(wǎng)的社交網(wǎng)絡(luò)用戶相似性發(fā)現(xiàn)[D].昆明:云南大學(xué),2015.

徐娟（1989—），女，山東菏澤人，2015年于云南大學(xué)獲得碩士學(xué)位，現(xiàn)為云南大學(xué)檔案館助理館員，主要研究領(lǐng)域為數(shù)據(jù)挖掘，高校檔案數(shù)字化等。主持云南省檔案館科技項目等。

ZHANG Diwasborn in 1990.He received theM.S.degree in computer sciences from Yunnan University in 2015.Now he is a teaching assistant at Yunnan University of Finance and Econom ics.His research interest is secure multi-party computation.

張迪（1990—），男，山西運(yùn)城人，2015年于云南大學(xué)獲得碩士學(xué)位，現(xiàn)為云南財經(jīng)大學(xué)人事處初級職員，主要研究領(lǐng)域為安全多方計算。

QIANWenhuawas born in 1980.He received the Ph.D.degree in computer sciences from Yunnan University in 2010.Now he is an associate professor at School of Information,Yunnan University.His research interests include non-photorealistic rendering and virtual reality,etc.

錢文華（1980—），男，云南曲靖人，2010年于云南大學(xué)獲得博士學(xué)位，現(xiàn)為云南大學(xué)信息學(xué)院副教授，主要研究領(lǐng)域為非真實感渲染，虛擬現(xiàn)實等。主持國家自然科學(xué)基金，云南省應(yīng)用基礎(chǔ)研究計劃等項目。

App lication of Probabilistic Graphical M odel for Discovering User Sim ilarity in SocialNetwork*

XU Juan1,ZHANG Di2,QIANWenhua3+
1.Archives·Party and University History Research Office,Yunnan University,Kunm ing 650091,China
2.PersonnalDepartment,Yunnan University of Finance and Econom ics,Kunm ing 650221,China
3.Schoolof Information,Yunnan University,Kunm ing 650504,China

Discovering user sim ilarity in socialnetwork asa basic research of socialmedia data analysis can be used in product recommendation and socialnetwork user relationship evolution effectively.To representcomplex correlations and their uncertainties among social network users and improve the accuracy of user sim ilarity inmass social network theoretically,this paper proposes an effectivemethod for discovering user sim ilarity in socialnetwork combining network topological structure and dependence between usersbased on Bayesian network,an importantprobabilistic graphicalmodel.To improve the scalability of the proposedmethod and solve the storage and computation problem ofmass data,this paper proposes Bayesian network distributed storage and parallel reasoning algorithm based on Hadoop platform.Theexperimental resultsverify that the proposedmethod iseffective and correct.

as born in 1989.She

the M.S.degree in computer sciences from Yunnan University in 2015.Now she is an assistant archivistat Yunnan University.Her research interests include datam ining and digital construction of university archives,etc.

A

：TP311

*The National Natural Science Foundation of China under GrantNos.61462093,61662087(國家自然科學(xué)基金);the Applied Basic Research Program of Yunnan Province under GrantNo.2014FB113(云南省應(yīng)用基礎(chǔ)研究計劃項目);the Key Program of Departmentof Education of Yunnan ProvinceunderGrantNo.2012Z012(云南省教育廳重點項目).

Received 2016-07,Accepted 2016-10.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-10-18,http://www.cnki.net/kcms/detail/11.5602.TP.20161018.1622.008.htm l

Keywords:socialnetwork;Bayesian network;user sim ilarity;parallel reasoning;Hadoop