基于社交網絡的社會化推薦算法研究

朱彥杰

（許昌學院，河南 許昌 461000）

美國著名的第三方調查機構尼爾森調查了影響用戶相信某個推薦的因素[1]，調查結果顯示，90%的用戶相信朋友對他們的推薦，70%的用戶相信網上其他用戶對廣告商品的評論。從該調查可以看到，好友的推薦對于增加用戶對推薦結果的信任度非常重要。在社交網站中，可以通過好友給自己過濾信息，只關注與閱讀和自己有共同興趣好友分享來的信息，從而避免了很多無關的信息，自然地減輕了信息過載問題。

在社交網站方面，國外以Facebook 和Twitter 為代表，國內社交網站，以QQ 空間、人人網、朋友網、新浪微博等為代表；這些社交網站形成了兩類社交網絡結構。一種是，好友一般都是自己在現實社會中認識的人，比如同事、同學、親戚等，并且這種好友關系是需要雙方確認的，如Facebook、QQ 空間，這種社交網絡稱為社交圖譜。另一種是，好友往往都是現實中自己不認識的，而只是出于對對方言論的興趣而建立好友關系，好友關系也是單向的關注關系，如Twitter、新浪微博，這種社交網絡稱為興趣圖譜。同時，也必須指出，任何一個社會化網站都不是單純的社交圖譜或興趣圖譜。在QQ 空間中大多數用戶聯系基于社交圖譜，而在微博上大多數用戶聯系基于興趣圖譜。在微博中，也會關注現實中的親朋好友，在QQ 中也會和部分好友有共同興趣。

1 社交網絡及其數據分類

在社交網絡中，需要表示用戶之間的聯系，可以用圖G(V，E，w)定義一個社交網絡，其中V 是頂點集合，每個頂點代表一個用戶，E 是邊集合，如果用戶va 和vb 有社交網絡關系，那么就有一條邊e(va，vb)連接這兩個用戶，w(va，vb)用來定義邊的權重。前面提到基于社交圖譜或興趣圖譜的兩種社交網絡，基于社交圖譜的朋友關系是需要雙向確認的，因而可以用無向邊連接有社交網絡關系的用戶；基于興趣圖譜的朋友關系是單向的，可以用有向邊代表這種社交網絡上的用戶關系。對圖G 中的用戶頂點u，定義out(u)為頂點u 指向的頂點集合（也就是用戶u 關注的用戶集合），定義in(u)為指向頂點u 的頂點集合（也就是關注用戶u 的用戶集合）。顯然在無向社交網絡中out(u)=in(u)。一般來說，有3 種不同的社交網絡數據[2]。

雙向確認的社交網絡數據：在以Facebook 和人人網為代表的社交網絡中，用戶A 和B 之間形成好友關系需要通過雙方的確認。因此，這種社交網絡一般可以通過無向圖表示。

單向關注的社交網絡數據：在以Twitter 和新浪微博為代表的社交網絡中，用戶A 可以關注用戶B 而不需要得到用戶B 的允許，因此這種社交網絡中的用戶關系是單向的，可以通過有向圖表示。

基于社區的社交網絡數據：還有一種社交網絡數據，用戶之間并沒有明確的關系，但是這種數據包含了用戶屬于不同社區的數據。比如豆瓣小組，屬于同一個小組可能代表了用戶興趣的相似性。

2 基于社交網絡的推薦算法

2.1 基于鄰域的社會化推薦算法

假設給定一個社交網絡及其用戶行為數據集，社交網絡列出了用戶之間的好友關系，用戶行為數據集給出了不同用戶的歷史行為和興趣數據，在這種情況，給用戶推薦好友喜歡的物品集合，其算法思想：

用戶u 對物品i 的興趣pui可以通過如下公式（1）計算：其中out(u)是用戶u 的好友集合，如果用戶v 喜歡物品i，則rvi=1，否則rvi=0。另外，要注意的是，在用戶u 的好友中，不同的好友和用戶u 的熟悉程度和興趣相似度也是不同的。因而，應該在推薦算法中考慮好友和用戶的熟悉程度以及興趣相似度，由公式（2）所示：wui由兩部分相似度構成，一部分是用戶u和用戶v 的熟悉程度，另一部分是用戶u 和用戶v 的興趣相似度。

用戶u 和用戶v 的熟悉程度主要描述用戶u 和v 在現實生活中的熟悉程度。這里熟悉度依據用戶之間的共同好友比例來度量。熟悉程度由公式（3）表示。用戶u 和用戶v 的興趣相似度的度量方法是：如果兩個用戶喜歡的物品集合重合度很高，兩個用戶的興趣相似度就很高。興趣相似度由公式（4）表示。其中N(u)是用戶u 喜歡的物品集合。

2.2 基于圖的社會化推薦算法

社交網站中存在兩種關系，一種是用戶對物品的興趣關系，一種是用戶之間的社交網絡關系。通過圖模型來表示這兩種關系，便于對用戶進行個性化推薦。用社交網絡圖來表示用戶的社交關系，用戶物品二分圖來描述用戶對物品的行為，這兩個圖可以合并成一個圖。如圖1，該圖上有用戶頂點（圓圈）和物品頂點（方塊）兩種頂點。若用戶u對物品i 產生過行為，那么兩個節點之間就有邊相連。圖1 中用戶A對物品a、e 產生過行為。如果用戶u 和v 是好友，有一條邊連接這兩個用戶，圖中用戶A 和B、D 是好友。

在社交網絡中，除了常見的、用戶和用戶之間直接的社交網絡關系，還有一種關系，即兩個用戶屬于同一個社群。可以加入一種節點表示社群（如圖2，最左邊一列的節點，六邊框），而如果用戶屬于某一社群，圖中就有一條邊聯系用戶對應的節點和社群對應的節點。

圖1 社交網絡圖和用戶物品二分圖的結合

圖2 融合兩種社交網絡信息的圖模型

在定義完圖中的頂點和邊后，需要定義邊的權重，其中用戶和用戶之間邊的權重可以定義為用戶之間的相似度的α倍（包括熟悉程度和興趣相似度），而用戶和物品之間的權重可以定義為用戶對物品喜歡程度的α倍。α 和β 需要根據應用的需求確定。如果希望用戶好友的行為對推薦結果產生比較大的影響，就選擇比較大的α，相反，如果希望用戶的歷史行為對推薦結果產生比較大的影響，就選擇比較大的β。

在定義完圖中的頂點、邊和邊的權重后，可以利用PersonalRank算法[3]度量圖中任兩個頂點之間的相關性，從而給每個用戶生成推薦結果。具體如下：假設要給用戶u 進行個性化推薦，可以從用戶u 對應的節點vu開始在用戶物品二分圖上進行隨機游走，游走到任何一個節點時，首先按照概率α 決定是繼續游走，還是停止這次游走并從vu節點開始重新游走。如果決定繼續游走，那么就從當前節點指向的節點中按照均勻分布隨機選擇一個節點作為游走下次經過的節點。這樣，經過很多次隨機游走后，每個物品節點被訪問到的概率會收斂到一個數。最終的推薦列表中物品的權重就是物品節點的訪問概率。

3 實際系統中的社會化推薦算法

基于鄰域的社會化推薦算法比較簡單，在實際系統中卻是難以操作的，因為該算法需要事先獲得用戶所有好友的歷史行為數據，而這一操作在實際系統中是比較重的操作，因為大型網站中用戶數目非常龐大，用戶的歷史行為記錄也非常龐大，所以不太可能將用戶的所有行為都緩存在內存中，只能在數據庫前做一個熱數據的緩存。如果需要比較實時的數據，這個緩存中的數據就要比較頻繁地更新，因此避免不了數據庫的查詢，然而，數據庫查詢一般是很慢的，特別是針對行為很多的用戶更是如此。因而，若一個算法再給一個用戶做推薦時，需要他所有好友的歷史行為數據，這在實際環境中是比較困難的。

為了讓它能夠具有比較快的響應時間，需要改進基于鄰域的社會化推薦算法。改進的方法有兩種：一種是兩處截斷法，第一處截斷就是在拿用戶好友集合時并不拿出用戶所有的好友，而是只拿出和用戶相似度最高的N 個好友（N 取一個比較小的數），從而給該用戶做推薦時可以只查詢N 次用戶歷史行為接口。第一處截斷在查詢每個用戶的歷史行為時，可以只返回用戶最近1 個月的行為，這樣就可以在用戶行為緩存中緩存更多用戶的歷史行為數據，從而加快查詢用戶歷史行為接口的速度。另一種解決方法是重新設計數據庫。通過前面分析可以發現，社會化推薦中關鍵的操作就是獲得用戶所有好友的行為數據，然后通過一定的聚合展示給用戶。如果對照一下微博，就會發現微博中每個用戶都有個信息墻，這個墻上實時展示著用戶關注的所有好友的動態。因此，只要能夠實現這個信息墻，就能夠實現社會化推薦算法。Twitter 給每個用戶維護一個消息隊列，當一個用戶發表一條微博時，所有關注他的用戶的消息隊列中都會加入這條微博。這樣用戶獲取信息墻時可以直接讀消息隊列，所有終端用戶的讀操作很快。Twitter 這種架構思想[4]移植到社會化推薦系統中，其具體設計為：首先，為每個用戶維護一個消息隊列，用于存儲他的推薦列表；接著，當一個用戶喜歡一個物品時，就將（物品ID、用戶ID 和時間）這條記錄寫入關注該用戶的推薦列表消息隊列中；最后，當用戶訪問推薦系統時，讀出他的推薦列表消息隊列，對于這個消息隊列中的每個物品，重新計算該物品的權重。計算權重時需要考慮物品在隊列中出現的次數，物品對應的用戶和當前用戶的熟悉程度、物品的時間戳。同時計算出每個物品被哪些好友喜歡過，用這些好友作為物品的推薦解釋。

4 結束語

社會化推薦得到許多網站的重視，一方面好友推薦可以增加推薦的信任度，好友往往是用戶最信任的，用戶往往不一定信任計算機的智能，但會信任好朋友的推薦。另一方面，社交網絡可以解決冷啟動問題，當一個新用戶通過微博或者Facebook 賬號登錄網站時，可以從社交網站中獲取用戶的好友列表，然后給用戶推薦好友在網站上喜歡的物品。從而可以在沒有用戶行為記錄時就給用戶提供較高質量的推薦結果，部分解決了推薦系統的冷啟動問題。當然，社會化推薦也有不足，其中最主要的是就是很多時候并不一定能提高推薦算法的離線精度（準確率和召回率）。特別是在基于社交圖譜數據的推薦系統中，因為用戶的好友關系不是基于共同興趣產生的，所以用戶好友的興趣往往和用戶興趣并不一致。

［1］http：//blog.nielsen.com/nielsenwire/consumer/globe-advertising-consumers-trustreal-friends-and-virtual-strangers-the-most/[OL].

［2］項亮.推薦系統實踐[M].人民郵電出版社，2012，6.

［3］Fouss Francois，Pirotte Alain.Random-walk Computation of Similarities between Nodes of a Graph with Application to Collaborative Recommendation [J].IEEE Transactions on Knowledge and Data Engineering，2007.

［4］http：//www.infoq.com/news/2009/06/Twitter-Architecture[OL].

［5］MaayanRoth，AssafBen-David.Suggesting Friends Using the Implicit Social Graph[J].ACM 2010.