基于社交影響力的推薦算法

房 旋，陳升波，宮 婧,，孫知信

(1.南京郵電大學 計算機學院、軟件學院，江蘇 南京 210003；2.南京郵電大學 理學院，江蘇 南京 210023；3.南京郵電大學 寬帶無線通信與傳感網技術教育部重點實驗室，江蘇 南京 210003)

基于社交影響力的推薦算法

房 旋1，陳升波2，宮 婧2,3，孫知信3

(1.南京郵電大學 計算機學院、軟件學院，江蘇 南京 210003；2.南京郵電大學 理學院，江蘇 南京 210023；3.南京郵電大學 寬帶無線通信與傳感網技術教育部重點實驗室，江蘇 南京 210003)

社交網站的興起促使社交推薦成為了推薦系統領域的熱門研究方向。微博是一類具有代表性的社交網站，其用戶之間以一對多的不對等關系為主，如何為微博用戶推薦潛在的關注對象是社交推薦中的一個重要研究點。文中針對微博類社交網站中用戶間關系不對等的特點，結合用戶間的交互行為信息，提出了一種社交影響力的計算方法，并在此基礎上提出基于社交影響力的推薦算法(SIB)。該算法通過計算用戶社交影響力矩陣，然后使用K個最近鄰(K-NearestNeighbor，KNN)算法找出目標用戶的鄰居集合，借助鄰居集合幫助推薦。該算法綜合考慮了微博社交網站中的兩種社交關系，能有效地對微博類社交網站進行個性化推薦。通過在真實數據集上進行實驗，證明該算法在微博類社交網站中的推薦效果比單純的基于用戶協同過濾(User-basedCollaborativeFiltering，UCF)算法有一定程度的提升。

社交網絡；微博；社交影響力；協同過濾；推薦算法

1 概 述

隨著網絡技術的發展，為用戶提供個性化推薦成為了目前互聯網服務的一個重要內容。推薦系統[1]的概念最早是在1997年提出的，一開始主要被用在電商網站中，向用戶推薦感興趣的商品[2]。

推薦系統的核心是推薦算法。早期的推薦算法主要分為基于內容的推薦算法和協同過濾算法。

基于內容的推薦算法的核心就是提取物品的特征，然后用TF-IDF方法計算各個特征的權重[3]，并根據這些特征與用戶的喜好進行匹配，從而向用戶進行推薦。相比于多媒體信息(視頻、音頻、圖片等)，文本類項目(新聞、網頁、博客)的特征相對容易提取，因而基于內容的推薦方法在文本類推薦領域得到了廣泛應用。

協同過濾算法主要分為兩大類：基于記憶(memory-based)和基于模型(model-based)[4]。基于記憶的方法又可以分為基于用戶(user-based)[5]和基于項目(item-based)[6]的方法?；谟脩舻膮f同過濾算法思想是找到和目標用戶相似的鄰居用戶，利用鄰居用戶的評分來估計目標用戶的評分?；陧椖康膮f同過濾算法認為，不同項目之間存在相似性，當需要估計目標用戶對某個項目的評分時，可以根據該目標用戶對相似項目的評分進行估計。

基于模型的推薦算法主要是利用數據挖掘、機器學習和概率統計等方法，對用戶的歷史行為數據進行分析，建立用戶模型，從而進行推薦[7]。

雖然協同過濾算法的商業應用非常成功，但是其存在的問題也不容忽視。冷啟動和數據稀疏性是協同過濾算法最突出的兩個問題。

近年來，隨著Facebook、騰訊微博等社交網站的興起，如何利用用戶與用戶之間的社交關系進行個性化推薦成為了研究的熱點。社交關系中包含了大量信息，如果能充分挖掘并利用好這些信息，可以在一定程度上緩解傳統協同過濾算法存在的問題，對后者是一個有效的補充，可以改善推薦的效果。文獻[8]利用Social Networks Analysis (SNA)理論分析微博內容，從中提取出關鍵詞作為特征圖譜，并以此來構建用戶與用戶以及用戶與商品之間的關系，從而進行商品推薦。文獻[9]認為在社會語境中存在兩個有效的語境因素—個體偏好和人際影響，可以將用戶-項目矩陣分解成用戶-項目偏好矩陣和用戶-項目影響力矩陣，并據此提出了一種基于社會語境的推薦框架。文獻[10]重新定義了社交網絡中的相似度屬性、相似度構成及其計算方法，提出了一種改進的協同過濾推薦算法。文獻[11]則從待推薦對象間的關系出發，提出了一種結合推薦對象間關聯關系的社會化推薦算法。Nirmal Jonnalagedda等在文獻[12]中提出了利用Twitter來提取用戶的興趣愛好和新聞的流行程度，進而向用戶提供個性化的新聞推薦。文獻[13]提出利用目標用戶的歷史數據構建一個個性化的候選項排序模型，同時提出一種具備多種推薦策略的推薦系統，可以向Twitter用戶推薦一些值得關注的對象。

上述研究表明，大多數算法把重心放在對用戶歷史評分信息或者文本內容的挖掘上，對于社交關系中包含的互動信息仍未能進行充分挖掘，推薦的準確度仍有提高的空間。針對這一問題，文中引入社交影響力的概念，在基于用戶的協同過濾算法的基礎上，提出一種基于社交影響力的SIB(Social Influence-Based)推薦算法，并對其推薦效果進行驗證。

2 SIB推薦算法

傳統的基于用戶的協同過濾算法通過計算用戶相似度矩陣，來尋找用戶的最近鄰居。這里的相似度矩陣是一個對稱矩陣，即認為用戶與用戶之間的關系是對等的。

然而在社交關系中，用戶與用戶之間不一定是對等關系。現實生活中也是這樣，兩人即使是好友，對方在自己心目中的地位和自己在對方心目中的地位也不一定完全對等，只能說好友之間的關系的對等程度普遍要大于陌生人。因此，文中采用社交影響力來描述用戶與用戶之間的社交關系。社交影響力表示的是單向的社會關系，這比傳統的相似度更加適用于社交場景。

2.1 算法介紹

SIB推薦算法通過挖掘用戶之間的社交關系數據，建立用戶之間的社交影響力矩陣，從而為用戶提供推薦。該算法流程見圖1。

圖1 融合社交網絡信息的協同過濾算法流程

首先根據用戶評分信息計算出用戶之間的相似度，然后根據用戶的社交信息計算出用戶的基礎影響力，通過線性融合的方式將二者結合起來，形成影響力矩陣。接著對用戶的影響力進行排序，找到對目標用戶影響力最大的K個鄰居用戶，利用這些鄰居用戶對待預測項目的評分估計目標用戶對待預測項目的評分，挑選出預測評分最高的L個項目作為推薦列表。

2.2 相關定義

在微博系統中，用戶的社交關系主要有兩種(如圖2所示)：一種是關注/被關注的靜態關系；另一種是提及(mention)/轉發(re-post)/評論(comment)的動態的互動關系。同一個用戶的關注用戶集合和互動用戶集合并不一定完全重合。關注/被關注的關系用關注影響力來衡量，用follow表示；互動關系用互動影響力來衡量，用interact表示。文中利用關注影響力和互動影響力來計算用戶之間的社交影響力。

圖2 微博系統中的兩種社交關系

定義1：關注影響力follow(u,v)。

(1)

其中，outDegree(u)指用戶u關注的人數，在社交圖中用頂點的出度表示。

關注影響力的含義如下：

(1)如果用戶u和用戶v互相關注了對方，那么u和v很可能互相認識，甚至是現實中的朋友。在這種情況下，他們之間有相似愛好的可能性很大，同時他們推薦給對方的東西更容易被接受，即他們對對方都有較大的影響力。

(2)如果用戶u關注了v，而v未關注u。這種情況可能是因為v的某些方面是u所喜歡的，u是v的“粉絲”。那么可以認為v對于u是有一定影響力的，而u對于v則沒有什么影響力。在這種情況下，考慮到有些用戶傾向于關注很多對象，其關注行為的價值就會變低，而有些用戶傾向于關注少量對象，其關注行為的價值就會比較高，因此將用戶u關注的人數納入計算。用戶u關注的人越多，其中某個被關注對象v對他的影響力就會降低。

(3)如果用戶u和用戶v都沒有關注對方，那么他們之間的關注影響力為0。

定義2：社交行為action(u,v)。

社交行為指提及(mention)、轉發(re-post)和評論(comment)。action(u,v)表示用戶u對用戶v發起的社交行為的次數，具體來說就是u提及v的次數(at(u,v))、u轉發v的微博次數(re(u,v))以及u評論v的微博次數(com(u,v))三者之和。

定義3：互動影響力interact(u,v)。

interact(u,v)=

(2)

其中，action(u,v)表示用戶u對用戶v發起的社交行為次數；actionSum(u,v)表示u，v之間的互動總次數；MIN_ACTION_SUM是一個閾值，當u，v之間的互動總次數小于這個閾值時，互動影響力設為0，以減少噪音。

互動總次數的公式如下：

actionSum(u,v)=action(u,v)+action(v,u)

(3)

f1是一個系數，其計算公式為：

(4)

函數f(x)定義如下：

(5)

(6)

其中，R表示的是用戶u對用戶v發起的社交行為次數占u，v之間互動總次數的比重，該值越大說明u越關注v。

當R=0時，說明u根本不關注v，則v對u的影響力為0；

當R大于0小于0.5時，說明u不是很關注v，但v對u的影響力會隨著R的增大而增大；

當R=0.5時，說明u，v之間的互動關系是比較平衡的，基本上是“有來有往”，那么u和v是好友的可能性很大，可以認為此時v對u的影響力最大；

當R大于0.5小于1時，說明u很關注v，但v不是很關注u，可以認為u是v的“粉絲”，此時v對u的影響力比較大，但會隨著R的增大而減小；

當R=1時，說明v根本不關注u，u單方面關注v，此時v對u還是有一定影響力的，但不如好友對其的影響力大，將影響力的值定義為最大值的0.8倍。

定義4：基礎影響力BaseInfluence(u,v)。

BaseInfluence(u,v)表示用戶v對用戶u的基礎影響力?；A影響力越大，用戶v推薦給用戶u的東西被接受的可能性越大。

BaseInfluence(u,v)=

(7)

定義5：用戶相似度[14]similarity(u,v)。

用戶相似度是根據用戶的歷史評分信息計算出來的用戶之間的相似程度。在基于用戶的協同過濾算法中，常用的計算用戶相似度的方法有余弦相似度、皮爾森相關系數、杰卡德相關系數等。

杰卡德相關系數衡量的是兩個集合之間的相似程度，它更加適合于描述離散值集合的相似度。微博系統中的評分正好是離散的：接受推薦用1標注，拒絕推薦用-1標注，未表態用0標注。因此文中采用杰卡德相關系數來計算用戶之間的相似度是合適的。

用戶u和用戶v之間的相似度用杰卡德相關系數表示如下：

其中，l{x}是一個指示函數，如果x值為真，則l{x}值為1；如果x值為假，則l{x}值為0。rui和rvi分別表示用戶u和用戶v對項目i的評分。I(u)和I(v)分別表示用戶u和用戶v有評分的項目集合。

定義6：社交影響力SocialInfluence(u,v)。

SocialInfluence(u,v)=(1-δ)?similarity(u,v)+ δ?BaseInfluence(u,v)

(9)

其中，similarity(u,v)是用戶u和用戶v的相似度；BaseInfluence(u,v)是用戶v對用戶u的基礎影響力；δ是系數。

通過上述公式得到任意用戶v對任意用戶u的社交影響力，N個用戶的社交影響力就構成一個N×N維的社交影響力矩陣。

有了社交影響力矩陣以后，就可以采用KNN算法[15]尋找目標用戶影響力最大的K個用戶，因為社交數據的稀疏性，為了避免鄰居用戶和目標用戶之間影響力過小造成計算不準確，因此采用基于閾值的KNN算法。首先設定一個影響力閾值MIN_INFLUENCE，只有影響力大于這個閾值的用戶才會被加入鄰居集合，雖然這樣得到的鄰居數可能少于K個，但可以提高推薦準確度。

2.3 算法設計

算法1：尋找用戶u的最大影響力鄰居集合。

輸入：社交影響力矩陣I，目標用戶u，鄰居數K，影響力閾值MIN_INFLUENCE；

輸出：鄰居集合N(u)。

S1：找出所有對u的影響力不為0的用戶，加入鄰居集合，并按照影響力倒序排列；

S2：取鄰居集合最后一個用戶，判斷影響力是否大于閾值，如果是，轉S3，否則轉S4；

S3：判斷當前鄰居數是否大于K，如果是，轉S4，否則轉S5；

S4：將該用戶從鄰居集合中刪除，轉S2；

S5：返回鄰居集合。

有了最大影響力鄰居集合以后就可以根據鄰居用戶的評分信息來預測目標用戶對未知項目的評分。預測用戶u對未知項目i的評分采用如下公式：

(10)

有了目標用戶對未知項目的評分，就可以從未知項目中找出預測評分最高的L個項目，組成推薦集合推薦給目標用戶。

算法2：SIB推薦算法。

輸入：用戶列表，用戶評分數據，用戶社交數據，目標用戶u，鄰居數K，推薦列表長度N，閾值MIN_ACTION_SUM、MIN_INFLUENCE；

輸出：為目標用戶u生成的推薦結果列表R。

S1：根據用戶評分數據計算用戶之間的相似度，得到用戶相似度矩陣S；

S2：根據用戶社交數據和閾值MIN_ACTION_SUM計算用戶之間基礎影響力，得到基礎影響力矩陣B；

S3：根據社交影響力生成公式計算社交影響力，得到社交影響力矩陣I；

S4：根據算法1計算得到目標用戶u的最大影響力鄰居集合N(u)；

S5：根據評分預測公式預測目標用戶u對所有未知項目的評分，并將評分按照從高到低排序，取預測評分最高的前L個項目組成推薦列表R，推薦給目標用戶u；

S6：算法結束。

3 實驗設計及分析

3.1 實驗數據及評價標準

為了驗證文中提出算法的有效性，用KDD CUP 2012 Track1數據集進行實驗。下面簡要介紹一下所采用的數據集的基本情況。

KDD CUP 2012 Track1數據集中的數據來源于騰訊微博的真實數據，其中包含了1 000萬用戶和5萬個項目，以及3億條推薦記錄和大約300萬個社會網絡的“關注(following)”行為。其中，用戶對項目關注情況采用-1、0、1三個數值表示：接受關注用1表示，拒絕關注用-1表示，未表態用0表示。除此之外，該數據集中還包含用戶屬性、用戶社交關系等信息。

由于原數據集比較龐大，為了提高實驗效率，從原數據集中隨機抽取一部分作為實驗數據。在該實驗中，隨機抽取了3 000個用戶對2 740個項目的關注信息，以及這3 000個用戶的社交關系數據作為訓練集。同時還隨機抽取了500個用戶作為測試集。

3.2 實驗評估指標

實驗采用的評價指標是MAE。MAE指標衡量的是推薦算法的準確率，值越小越好。

MAE計算的是預測評分和實際評分之間的平均誤差，其定義為：

(11)

3.3 實驗結果及分析

設定推薦列表長度L=5，BaseInfluence所占比重δ={0.2,0.4,0.6}。對于每個δ，都考察不同鄰居數K情況下的實驗結果，K={2,4,6,8,10,12,14,16,18,20}，并且和傳統UCF算法進行比較，見圖3～5。

圖3 δ取0.2時算法MAE指標隨著鄰居數K的變化曲線

從實驗結果可以看出，文中提出的基于用戶社交影響力的SIB推薦算法較傳統UCF算法在推薦準確率上有所提升。因為社交數據相對于用戶評分數據更為稀疏，隨著δ值的變大，或多或少會引入噪聲，影響SIB算法的推薦效果。但總體上可以看出，挖掘用戶的社交數據對于提升推薦算法的推薦效果有著積極意義，尤其是針對微博類社交網站中用戶關系不對等的特點，SIB算法中建立的影響力模型能夠較好地描述這一特點。

圖4 δ取0.4時算法MAE指標隨著鄰居數K的變化曲線

圖5 δ取0.6時算法MAE指標隨著鄰居數K的變化曲線

4 結束語

在社交網站中，豐富的社交關系數據具有非常大的利用價值。利用用戶的社交關系數據輔助推薦是目前社交類推薦系統研究的熱點。微博系統作為目前非常流行的社交系統，有其自身的特點。好友關系在微博系統中并不是主要的社交關系，更多的是關注與被關注的關系。如何能更好地描述用戶與用戶之間這種不對等的社交關系，對于提升微博類社交網站的推薦效果有很大的意義?；谶@方面的考慮，文中提出的SIB推薦算法充分利用了用戶關注數據和互動數據，不僅在一定程度上可以緩解冷啟動問題，而且對于傳統UCF算法是一個很好的補充，提高了推薦算法的準確率。

后續研究需要繼續考慮微博系統的特點，繼續對其中的社交數據或者文本數據進行分析挖掘。例如，可以考慮微博內容的“話題性”、微博名人的領域權威性、被推薦對象之間的關聯關系以及被推薦對象對普通用戶的影響力等等。社交系統中的信息非常豐富，數據量非常大，也可以考慮對數據進行分布式處理，這樣可以對更多的數據進行挖掘，提高處理的效率。

[1]ResinickP,VarianHR.Recommendersystems[J].CommunicationsoftheACM,1997,40(3):56-58.

[2]LindenG,SmithB,YorkJ.Amazon.comrecommendationsitem-to-itemcollaborativefiltering[J].IEEEInternetComputing,2003,7(1):76-80.

[3] 王嫣然,陳 梅,王翰虎,等.一種基于內容過濾的科技文獻推薦算法[J].計算機技術與發展,2011,21(2):66-69.

[4]BreeseJS,HeckermanD,KadieC.Empiricalanalysisofpredictivealgorithmsforcollaborativefiltering[C]//Proceedingsofthe14thconferenceonuncertaintyinartificialintelligence.[s.l.]:[s.n.],1998:43-52.

[5]ResnickP,IakovouN,SushakM,etal.GroupLens:anopenarchitectureforcollaborativefilteringofnetnews[C]//Proceedingsofthe1994computersupportedcooperativeworkconference.[s.l.]:[s.n.],1994:175-186.

[6]SarwarB,KarypisG,KonstanJ.Item-basedcollaborativefilteringrecommendationalgorithms[C]//Proceedingsofthe10thinternationalconferenceonworldwideweb.[s.l.]:[s.n.],2001:285-295.

[7] 陳克寒，韓盼盼，吳 健.基于用戶聚類的異構社交網絡推薦算法[J].計算機學報,2013,36(2):349-359.

[8]ChangPei-Shan,TingI-Hsien,WangShyue-Liang.Towardssocialrecommendationsystembasedonthedatafrommicroblogs[C]//Procofinternationalconferenceonadvancesinsocialnetworksanalysisandmining.[s.l.]:IEEE,2011:672-677.

[9]JiangMeng,CuiPeng,WangFei,etal.Scalablerecommendationwithsocialcontextualinformation[J].IEEETransactionsonKnowledgeandDataEngineering,2014,26(11):2789-2802.

[10] 榮輝桂,火生旭,胡春華,等.基于用戶相似度的協同過濾推薦算法[J].通信學報,2014,35(2):16-24.

[11] 郭 磊，馬 軍，陳竹敏，等.一種結合推薦對象間關聯關系的社會化推薦算法[J].計算機學報,2014,37(1):219-228.

[12]JonnalageddaN,GauchS.Personalizednewsrecommendationusingtwitter[C]//ProcofIEEE/WIC/ACMInternationalconferencesonwebintelligenceandintelligentagenttechnology.[s.l.]:IEEE,2013:21-25.

[13]IslamM,DingChen,ChiChi-Hung.Personalizedrecommendersystemonwhomtofollowintwitter[C]//ProceedingsofIEEEfourthinternationalconferenceonbigdataandcloudcomputing.[s.l.]:IEEE,2014:326-333.

[14]DengYingying,LuTun,XiaHuanhuan,etal.AOPUT:arecommendationframeworkbasedonsocialactivitiesandcontentinterests[C]//ProceedingsofIEEE17thinternationalconferenceoncomputersupportedcooperativeworkindesign.[s.l.]:IEEE,2013:545-550.

[15] 黃創光，印 鑒，汪 靜，等.不確定近鄰的協同過濾推薦算法[J].計算機學報,2010,33(8):1369-1377.

A Recommendation Algorithm Based on Social Influence

FANG Xuan1,CHEN Sheng-bo2,GONG Jing2,3,SUN Zhi-xin3

(1.School of Computer Science,School of Software,Nanjing University of Posts and Telecommunications,class="content_center">Nanjing 210003,China;2.College of Mathematics & Physics,Nanjing University of Posts and Telecommunications,Nanjing 210023,China;3.Key Laboratory of Broadband Wireless Communication and Sensor Network Technology,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

The rise of social networking sites promotes social recommendation becoming the research hotspot in the field of recommender systems.As a representative social network,Weibo has unequal one-to-many relationship between users.How to recommend potential Weibo users concerned is an important research direction in the social recommendation.Aiming at the characteristics of unequal relationship between users in social network of Weibo,combined with the mutual behavior information between users,a computing method of social influence is proposed and on the basis,a SIB algorithm is also presented.By calculating the social influence matrix of user,this algorithm uses the KNN algorithm to find the target user set of neighbors,and helps to recommend with the aid of neighbors set.The algorithm considers the two kinds of social relations for social network in Weibo,which can effectively conduct personalized recommendation for social networking sites in Weibo.The experiment shows that the SIB algorithm can effectively improve the accuracy of recommendation system in social networks compared with UCF algorithm.

social network;Weibo;social influence;collaborative filtering;recommendation algorithm

2015-09-12

2015-12-16

時間：2016-05-25

國家自然科學基金資助項目(60973140，61170276，61373135)；江蘇省產學研項目(BY2013011)；江蘇省科技型企業創新基金(BC2013027)；江蘇省高校自然科學研究重大項目(12KJA520003)；江蘇省大學生創新創業訓練計劃項目(201410293023Z)

房 旋(1990-)，男，碩士生，研究方向為移動開發、推薦系統；宮 婧，副教授，研究方向為計算機應用技術；孫知信，教授，研究方向為計算機應用技術。

http://www.cnki.net/kcms/detail/61.1450.TP.20160525.1706.036.html

TP

A

1673-629X(2016)06-0031-06

10.3969/j.issn.1673-629X.2016.06.007