社交網絡中基于用戶投票的推薦機制

劉錫文 蔣俊杰

(1東南大學計算機科學與工程學院, 南京 211189)

(2上海貝爾股份有限公司, 上海 201206)

社交網絡可定義為基于網絡的服務.它允許用戶在一個有界限的系統中構建公開或半公開的資料,聯系分享連接的用戶,觀察并詳細研究系統中由其他用戶所建立的這一系列連接．不同社交網絡中的這些連接的性質和命名方法可能會不同[1]．交友和維持人際關系是傳統社交網絡的2種作用．按照傳遞性理論[2],社交網絡中互為好友關系的用戶更容易通過彼此的好友擴展自己的社交圈．社交網絡中的人際關系也是基于這種理論形成并發展起來的,但這種方式使得用戶在社交網絡中交互的對象大多數是日常生活中的朋友,即人們交互的對象基本上是和他們有強連接關系的人,而忽視了弱連接[3]的作用．

推薦機制是在電子商務領域發展起來的,屬于信息過濾的一種應用,使用基于物品特點的模型或者基于用戶社會環境的模型,來預測用戶對那些還沒有認真考慮過的物品或社會元素的喜愛程度[4]．但是目前推薦機制已經不僅僅局限于電子商務領域．自從首批關于協同過濾的文獻[4-6]發表以來推薦機制已經應用到各行各業中,推薦算法是其中最核心和關鍵的部分,在很大程度上決定了推薦性能的優劣[7]．

考慮到目前社交網絡中推薦機制的不足,本文將傳統的用戶對網絡信息的瀏覽、評論、轉發等操作以及時間因素與用戶主動性投票相結合,研究并設計了基于用戶投票的熱點信息推薦算法,從而為用戶提供熱點信息的推薦服務．另外,將用戶對網絡信息的投票與瀏覽情況相結合,確定此用戶的興趣度,進而提出基于用戶投票的個性化好友推薦算法,為用戶提供個性化的好友推薦服務．

1 基于用戶投票的熱點信息推薦機制

1.1 基于用戶投票的熱點信息推薦算法

投票是用戶根據其對信息的理解表示贊同或反對的操作．設Wscore為根據用戶投票情況計算出的信息投票得分．用戶可以投2種票,即贊成票和反對票．信息投票得分最直觀的計算方式有2種：① 得分=贊成票數-反對票數;② 得分=贊成票數/總票數.但是這2種方式都有缺陷．

第1種方式沒有考慮贊成票占總票數的比重．第2種方式在總票數足夠大的情況下是正確的,但在總票數很少時會出現誤差,因此需要解決小樣本情況下好評率準確性的問題．1927年Wilson提出了一個被稱為Wilson score interval的修正公式[8-9],很好地解決了小樣本準確性的問題，即

(1)

(2)

(3)

式中，R表示信息整體得分；Wviews為信息的瀏覽次數，log10Wviews表示信息瀏覽次數對信息整體得分的影響，采用以10為底的對數是為了使前10個瀏覽者的權重和后90個瀏覽者的權重一致.Wfors為信息的轉發次數，Wscore(Wfors+1)對信息整體得分有決定性影響，因為轉發次數本身就代表信息的傳播特性，信息傳播得越遠越廣，在一定程度上反映出信息越有價值，將其次數加1是為了使用戶轉發次數為零時不對信息整體得分有影響.信息投票得分是隨著轉發次數的增多而成倍增長的，但是如果沒人投票，那么即使有再多的人轉發，這一項的值仍是零，這在一定程度上防止了某些無信息量的信息成為熱點信息.Wcoms為信息的評論次數，Wcoms/k表示評論次數對信息整體得分的影響，這里的評論次數是凈評論次數，這樣可避免用戶圍繞一條信息進行聊天從而增加評論次數，進而使整體得分升高這種情況的發生.參數k起到拉低評論次數對整體得分影響的作用，因為評論次數多的信息不一定有價值，有可能存在名人效應或者只是充當朋友們之間的聊天工具等.Wage為距離信息發布的時間，(Wage+1)G中的參數G為重力因子，即將信息整體得分往下拉的力量.隨著時間增長，信息整體得分下降，加1是考慮到信息的傳播需要一定的時間，同時也保證整個公式的分母不為零.

1.2 仿真實驗

1.2.1 信息瀏覽次數的影響

本節只考慮信息瀏覽次數對信息整體得分的影響.首先將信息投票得分、轉發次數和評論次數均置為零.然后分析隨著時間增長不同的瀏覽次數對信息整體得分的影響.信息的瀏覽次數Wviews分別取10，100，1000，10000，實驗結果如圖1所示.

由圖1可知，信息的瀏覽次數越多，R值越大，信息的排名就越靠前，但是隨著信息瀏覽次數的增多，信息整體得分并沒有很大的變化，這就保證了所有瀏覽者的權重是一致的，即瀏覽次數越多對信息整體得分的影響越小.另外，隨著時間的增長，R值在逐漸降低，即熱點信息具有時效性.

圖1 信息瀏覽次數對信息整體得分的影響

1.2.2 信息評論次數的影響

對一條信息來說，其瀏覽次數大于等于評論次數.如果要分析評論次數對信息排名的影響，就要先確定瀏覽次數的值，然后評論次數取一系列小于等于瀏覽次數的值.這里Wviews取10000,Wcoms分別取10，100，1000，10000.實驗結果見圖2.

圖2 信息評論次數對信息整體得分的影響

由圖2可知，信息整體得分隨著評論次數的增多逐漸升高，并且評論次數越多，對信息整體得分的影響越大，當Wcoms為1000和10000時，R值約有10倍的差距.另外，隨時間增加，R值也在逐漸降低，即使R值再大，經過一段時間后也會變得很小，這再次說明了熱點信息具有時效性.通過對比圖1和圖2可知，在同等條件下，信息評論次數對信息整體得分的影響遠大于信息瀏覽次數對信息整體得分的影響，因此當用戶只對信息進行瀏覽和評論操作時，信息的評論次數對信息整體得分起主導作用.

1.2.3 信息投票得分及信息轉發次數的影響

本節分析不同信息投票得分和轉發次數對信息整體得分的影響.由于信息的瀏覽次數大于等于轉發次數，所以取Wviews=10000,Wcoms=0,Wfors分別取10，100，1000和10000，信息投票得分Wscore分別取10，25，50和75，實驗結果如圖3所示.

由圖3可知,在信息投票得分確定的情況下,信息整體得分隨著轉發次數的增多而升高,并且轉發的次數越多對信息整體得分的影響越大．信息投票得分越高,整體得分就越高,排名就越靠前,并且信息整體得分幾乎是隨著投票得分成倍增長的,這就說明當信息投票得分和信息轉發次數達到一定程度時,這2個因素在算法中起主導作用．而且通過與圖1和圖2作對比,也會發現這2個因素對信息整體得分的影響要大于同等條件下瀏覽次數和評論次數對信息整體得分的影響．

圖3 信息投票得分和轉發次數對信息整體得分的影響

1.2.4 算法有效性驗證

本節通過新浪微博提供的API提取相關數據來驗證算法的有效性．首先提取用戶ID,然后通過用戶ID取得其所發布的微博ID,進而取得相應的評論數和轉發數．所取得的微博ID均來自不同用戶,以保證數據的有效性．1.2.3節已經說明信息的轉發次數和投票得分對信息整體得分起主導作用,但也要保證熱點信息的質量,因為信息整體得分很高也可能是轉發次數很多但投票得分不高引起的,這類信息不應是熱點信息.此算法的目的是給用戶推薦有價值的熱點信息,所以將提取到的數據代入到式(3)中,并且通過賦予不同的投票得分來驗證算法的有效性．取1000條微博的評論數和轉發數,信息的投票得分Wscore取10,實驗結果如圖4(a)所示．

由圖4(a)可知,大部分信息的轉發次數很少,整體得分不高,這也符合實際情況．只有少部分信息的轉發次數很多,這些信息才有可能成為熱點信息.當信息的投票得分為10時,這些信息的整體得分非常高,系統就會推薦這些信息給用戶作為熱點信息．當信息的投票得分為20和50時,其整體得分也得到提高,如圖4(b)、(c)所示．

信息的轉發次數越多表示信息傳播得越遠越廣,用戶的參與度越高;信息投票得分越高表示信息的質量越高,越有價值．因此，由于這2個因素都高而導致的整體得分高的信息將作為熱點信息被推薦．

2 基于用戶投票的個性化信息與個性化好友推薦機制

2.1 基于用戶投票的個性化好友推薦算法

在進行個性化好友推薦之前首先對信息進行簡單的分類,并在此基礎上給出興趣度的概念,即用戶對某類信息感興趣的程度．要想知道用戶的興趣度,就要挖掘用戶對信息的一系列操作,而評論和轉發操作都是在用戶瀏覽信息的基礎上進行的,用戶對信息進行瀏覽、評論、轉發就說明其可能對某類信息感興趣．但是這些操作都不能確定用戶是否真的對這些信息感興趣,即無法確定其可靠性,這時就要結合用戶的主動性投票來確定用戶到底對哪些信息感興趣．興趣度計算公式如下:

圖4 熱點信息分布

I=aCviews(1+Cvotes)

(4)

式中,Cviews為用戶對某類信息的瀏覽次數，aCviews表示用戶對某類信息的瀏覽次數對興趣度的影響,系數a∈(0，1),起到降低瀏覽次數對興趣度影響的作用,因為用戶瀏覽的信息不一定是感興趣的信息;Cvotes為用戶對某類信息投贊成票的次數，aCviews(1+Cvotes)表示用戶對某類信息的瀏覽和投票情況對興趣度的影響．如果用戶投票說明已經瀏覽過該信息(即用戶對某類信息投贊成票的次數要小于等于瀏覽次數,Cvotes≤Cviews),所以興趣度會隨著投票次數的增加而成倍增長,而Cvotes=0時則只有瀏覽次數的多少表示興趣度的大小,因此興趣度會較低．另外,考慮到用戶的興趣度會發生變化,通過式(4)計算出來的是一段時間內的興趣度．在用戶不活躍時計算其前一段時間內的興趣度,以適應用戶的需求．

基于興趣度的概念,系統可以提供個性化的好友推薦服務．首先通過用戶的主動性投票確定用戶的興趣度,然后根據用戶的興趣度分析對某類信息感興趣的其他用戶,如果其他用戶的興趣度和當前用戶很接近,說明他們感興趣的信息也相近,因此系統就會推薦這些用戶給當前用戶．

2.2 仿真實驗

2.2.1 用戶對某類信息的瀏覽次數和投票情況對興趣度的影響

本節根據式(4)分析用戶對某類信息的投票以及瀏覽次數對興趣度的影響,這里參數a取0.8．興趣度是根據用戶在一段時間內對各類信息的投票和瀏覽情況得出的．當用戶不活躍時,再計算前一段時間內的興趣度,以適應用戶興趣的變化．用戶在一段時間內對某類信息的瀏覽次數Cviews取0～100,贊成票數量小于等于瀏覽次數,所以Cvotes分別取0,30,50和80,據此來分析這2個因素對興趣度的影響．實驗結果如圖5所示．

圖5 用戶對某類信息瀏覽次數和投票情況對興趣度的影響

由圖5可知,隨著用戶對某類信息瀏覽次數的增加,興趣度逐漸增大,并且投票得分越高,興趣度增加得越快．如果用戶只是瀏覽某類信息而沒有進行投票,那么興趣度會非常低,說明用戶對這類信息沒有什么興趣．用戶對某類信息的投票情況恰恰反映了其對這類信息感興趣的程度,投票得分越高說明用戶對這類信息越感興趣,那么相應的興趣度也就越高．這說明興趣度的大小真實地反映了用戶對某類信息感興趣的程度,從而也就證明了以興趣度為基礎的個性化好友推薦的合理性．

2.2.2 算法有效性驗證

為了驗證算法的有效性,引入MovieLens[10]數據集,在此數據集中,用戶對其看過的電影進行評分,分值為1～5．本實驗使用MovieLens中的小規模數據庫,其中包含943個獨立用戶對1682部電影的1.0×105次評分,這1682部電影被分為19個類別,每部電影屬于一個或多個類別．該庫中有5組數據:u1.base和u1.test, u2.base和u2.test,…,u5.base和u5.test．這些數據都是80%作為訓練集,20%作為測試集．首先將式(4)應用于訓練集,調整參數a,以便獲得更好的算法推薦值與訓練集中用戶打分值的擬合度．因此,必須對數據進行處理,同時為了適應本文提出的個性化好友推薦算法,把得分為4分和5分的電影認為是用戶會投贊成票的信息．然后分別統計出u1.base,u2.base, …, u5.base中各用戶看過的電影總數量和得分為4分和5分的電影數量以及在各個類別下用戶看過的電影總數量和得分為4分和5分的電影數量．根據5組數據中用戶看過的得分為4分和5分電影數量占用戶看過電影總數量的比例的平均值來確定式(4)中的參數a,實驗數據如表1所示．其中,nvote表示用戶看過的得分為4分和5分的電影數量,nsum表示用戶看過的電影總數量．

表1 用戶感興趣的電影數量占看過電影總數量的比例

由表1可知,這個比例的平均值為0.578,因此把式(4)中的參數a取為0.6．

下面把算法應用于測試集,在943個獨立用戶中隨機抽取3個,通過比較式(4)計算出來的興趣度和用戶確實感興趣的電影數量來驗證算法的有效性．實驗結果如圖6所示．

圖6中的用戶ID分別為178,532,749,橫坐標i為電影類別．通過對比圖6(a)～(c)與圖6(d)～(f)可知,根據式(4)計算出來的興趣度的大小和用戶感興趣的電影數量的整體趨勢基本一致,這說明了式(4)的有效性,而個性化的好友推薦算法都是基于式(4)的,從而也就說明了基于用戶投票的個性化好友推薦算法的有效性．

圖6 用戶感興趣的電影數量與興趣度的對比

3 結語

本文主要針對目前社交網絡中推薦機制的不足,提出了基于用戶投票的熱點信息推薦機制以及個性化好友推薦機制．眾多用戶對某條信息的投票情況反映了此信息的熱度與價值,某個用戶對眾多信息的投票情況反映了此用戶的興趣．針對2個算法進行仿真實驗,評估各因素對推薦算法的影響以及推薦的有效性．實驗結果表明,本文提出的基于用戶投票的推薦機制可以有效地進行熱點性與個性化好友的推薦．接下來將進一步研究社交網絡中推薦機制的合理性和有效性．

)

[1]Boyd D M, Ellison N B. Social network sites: definition, history, and scholarship[J].JournalofComputer-MediatedCommunication, 2008,13(1): 210-230.

[2]Snijders T A B, Bunt G G V, Steglich C E G. Introduction to stochastic actor-based models for network dynamics[J].SocialNetworks, 2010,32(1): 44-60.

[3]Granovetter M S. The strength of weak ties[J].AmericanJournalofSociology, 1973,78(6): 1360-1380.

[4]Resnick P, Varian H R. Recommender systems[J].CommunicationsoftheACM, 1997,40(3): 56-58.

[6]Schafer J B, Konstan J, Riedl J. Recommender systems in e-commerce[C]//Proceedingsofthe1stACMConferenceonElectronicCommerce. New York, 1999: 158-166.

[7]徐海玲, 吳瀟, 李曉東, 等. 互聯網推薦系統比較研究[J]. 軟件學報, 2009, 20(2): 350-362.

Xu Hailing, Wu Xiao, Li Xiaodong, et al. Comparison study of Internet recommendation system[J].JournalofSoftware, 2009,20(2): 350-362. (in Chinese)

[8]Wikipedia. Wilson score interval[EB/OL].(2011-11-03) [2012-06-31].http://en.wikipedia.org/wiki/Binomial-proportion-confidence-interval.

[9]Wilson E B. Probable inference, the law of succession, and statistical inference[J].JournaloftheAmericanStatisticalAssociation, 1927,22(158): 209-212.

[10]GroupLens Research. MovieLens data sets[EB/OL]. (2011-08-24)[2012-06-31]. http://www.grouplens.org/node/73#attachments.