基于用戶社會關(guān)系的社交網(wǎng)絡(luò)好友推薦算法研究

景 楠，王建霞，許 皓，卞亦文

(1.上海大學(xué)悉尼工商學(xué)院，上海 201899；2.安徽大學(xué)商學(xué)院，安徽 合肥 230601)

?

基于用戶社會關(guān)系的社交網(wǎng)絡(luò)好友推薦算法研究

景 楠1，王建霞1，許 皓2，卞亦文1

(1.上海大學(xué)悉尼工商學(xué)院，上海 201899；2.安徽大學(xué)商學(xué)院，安徽 合肥 230601)

社交網(wǎng)絡(luò)中存在海量用戶，如何有效推薦好友是社交網(wǎng)絡(luò)可持續(xù)發(fā)展的重要環(huán)節(jié)，也是社交網(wǎng)絡(luò)相關(guān)研究的重要主題。當(dāng)前實踐及現(xiàn)有研究往往基于用戶的顯性信息推薦好友，而忽略了用戶之間的隱性社會關(guān)系；此外，顯性信息往往不夠完整且存在虛假信息問題。為有效實現(xiàn)好友推薦，本文提出了基于用戶社會關(guān)系的好友推薦算法，并重點應(yīng)用關(guān)聯(lián)規(guī)則算法分析用戶之間的隱含關(guān)聯(lián)度，構(gòu)造用戶之間的網(wǎng)絡(luò)有向圖及關(guān)系轉(zhuǎn)移矩陣；然后，結(jié)合關(guān)系轉(zhuǎn)移矩陣與PageRank算法計算每個用戶的分數(shù)，將分數(shù)較高的用戶推薦給目標用戶。在此基礎(chǔ)上，本文引入用戶影響力，提出綜合考慮用戶社會關(guān)系及用戶影響力的PeopleRank算法。為驗證算法的合理性和有效性，將本文所提出的兩種算法與傳統(tǒng)的社會過濾算法、PageRank算法進行對比分析。為此，本文抓取了Twitter社交網(wǎng)站上用戶數(shù)據(jù)開展實驗分析。實驗結(jié)果顯示本文所提出的算法具有較好的推薦效果，尤其是綜合考慮用戶社會關(guān)系及用戶影響力的好友推薦算法在推薦準確率和推薦召回率上都有明顯的優(yōu)勢。

社交網(wǎng)絡(luò)；好友推薦；社會關(guān)系；影響力；PageRank算法

1 引言

社交網(wǎng)站的興起改變了人們的交流方式，促進了溝通頻率，并提高了溝通效率。網(wǎng)絡(luò)用戶主要通過社交網(wǎng)站關(guān)注新聞熱點話題及感興趣的人與事，而相關(guān)信息的獲取主要來源于其所關(guān)注的人群[1]。對于用戶而言，如果能夠提供一些精選的用戶，將能提升用戶在社交網(wǎng)站中的體驗和滿意度。因此，社交網(wǎng)站中好友推薦應(yīng)運而生。為有效推薦用戶好友，推薦算法就成為重要的研究主題。

目前，國內(nèi)外對于社交網(wǎng)站好友推薦算法的研究成果相對較少。從研究對象角度來看，現(xiàn)有的好友推薦算法主要基于社交網(wǎng)站用戶的顯性社交信息和顯性社會關(guān)系[2]。顯性社交信息包括用戶的地理位置、標簽信息、話題信息、文本信息。Zheng Yu等[3]將一個用戶訪問某個位置的次數(shù)作為對該位置的隱含評分，并利用該評分來計算用戶之間的相似性，并以此進行好友推薦。胡江文等[4]提出了基于關(guān)聯(lián)規(guī)則與標簽的好友推薦算法，該算法首先挑選出與目標用戶共同好友最多的用戶集，然后通過計算目標用戶和每個候選用戶之間的標簽相似度以推薦相似度最高的用戶；然后設(shè)定初步推薦好友的權(quán)重，并進行打分，選取分數(shù)最高的用戶進行推薦。于海群等[5]利用文本挖掘的相關(guān)技術(shù)和最小均方誤差算法，把抓取的用戶話題數(shù)據(jù)轉(zhuǎn)化成用戶偏好特征向量，用相似度度量方法計算用戶之間的相似度以確定與用戶話題偏好最相近的用戶集，并完成用戶的二級好友推薦。Weng Jianshu等[6]分別把每個用戶發(fā)布的所有微博集成為一個文檔，使用文檔主題生成模型發(fā)現(xiàn)每個用戶潛在感興趣的主題。Chen Jilin等[7]采用向量空間模型表示用戶所發(fā)布的微博文本，用Term Frequency-Inverse Document Frequency 技術(shù)提取用戶的特征向量，計算用戶特征向量之間的相似性，以此推薦相似性較高的用戶。

基于顯式社會關(guān)系的好友推薦基于用戶的社會關(guān)系在不同的好友之間進行信息互聯(lián)和好友推薦[8]。顯式社會關(guān)系通常指社會網(wǎng)絡(luò)用戶的一級人脈，即直接關(guān)注關(guān)系?；诖祟愱P(guān)系的主要算法包括社會過濾和PageRank算法。社會過濾算法基于分析隱含于用戶每一位好友的信息準確地推薦好友，主要推薦與目標用戶共同好友最多的用戶[9]。舒琰等[10]認為微博平臺上只通過對比粉絲人數(shù)而進行排名的方法不盡合理，其基于PageRank算法，以用戶為節(jié)點，以用戶關(guān)系為有向邊，建立概率轉(zhuǎn)移矩陣，計算微博用戶的PageRank值。Weng Jianshu等[6]提出將用于網(wǎng)頁排序的Page Rank 算法應(yīng)用于社交網(wǎng)絡(luò)計算用戶的影響力，并向目標用戶推薦影響力較大的用戶。王平等[11]基于人人網(wǎng)的用戶社會關(guān)系，應(yīng)用好友分類和關(guān)系連接權(quán)重分類的方法解決好友過多和信息爆炸的問題。Chen Can等[12]認為用戶的影響力與用戶頁面和用戶交互之間的鏈接結(jié)構(gòu)有關(guān)，利用用戶之間的社會關(guān)系計算用戶之間的關(guān)系強度構(gòu)建轉(zhuǎn)移矩陣，結(jié)合PageRank算法計算用戶的影響力，從而推薦出影響力較高的用戶。向程冠等[13]提出一種基于關(guān)聯(lián)規(guī)則的社交網(wǎng)絡(luò)好友推薦算法，其將新浪微博中用戶之間的“關(guān)注”作為交易記錄，將關(guān)注的用戶作為交易項，所有交易項的集合作為交易數(shù)據(jù)庫，生成二階候選集，并按支持數(shù)降序排序，推薦出排名較高的用戶作為好友。

綜上所述，現(xiàn)有好友推薦算法通?；谟脩麸@性的社交信息和社會關(guān)系，結(jié)合數(shù)據(jù)挖掘技術(shù)、統(tǒng)計學(xué)方法等進行好友推薦。但這類顯性信息多包含結(jié)構(gòu)化與非結(jié)構(gòu)化數(shù)據(jù)，如短文本、鏈接、視頻、音頻、圖片等，需要經(jīng)過復(fù)雜的數(shù)據(jù)處理技術(shù)轉(zhuǎn)換成能夠描述用戶特征的結(jié)構(gòu)化數(shù)據(jù)才能有效利用[14-16]。同時，這些顯式信息的準確獲取比較困難，信息中存在信息不完整以及虛假成分等問題，以此信息提取的用戶特征向量往往是不準確的。相對于用戶顯性信息，用戶的隱性社會關(guān)系往往能為好友推薦提供更多的有效因素。在社交網(wǎng)站的用戶關(guān)系中，除強關(guān)系外，還存在弱關(guān)系[4-5]。弱關(guān)系是指二級人脈，實質(zhì)是一種傳遞關(guān)注關(guān)系。例如，Simmel三元閉包理論中認為，在一個社交圈內(nèi)，若兩個人有一個共同朋友，則這兩個人成為朋友的可能性會提高[18-19]；Naruchitparames等[20]提出的FOF理論(好友的好友理論)認為，如果兩個用戶有很多共同好友，那么這兩個用戶很可能是好友。在社交網(wǎng)站中，弱關(guān)系往往具有較大的人脈關(guān)系價值，并能提供較為客觀和可靠的數(shù)據(jù)，可以直接反映用戶之間的隱含關(guān)聯(lián)，并能更為準確地反映用戶之間的相似性，為好友推薦提供支持[7, 17]。

本文以用戶的隱性社會關(guān)系為研究對象，著重挖掘用戶之間隱含的關(guān)聯(lián)關(guān)系，提出一種新的好友推薦算法。該算法將用戶選擇好友的過程模擬為一個馬爾科夫過程，為用戶下一步選擇關(guān)注的用戶與當(dāng)前關(guān)注的用戶建立關(guān)聯(lián)關(guān)系。同時基于此關(guān)聯(lián)關(guān)系構(gòu)造用戶間網(wǎng)絡(luò)有向圖，以關(guān)聯(lián)規(guī)則的置信度作為圖中有向邊的權(quán)重，并根據(jù)此加權(quán)有向圖建立轉(zhuǎn)移矩陣。結(jié)合PageRank 算法計算用戶在社交關(guān)系中的實際權(quán)重，再將權(quán)重較高的用戶作為潛在好友進行推薦。為便于描述，將該算法稱為PeopleRank算法?；谠撍惴ǎ胗脩粲绊懥?，本文又提出了基于用戶影響力的PeopleRank算法。本文給出了兩種算法的詳細過程，并用實驗分析說明了所提出算法的合理性和優(yōu)越性。

2 理論基礎(chǔ)

本文所提出的好友推薦算法是基于關(guān)聯(lián)規(guī)則和PageRank算法的；因此，本節(jié)首先簡要介紹這兩種方法的基本原理。

2.1 關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則是一種數(shù)據(jù)刻畫方式，主要是從數(shù)據(jù)中抽取頻繁項集[21-23]。設(shè)I是一個項集，I={i1,i2,…,in},元素i1,i2,…,in稱之為項。事務(wù)數(shù)據(jù)庫D={T1,T2,…,Ti,…,Tm}是事務(wù)數(shù)據(jù)集的集合，Ti?I。關(guān)聯(lián)規(guī)則的形式為X→Y，其中X?I、Y?I且X∩Y=?。該關(guān)聯(lián)規(guī)則的意義是，如果X中所有項都出現(xiàn)在某事務(wù)數(shù)據(jù)集，那么Y也有可能出現(xiàn)在該事務(wù)數(shù)據(jù)集。

關(guān)聯(lián)規(guī)則通常用支持度和置信度衡量。規(guī)則X→Y的支持度是指事務(wù)數(shù)據(jù)庫中包含X和Y的事務(wù)數(shù)與所有事務(wù)數(shù)之比，記為Support(X→Y)，即：

(1)

規(guī)則X→Y的置信度是指事務(wù)數(shù)據(jù)庫中包含X和Y的事務(wù)數(shù)與包含X的事務(wù)數(shù)之比。換言之，該規(guī)則的置信度等于所有包含X的事務(wù)中同時包含Y的事務(wù)的比例，記為Confidence(X→Y)，即：

(2)

實際上，規(guī)則X→Y的支持度可以看作是X∪Y同時出現(xiàn)在事務(wù)中的概率P(X∪Y)，即Support(X→Y)=P(X∪Y)；規(guī)則X→Y的置信度可以看作是一個條件概率P(Y|X)，即Confidence(X→Y)=P(Y|X)。關(guān)聯(lián)規(guī)則挖掘就是在給定的事務(wù)數(shù)據(jù)庫中找到那些支持度和置信度不低于給定閾值的關(guān)聯(lián)規(guī)則。

2.2 PageRank算法

PageRank算法最早是在谷歌搜索引擎中對網(wǎng)頁重要性進行排序的算法[24-26]。該算法將網(wǎng)頁之間的鏈接關(guān)系表示成一個有向圖，圖中的節(jié)點代表網(wǎng)頁，有向邊代表網(wǎng)頁之間的鏈接關(guān)系，并對圖中的每個網(wǎng)頁進行賦值(PageRank值)。對于一個網(wǎng)頁而言，其PageRank值是來源于所有鏈向它的網(wǎng)頁，而它也會將自己的PageRank值平均分配給所有它鏈向的網(wǎng)頁。顯然，網(wǎng)頁被鏈接的次數(shù)越多，其PageRank值也就越高。

PageRank算法模擬了一個人瀏覽網(wǎng)頁的行為，假設(shè)一個人從一個隨機網(wǎng)頁出發(fā)，除了可以點擊當(dāng)前網(wǎng)頁的出鏈前進，還能夠隨機跳轉(zhuǎn)到任一隨機網(wǎng)頁。

根據(jù)上述原理，網(wǎng)頁PageRank值的計算公式定義如下：

(3)

其中，PR(Vi)是網(wǎng)頁Vi的PageRank值；n是網(wǎng)頁總數(shù)；d是阻尼系數(shù)，它表示一個人在瀏覽網(wǎng)頁時，以d的概率點擊當(dāng)前網(wǎng)頁上的出鏈進行瀏覽，以1-d的概率隨機選擇別的網(wǎng)頁瀏覽；In(Vi)是所有鏈向Vi的網(wǎng)頁集合；Out(Vj)是Vj鏈向的網(wǎng)頁的集合；|Out(Vj)|是Vj出鏈的總數(shù)，即出度。

定義一個轉(zhuǎn)移矩陣來表示有向圖。假設(shè)網(wǎng)頁節(jié)點數(shù)為n，則該矩陣M=(mij)n×n是一個n行n列的矩陣。如果節(jié)點i有k條出鏈，那么對每一個出邊鏈向的節(jié)點j，矩陣第i行第j列的矩陣元素mij值為1/k；而其余節(jié)點的值為0。因此，可將公式(3)表示成如下形式：

(4)

PageRank算法就是通過計算網(wǎng)頁的PageRank值對網(wǎng)頁進行排序的，僅僅依賴于網(wǎng)頁之間的鏈接關(guān)系，其計算可以離線完成。

3 基于用戶社會關(guān)系的好友推薦算法

本節(jié)基于社會網(wǎng)絡(luò)中用戶間隱性關(guān)系，首先提出一種基于用戶社會關(guān)系的好友推薦算法；然后，引入用戶影響力，并提出綜合考慮用戶社會關(guān)系及用戶社會影響力的好友推薦算法。

3.1 算法過程描述

本文提出的好友推薦算法將用戶隨機選擇好友的過程模擬成一個馬爾科夫過程[27]，即在很大程度上，目標用戶選擇關(guān)注的下一個用戶與當(dāng)前已關(guān)注的用戶之間是關(guān)聯(lián)的，具體定義為：

定義3.1：設(shè)目標用戶為u，推薦候選集為U={u1,u2,…,un}，對于任意m個非負整數(shù)t1,t2,…,tm(0≤t1

P{U(tm+k)=u′|U(t1)=u1,U(t2)=u2,…,U(tm)=um}=P(U(tm+k)=u′|U(tm)=um).

(5)

其中，P(U(tm+k)=u′|U(tm)=um)是條件概率，亦為轉(zhuǎn)移概率，表示在tm時刻目標用戶選擇關(guān)注了用戶um的情況下，在tm+k時刻選擇關(guān)注用戶u′的概率。

在社交網(wǎng)站G=(U,E)中，U={u1,u2,…,un}，令p(uj|ui)表示一步轉(zhuǎn)移概率，其含義是：已知當(dāng)前時刻目標用戶u關(guān)注了ui，則下一步其選擇關(guān)注用戶uj的概率。因此，可定義如下轉(zhuǎn)移概率矩陣：

定義3.2：一步轉(zhuǎn)移矩陣可表示為P=(pij)n×n，其中，pij=p(uj|ui)，具體形式如下：

P=

其中，一步轉(zhuǎn)移矩陣滿足以下兩個條件：

(1)0≤p(uj|ui)≤1(i,j=1,2,…,n)；

3.2 PeopleRank好友推薦算法

本文基于上述馬爾科夫過程提出的PeopleRank好友推薦算法假設(shè)目標用戶隨機關(guān)注了一個用戶，將會以一定的概率d選擇與當(dāng)前用戶相關(guān)聯(lián)的用戶進行關(guān)注，并以(1-d)的概率隨機選擇別的用戶進行關(guān)注。設(shè)目標用戶u的推薦候選集U為包含了n個用戶的集合，記為U={u1,u2,…,un}。具體算法過程描述如下：

(1)利用關(guān)聯(lián)規(guī)則構(gòu)造用戶之間的有向圖

設(shè)ui,uj∈U，且j≠i，如果剩余n-2個用戶中存在關(guān)注過ui的用戶也同時關(guān)注了用戶uj，稱ui存在一條邊指向uj，記為關(guān)聯(lián)規(guī)則ui→uj；其表示關(guān)注過ui的用戶也有可能關(guān)注uj。以此類推，當(dāng)U中所有用戶都建立了兩兩關(guān)聯(lián)的有向邊后，即可得到用戶關(guān)系的有向圖。

(2)計算有向邊的權(quán)重

將關(guān)聯(lián)規(guī)則ui→uj的置信度賦值于網(wǎng)絡(luò)圖中有向邊的權(quán)重。記Confidence(ui→uj)是關(guān)聯(lián)規(guī)則ui→uj的置信度，其表示關(guān)注過ui的用戶也關(guān)注uj的概率。具體計算方法如下：

定義剩余n-2個用戶中關(guān)注過ui的用戶的數(shù)目為ui的支持度，記為Support(ui)；剩余n-2個用戶中同時關(guān)注過ui和uj的用戶的數(shù)目為項集{ui,uj}的支持度，記為Support(ui,uj)；則有：

Confidence(ui→uj)=

(6)

(3)建立轉(zhuǎn)移矩陣

設(shè)M是一個n×n矩陣，n為用戶數(shù)量。于是，可得到關(guān)于目標用戶u的轉(zhuǎn)移矩陣M=(mij)n×n，(i,j=1,2,…,n)，即：

mij=

(7)

(4)計算候選集中用戶的PeopleRank值

在得到轉(zhuǎn)移矩陣M后，即可計算用戶的PeopleRank值，即：

其中，PRu(ui)表示用戶ui推薦給用戶u的PeopleRank值，d是阻尼系數(shù)；mji是矩陣M的第j行第i列元素。根據(jù)式(8)可得到用戶ui的PeopleRank值。

(5)Top-N用戶推薦

根據(jù)得到的PeopleRank值，并將其按降序排列，并選取前N個用戶(Top-N用戶)推薦給目標用戶。

上述PeopleRank好友推薦算法可總結(jié)為：通過用戶之間的關(guān)聯(lián)關(guān)系，構(gòu)造有向圖和轉(zhuǎn)移矩陣；然后，計算用戶的PeopleRank值，并進行排序，將PeopleRank值高的用戶推薦給目標用戶。從算法角度[18]，該過程可描述為：

步驟1：構(gòu)造用戶之間的有向圖，如果存在關(guān)注過ui的用戶也關(guān)注了用戶uj，就稱ui存在一條有向邊指向uj，否則不存在有向邊。

步驟2：設(shè)矩陣M=(mij)n×n是n×n矩陣，n為用戶數(shù)量，mij是關(guān)聯(lián)規(guī)則ui→uj的置信度，它表示關(guān)注過ui的用戶關(guān)注uj的概率。

步驟3：利用公式(8)計算用戶的PeopleRank值。

步驟4：根據(jù)PeopleRank值輸出值較高的Top-N用戶列表。

3.3 綜合考慮用戶社會關(guān)系及社會影響力的PeopleRank好友推薦算法

PeopleRank好友推薦算法在進行PeopleRank值的計算時，將權(quán)重(1-d)平均分給了每個用戶。因此，當(dāng)目標用戶不選擇與當(dāng)前用戶相關(guān)聯(lián)的用戶，而以(1-d)的概率去隨機關(guān)注其他用戶，候選集中每個用戶對于目標用戶而言都是同等重要的。換言之，目標用戶會以同等概率去選擇關(guān)注其他用戶。實際上，現(xiàn)實中人們往往會關(guān)注那些在社交網(wǎng)絡(luò)中影響力較大的用戶而不是其他普通用戶。因此，我們提出一種假設(shè)：在這種情況下，目標用戶可能更傾向于去關(guān)注那些比較有影響力的人。因此，考慮用戶的影響力，基于用戶影響力區(qū)分候選集中的用戶修正所提出的PeopleRank好友推薦算法。

綜合考慮用戶社會關(guān)系及用戶社會影響力的PeopleRank算法需要運用PageRank算法計算候選人集合中的每個用戶的影響力，得到表示用戶影響力的特定向量，記為eu=(e1,e2,…,en)，其中ei表示目標用戶u的候選集中用戶ui的影響力。因此，基于式(8)，可得到用戶影響力的PeopleRank值，即：

(9)

其中，PRu(ui)表示用戶ui推薦給用戶u的PeopleRank值；d是阻尼系數(shù)；mji是矩陣M的第j行第i列元素。

4 實驗分析

實驗數(shù)據(jù)集來源于Arizona State University官方網(wǎng)站；該數(shù)據(jù)集收集了Twitter網(wǎng)站上一部分用戶以及用戶之間的社會關(guān)系[28]。本文選取了1658個用戶，包含了60589個用戶關(guān)系。用戶關(guān)系數(shù)據(jù)集用Oracle數(shù)據(jù)庫存儲；實驗硬件平臺為Intel(R) Core(TM)i5-3230M CPU，主頻為2.6GHz，4GB內(nèi)存，500GB硬盤；操作系統(tǒng)為Windows 8.1；數(shù)據(jù)的查找和分離用Oracle語句完成，所有算法用C++語言實現(xiàn)。

實驗采用交叉驗證方法[17,29]開展；為此，將數(shù)據(jù)集分為80%的訓(xùn)練集和20%的測試集。對于目標用戶u，將其已經(jīng)關(guān)注的用戶集合記為first-user(u)，并將first-user(u)里面用戶關(guān)注的用戶記為second-user(u)；將second-user(u)中的用戶作為候選集，對目標用戶u進行Top-N好友推薦。為說明本文所提出方法的合理性和有效性，將之與社會過濾算法和PageRank算法進行對比分析，并采用準確率和召回率進行評價分析[4,9]。其定義為：

準確率=推薦出的已經(jīng)成為好友的用戶數(shù)/推薦出的好友數(shù)；

召回率=推薦出的已經(jīng)成為好友的用戶數(shù)/好友總個數(shù)。

實驗將使用好友推薦個數(shù)N=5,10,15,20,25,30,35,40,45等九種情況分別計算每種算法的準確率和召回率。為比較四種算法的有效性，根據(jù)每個算法的推薦結(jié)果，分別計算測試集中每個用戶在每種情況(N值)下的好友推薦準確率和召回率；然后，計算測試集中所有用戶在每種情況下的平均準確率和平均召回率。計算結(jié)果如圖1和圖2所示。

圖1 不同N值情形下四種算法平均準確率對比

圖2 不同N值情形下四種算法平均召回率對比

圖1顯示了不同N值情況下四種好友推薦算法的平均準確率。結(jié)果顯示：社會過濾算法在每一個N值下的平均準確率都遠遠低于其它3個算法；當(dāng)N≤25時，PeopleRank算法的平均準確率明顯高于PageRank算法的平均準確率；而當(dāng)N>25時，其平均準確率要比PageRank算法平均準確率差。在每一個N值情形下，基于用戶社會關(guān)系及用戶影響力的PeopleRank算法的平均準確率都高于PageRank算法的平均準確率。就本文所提出的兩種算法而言，當(dāng)N≤25時，兩種算法的平均準確率差異較??；而當(dāng)N>25時，綜合考慮用戶社會關(guān)系及用戶影響力的PeopleRank算法的平均準確率明顯要高于PeopleRank算法的評價準確率。根據(jù)上述結(jié)果可知，社會過濾算法推薦的用戶往往不被目標用戶接受。當(dāng)N較小時，基于用戶社會關(guān)系的推薦算法的準確率高于PageRank算法，表明其推薦出來的用戶更能讓目標用戶接受；但是隨著N的增大，其推薦準確率就低于PageRank算法，即基于用戶社會關(guān)系的算法更加適用于精準推薦而非大規(guī)模推薦。而綜合考慮用戶社會關(guān)系及用戶影響力的推薦算法，在各種情況下，推薦出來的用戶都更能讓目標用戶接受，即對于精準推薦和大規(guī)模推薦都具有明顯優(yōu)勢。

圖2顯示了不同N值情形下四種好友推薦算法的平均召回率。與其它三種算法相比，社會過濾算法在每一個N值下的平均召回率都遠遠低于其它三個算法的平均召回率；綜合考慮用戶社會關(guān)系及社會影響力的PeopleRank算法在每一個N值情形下的平均召回率都優(yōu)于PageRank算法及PeopleRank算法的平均召回率。當(dāng)N≤15時，PeopleRank算法的平均召回率高于PageRank算法的平均召回率；而當(dāng)N>15時，其平均召回率卻差于PageRank算法的平均召回率。可見，社會過濾算法在用于好友推薦時，不能有效推薦目標用戶真正感興趣的用戶。當(dāng)N較小時，基于用戶社會關(guān)系的推薦算法的召回率高于PageRank算法，表明其能挑選出更多的目標用戶感興趣的用戶；但是隨著N的增大，其推薦召回率低于PageRank算法，表明基于用戶社會關(guān)系的推薦算法在大規(guī)模推薦時，推薦質(zhì)量降低。而綜合考慮用戶社會關(guān)系及用戶影響力的推薦算法，對于精準推薦和大規(guī)模推薦都具有明顯優(yōu)勢。

基于上述實驗結(jié)果，可得出以下結(jié)論：

(1)社會過濾算法在用于Twitter這種雙向關(guān)注型社交網(wǎng)絡(luò)的好友推薦時，效果不理想，不適用于弱關(guān)系推薦；

(2)PageRank算法僅僅考慮了用戶的影響力而忽略了用戶之間的關(guān)聯(lián)關(guān)系，其推薦的好友大多是粉絲數(shù)較多的名人明星，而用戶關(guān)注的名人明星通常是有限的，該算法具有一定的局限性；

(3)當(dāng)推薦人數(shù)N較少時，PeopleRank算法的推薦準確率明顯高于PageRank算法，在社交網(wǎng)站中進行精準推薦時，可能會有更好的推薦效果；但是PeopleRank算法注重用戶之間的關(guān)聯(lián)關(guān)系，將隨機選擇集中的用戶同等看待，可能會忽略那些更容易被大眾熟知且影響力較高的用戶，推薦效果具有局限性；

(4)綜合考慮用戶社會關(guān)系及用戶影響力的PeopleRank算法兼顧了用戶之間的關(guān)聯(lián)關(guān)系以及用戶影響力，其推薦準確率和召回率是四種算法中最高的，能夠更好地向目標用戶推薦好友。

5 結(jié)語

在線社交網(wǎng)站中存在海量用戶，如何從中尋找出目標用戶真正認識或感興趣的潛在好友是社交網(wǎng)絡(luò)相關(guān)研究的重要主題。在此背景下，本文提出了基于用戶社會關(guān)系的好友推薦算法，其基本思想是將用戶選擇好友的過程模擬成一個馬爾科夫過程，通過建立并挖掘用戶間潛在的關(guān)聯(lián)關(guān)系確定推薦好友集合。對于目標用戶，選定其二級好友作為候選集；首先，通過關(guān)聯(lián)規(guī)則去挖掘候選集中用戶間的關(guān)聯(lián)關(guān)系，以此重新構(gòu)造用戶間的網(wǎng)絡(luò)有向圖，并以關(guān)聯(lián)規(guī)則的置信度作為圖中有向邊的權(quán)重；然后，根據(jù)加權(quán)有向圖建立轉(zhuǎn)移矩陣；最后，結(jié)合PageRank算法計算候選集中每個用戶的分數(shù)，并將排名靠前的用戶推薦給目標用戶。基于此推薦算法，本文又引入了用戶在社會網(wǎng)絡(luò)中的影響力，對推薦算法進行修正，提出綜合考慮用戶社會關(guān)系及用戶社會影響力的好友推薦算法。

為了驗證本文所提出的兩種算法的有效性，基于準確率和召回率兩種評價指標，將其與社會過濾算法以及PageRank算法進行比較。為此，選取了Twitter網(wǎng)站上的數(shù)據(jù)進行實驗分析。實驗結(jié)果表明：當(dāng)推薦人數(shù)較少時，本文提出的PeopleRank算法的推薦準確率和召回率是優(yōu)于社會過濾算法和PageRank算法的，更適用于精準推薦；同時，本文提出的綜合考慮用戶社會關(guān)系及用戶影響力的PeopleRank算法無論是在準確率還是召回率上都相對較高，表明其無論是用于精準推薦還是大規(guī)模推薦，都比另外三種算法具有更好的推薦效果。

本文所提出的算法采用Twitter網(wǎng)站上的數(shù)據(jù)，且數(shù)據(jù)集相對較小，未來的研究工作可以考慮采用FaceBook和新浪微博的數(shù)據(jù)，并盡可能擴大數(shù)據(jù)集，以進一步驗證算法的有效性。此外，本文所提出的算法需要大量的迭代計算，算法有待完善。

[1] 中國互聯(lián)網(wǎng)信息中心.2014年中國社交類應(yīng)用用戶行為研究報告[EB/OL].[2014-08-22].http://www.cnnic.net.cn/hlwfzyj/hlwxzbg/201408/P020140822379356612744.pdf.

[2] Shriver SK,Nair HS,Hofstetter R.Social ties and user-generated content: Evidence from an online social network[J].Management Science,2013,59(6):1425-1443.

[3] Zheng Yu, Zhang Lizhu, Ma Zhengnin, et al.Recommending friends and locations based on individual location history [J].ACM Transactions on the Web (TWEB),2011,5(1):5.

[4] 胡文江,胡大偉,高永兵,等.基于關(guān)聯(lián)規(guī)則與標簽的好友推薦算法[J].計算機工程與科學(xué),2013,35(2):109-113.

[5] 于海群,劉萬軍,邱云飛.基于用戶話題偏好的社會網(wǎng)絡(luò)二級人脈推薦[J].計算機應(yīng)用,2012,32(05):1366-1370.

[6] Weng Jianshu, Lim E P, Jiang Jing, et al. Twitterrank: Finding topic-sensitive influential twitterers[C]//Proceedings of the third ACM international conference on Web search and data mining:New York, USA, February 04-06,2010.

[7] Chen Jilin, Geyer W, Dugan C, et al. Make new friends, but keep the old: Recommending people on social networking sites[C]//Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. Boston, USA, April 04-09,2009.

[8] Huang Wuhan, Meng Xiangwu, Wang Licai. A collaborative filtering algorithm based on users' social relationship mining in mobile communication network [J].Journal of Electronics and Information Technology,2011,33(12):3002-3007.

[9] 高永兵,楊紅磊,劉春祥,等.基于內(nèi)容與社會過濾的好友推薦算法研究[J].微型機與應(yīng)用,2013,32(14):75-78.

[10] 舒琰,向陽,張騏,等.基于PageRank的微博排名MapReduce算法研究[J].計算機技術(shù)與發(fā)展,2013,23(2):73-76.

[11] 王平,龍毅宏,唐志紅,等.基于社會關(guān)系的互聯(lián)網(wǎng)信任建立模式研究[J].軟件,2011,32(4):12-15.

[12] Chen Can, Feng Haodi. Microblog recommendation based on user interaction[C]//Proceedings of 2012 2nd International Conference on.Computer Science and Network Technology (ICCSNT),December 29-31,2012.

[13] 向程冠,熊世桓,王東.基于關(guān)聯(lián)規(guī)則的社交網(wǎng)絡(luò)好友推薦算法[J].中國科技論文,2014,9(1):87-91.

[14] 丁兆云,賈焰,周斌.微博數(shù)據(jù)挖掘研究綜述[J].計算機研究與發(fā)展,2015,51(4):691-706.

[15] 官思發(fā),朝樂門.大數(shù)據(jù)時代信息分析的關(guān)鍵問題、挑戰(zhàn)與對策[J].圖書情報工作,2015,59(3):12-18.

[16] 趙宇,黃思明,陳銳.數(shù)據(jù)分類中的特征選擇算法研究[J].中國管理科學(xué),2013,21(6):38-46.

[17] 徐志明,李棟,劉挺,等.微博用戶的相似性度量及其應(yīng)用[J].計算機學(xué)報,2014,37(1):207-218.

[18] Klimek P, Thurner S. Triadic closure dynamics drives scaling laws in social multiplex networks [J].New Journal of Physics,2013,15(6):63008-63016.

[19] Opsahl T. Triadic closure in two-mode networks: Redefining the global and local clustering coefficients [J].Social Networks,2013,35(2):159-167.

[20] Naruchitparames J, Gunes M H, Louis S J. Friend recommendations in social networks using genetic algorithms and network topology[C]//Proceedings of 2011 IEEE Congress on.Evolutionary Computation (CEC).New Drleans, USA, June 5-8,2011.

[21] Orriols-Puig A, Martínez-López F J, Casillas J, et al. Unsupervised KDD to creatively support managers' decision making with fuzzy association rules: A distribution channel application[J].Industrial Marketing Management,2013,42(4):532-543.

[22] 張玲玲,周全亮,唐廣文,等.基于領(lǐng)域知識和聚類的關(guān)聯(lián)規(guī)則深層知識發(fā)現(xiàn)研究[J].中國管理科學(xué), 2015,23(2):154-161.

[23] 蔡偉杰,張曉輝.關(guān)聯(lián)規(guī)則挖掘綜述[J].計算機工程,2001,27(5):31-33.

[24] 歐衛(wèi),歐繽憶,謝贊福,等.一種基于PageRank的微博用戶影響度評估算法[J].計算機與現(xiàn)代化,2013,(12):34-37.

[25] Rajaraman A, Ullman J D.大數(shù)據(jù):互聯(lián)網(wǎng)大規(guī)模數(shù)據(jù)挖掘與分布式處理[M].王斌，譯.北京:人民郵電大學(xué)出版社,2012.

[26] 李強,王申康.一種基于PageRank算法原理的會員人氣度排序算法[J].計算機系統(tǒng)應(yīng)用,2008,(1):27-30.

[27] 姬新龍,周孝華.基于馬爾科夫隨機波動和極值理論的風(fēng)險測度[J].中國管理科學(xué),2014,22(10):44-51.

[28] Arizona State University. Twitter dataset[R/OL]. http://socialcomputing.asu.edu/datasets/Twitte.

[29] Hsu W H, King A L, Paradesi M S R, et al. Collaborative and structural recommendation of friends using weblog-based social network analysis[C]//Proceedings of AAAI Spring Symposium:Computational Approaches to Analyzing Weblogs.Stanford, California, USA, March 27-29,2006.

Friend Recommendation Algorithm based on User Relations in Social Networks

JING Nan1，WANG Jian-xia1，XU Hao2, BIAN Yi-wen1

(1.SHU-UTS SILC Business School, Shanghai University, Shanghai 201899, China; 2. Schoolof Business, Anhui University, Hefei 230601, China)

Due to the vast amounts of users, it is difficult for a user to make effective connections with others for common interests. Friend recommendationon online social networks, therefore, becomes a challenging research issue, which may have significant effects on sustainable developments of social networks.Most of the existing friend recommendation methods are conducted based on users’ explicit informationsuch as background, demography, interests and posts, while ignoring users’ implicit informationsuch as their social relationships. Notably, explicit information is often incomplete and not trustworthy, and cannot be appropriately used to measure user similarities.In order toeffectively recommend friends, a recommendation algorithm is proposed based on user relationship information in online social networks. In the described algorithm, user relationships are characterized by using the association analysis method, and then a weighted, directed graph between network users is constructed. Based on this graph, this algorithm builds a transition matrix and uses the PageRank algorithm to calculateusers’ scores that indicate the acceptance probabilities, and then recommend the users with high scores to the target user on social networks. In addition, with the consideration of the user authority in a specific social network, an enhanced friend recommendation algorithm is further developed.In order to validate the proposed approaches, friend recommendation experiments on Twitter are conducted and the users’ information and their relationship data are extracted. For this purpose, two traditional methods, i.e., social filtering algorithm and the PageRank algorithm, are used to compare with the two proposed approaches based on two measures, i.e., accuracy and recall rate. Experiments results show that the proposed recommendation algorithms yield clearly better results in accuracy and recall rate than the traditional recommendation algorithms.

social networks; friend recommendation; social relationship; user authority; PageRank algorithm

1003-207(2017)03-0164-08

10.16381/j.cnki.issn1003-207x.2017.03.019

2015-11-18；

2016-05-14

國家自然科學(xué)基金面上資助項目(71371010,71571115)；上海市科學(xué)委員會科技人才計劃項目(14PJ1403700)；上海市教育委員會科研創(chuàng)新項目(14YS006)；教育部在線教育研究中心在線教育研究基金(全通教育)項目資助(2016YB138)

卞亦文(1978-)，男(漢族)，安徽蕪湖人，上海大學(xué)悉尼工商學(xué)院，博士，教授，研究方向：服務(wù)運作管理、決策分析，E-mail:ywbian@shu.edu.cn.

C931;TP39

A