社交網(wǎng)絡(luò)中基于用戶投票的推薦機(jī)制

劉錫文 蔣俊杰

(1東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院, 南京 211189)

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

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

推薦機(jī)制是在電子商務(wù)領(lǐng)域發(fā)展起來(lái)的,屬于信息過(guò)濾的一種應(yīng)用,使用基于物品特點(diǎn)的模型或者基于用戶社會(huì)環(huán)境的模型,來(lái)預(yù)測(cè)用戶對(duì)那些還沒(méi)有認(rèn)真考慮過(guò)的物品或社會(huì)元素的喜愛(ài)程度[4]．但是目前推薦機(jī)制已經(jīng)不僅僅局限于電子商務(wù)領(lǐng)域．自從首批關(guān)于協(xié)同過(guò)濾的文獻(xiàn)[4-6]發(fā)表以來(lái)推薦機(jī)制已經(jīng)應(yīng)用到各行各業(yè)中,推薦算法是其中最核心和關(guān)鍵的部分,在很大程度上決定了推薦性能的優(yōu)劣[7]．

考慮到目前社交網(wǎng)絡(luò)中推薦機(jī)制的不足,本文將傳統(tǒng)的用戶對(duì)網(wǎng)絡(luò)信息的瀏覽、評(píng)論、轉(zhuǎn)發(fā)等操作以及時(shí)間因素與用戶主動(dòng)性投票相結(jié)合,研究并設(shè)計(jì)了基于用戶投票的熱點(diǎn)信息推薦算法,從而為用戶提供熱點(diǎn)信息的推薦服務(wù)．另外,將用戶對(duì)網(wǎng)絡(luò)信息的投票與瀏覽情況相結(jié)合,確定此用戶的興趣度,進(jìn)而提出基于用戶投票的個(gè)性化好友推薦算法,為用戶提供個(gè)性化的好友推薦服務(wù)．

1 基于用戶投票的熱點(diǎn)信息推薦機(jī)制

1.1 基于用戶投票的熱點(diǎn)信息推薦算法

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

第1種方式?jīng)]有考慮贊成票占總票數(shù)的比重．第2種方式在總票數(shù)足夠大的情況下是正確的,但在總票數(shù)很少時(shí)會(huì)出現(xiàn)誤差,因此需要解決小樣本情況下好評(píng)率準(zhǔn)確性的問(wèn)題．1927年Wilson提出了一個(gè)被稱為Wilson score interval的修正公式[8-9],很好地解決了小樣本準(zhǔn)確性的問(wèn)題，即

(1)

(2)

(3)

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

1.2 仿真實(shí)驗(yàn)

1.2.1 信息瀏覽次數(shù)的影響

本節(jié)只考慮信息瀏覽次數(shù)對(duì)信息整體得分的影響.首先將信息投票得分、轉(zhuǎn)發(fā)次數(shù)和評(píng)論次數(shù)均置為零.然后分析隨著時(shí)間增長(zhǎng)不同的瀏覽次數(shù)對(duì)信息整體得分的影響.信息的瀏覽次數(shù)Wviews分別取10，100，1000，10000，實(shí)驗(yàn)結(jié)果如圖1所示.

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

圖1 信息瀏覽次數(shù)對(duì)信息整體得分的影響

1.2.2 信息評(píng)論次數(shù)的影響

對(duì)一條信息來(lái)說(shuō)，其瀏覽次數(shù)大于等于評(píng)論次數(shù).如果要分析評(píng)論次數(shù)對(duì)信息排名的影響，就要先確定瀏覽次數(shù)的值，然后評(píng)論次數(shù)取一系列小于等于瀏覽次數(shù)的值.這里Wviews取10000,Wcoms分別取10，100，1000，10000.實(shí)驗(yàn)結(jié)果見(jiàn)圖2.

圖2 信息評(píng)論次數(shù)對(duì)信息整體得分的影響

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

1.2.3 信息投票得分及信息轉(zhuǎn)發(fā)次數(shù)的影響

本節(jié)分析不同信息投票得分和轉(zhuǎn)發(fā)次數(shù)對(duì)信息整體得分的影響.由于信息的瀏覽次數(shù)大于等于轉(zhuǎn)發(fā)次數(shù)，所以取Wviews=10000,Wcoms=0,Wfors分別取10，100，1000和10000，信息投票得分Wscore分別取10，25，50和75，實(shí)驗(yàn)結(jié)果如圖3所示.

由圖3可知,在信息投票得分確定的情況下,信息整體得分隨著轉(zhuǎn)發(fā)次數(shù)的增多而升高,并且轉(zhuǎn)發(fā)的次數(shù)越多對(duì)信息整體得分的影響越大．信息投票得分越高,整體得分就越高,排名就越靠前,并且信息整體得分幾乎是隨著投票得分成倍增長(zhǎng)的,這就說(shuō)明當(dāng)信息投票得分和信息轉(zhuǎn)發(fā)次數(shù)達(dá)到一定程度時(shí),這2個(gè)因素在算法中起主導(dǎo)作用．而且通過(guò)與圖1和圖2作對(duì)比,也會(huì)發(fā)現(xiàn)這2個(gè)因素對(duì)信息整體得分的影響要大于同等條件下瀏覽次數(shù)和評(píng)論次數(shù)對(duì)信息整體得分的影響．

圖3 信息投票得分和轉(zhuǎn)發(fā)次數(shù)對(duì)信息整體得分的影響

1.2.4 算法有效性驗(yàn)證

本節(jié)通過(guò)新浪微博提供的API提取相關(guān)數(shù)據(jù)來(lái)驗(yàn)證算法的有效性．首先提取用戶ID,然后通過(guò)用戶ID取得其所發(fā)布的微博ID,進(jìn)而取得相應(yīng)的評(píng)論數(shù)和轉(zhuǎn)發(fā)數(shù)．所取得的微博ID均來(lái)自不同用戶,以保證數(shù)據(jù)的有效性．1.2.3節(jié)已經(jīng)說(shuō)明信息的轉(zhuǎn)發(fā)次數(shù)和投票得分對(duì)信息整體得分起主導(dǎo)作用,但也要保證熱點(diǎn)信息的質(zhì)量,因?yàn)樾畔⒄w得分很高也可能是轉(zhuǎn)發(fā)次數(shù)很多但投票得分不高引起的,這類信息不應(yīng)是熱點(diǎn)信息.此算法的目的是給用戶推薦有價(jià)值的熱點(diǎn)信息,所以將提取到的數(shù)據(jù)代入到式(3)中,并且通過(guò)賦予不同的投票得分來(lái)驗(yàn)證算法的有效性．取1000條微博的評(píng)論數(shù)和轉(zhuǎn)發(fā)數(shù),信息的投票得分Wscore取10,實(shí)驗(yàn)結(jié)果如圖4(a)所示．

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

信息的轉(zhuǎn)發(fā)次數(shù)越多表示信息傳播得越遠(yuǎn)越廣,用戶的參與度越高;信息投票得分越高表示信息的質(zhì)量越高,越有價(jià)值．因此，由于這2個(gè)因素都高而導(dǎo)致的整體得分高的信息將作為熱點(diǎn)信息被推薦．

2 基于用戶投票的個(gè)性化信息與個(gè)性化好友推薦機(jī)制

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

在進(jìn)行個(gè)性化好友推薦之前首先對(duì)信息進(jìn)行簡(jiǎn)單的分類,并在此基礎(chǔ)上給出興趣度的概念,即用戶對(duì)某類信息感興趣的程度．要想知道用戶的興趣度,就要挖掘用戶對(duì)信息的一系列操作,而評(píng)論和轉(zhuǎn)發(fā)操作都是在用戶瀏覽信息的基礎(chǔ)上進(jìn)行的,用戶對(duì)信息進(jìn)行瀏覽、評(píng)論、轉(zhuǎn)發(fā)就說(shuō)明其可能對(duì)某類信息感興趣．但是這些操作都不能確定用戶是否真的對(duì)這些信息感興趣,即無(wú)法確定其可靠性,這時(shí)就要結(jié)合用戶的主動(dòng)性投票來(lái)確定用戶到底對(duì)哪些信息感興趣．興趣度計(jì)算公式如下:

圖4 熱點(diǎn)信息分布

I=aCviews(1+Cvotes)

(4)

式中,Cviews為用戶對(duì)某類信息的瀏覽次數(shù)，aCviews表示用戶對(duì)某類信息的瀏覽次數(shù)對(duì)興趣度的影響,系數(shù)a∈(0，1),起到降低瀏覽次數(shù)對(duì)興趣度影響的作用,因?yàn)橛脩魹g覽的信息不一定是感興趣的信息;Cvotes為用戶對(duì)某類信息投贊成票的次數(shù)，aCviews(1+Cvotes)表示用戶對(duì)某類信息的瀏覽和投票情況對(duì)興趣度的影響．如果用戶投票說(shuō)明已經(jīng)瀏覽過(guò)該信息(即用戶對(duì)某類信息投贊成票的次數(shù)要小于等于瀏覽次數(shù),Cvotes≤Cviews),所以興趣度會(huì)隨著投票次數(shù)的增加而成倍增長(zhǎng),而Cvotes=0時(shí)則只有瀏覽次數(shù)的多少表示興趣度的大小,因此興趣度會(huì)較低．另外,考慮到用戶的興趣度會(huì)發(fā)生變化,通過(guò)式(4)計(jì)算出來(lái)的是一段時(shí)間內(nèi)的興趣度．在用戶不活躍時(shí)計(jì)算其前一段時(shí)間內(nèi)的興趣度,以適應(yīng)用戶的需求．

基于興趣度的概念,系統(tǒng)可以提供個(gè)性化的好友推薦服務(wù)．首先通過(guò)用戶的主動(dòng)性投票確定用戶的興趣度,然后根據(jù)用戶的興趣度分析對(duì)某類信息感興趣的其他用戶,如果其他用戶的興趣度和當(dāng)前用戶很接近,說(shuō)明他們感興趣的信息也相近,因此系統(tǒng)就會(huì)推薦這些用戶給當(dāng)前用戶．

2.2 仿真實(shí)驗(yàn)

2.2.1 用戶對(duì)某類信息的瀏覽次數(shù)和投票情況對(duì)興趣度的影響

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

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

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

2.2.2 算法有效性驗(yàn)證

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

表1 用戶感興趣的電影數(shù)量占看過(guò)電影總數(shù)量的比例

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

下面把算法應(yīng)用于測(cè)試集,在943個(gè)獨(dú)立用戶中隨機(jī)抽取3個(gè),通過(guò)比較式(4)計(jì)算出來(lái)的興趣度和用戶確實(shí)感興趣的電影數(shù)量來(lái)驗(yàn)證算法的有效性．實(shí)驗(yàn)結(jié)果如圖6所示．

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

圖6 用戶感興趣的電影數(shù)量與興趣度的對(duì)比

3 結(jié)語(yǔ)

本文主要針對(duì)目前社交網(wǎng)絡(luò)中推薦機(jī)制的不足,提出了基于用戶投票的熱點(diǎn)信息推薦機(jī)制以及個(gè)性化好友推薦機(jī)制．眾多用戶對(duì)某條信息的投票情況反映了此信息的熱度與價(jià)值,某個(gè)用戶對(duì)眾多信息的投票情況反映了此用戶的興趣．針對(duì)2個(gè)算法進(jìn)行仿真實(shí)驗(yàn),評(píng)估各因素對(duì)推薦算法的影響以及推薦的有效性．實(shí)驗(yàn)結(jié)果表明,本文提出的基于用戶投票的推薦機(jī)制可以有效地進(jìn)行熱點(diǎn)性與個(gè)性化好友的推薦．接下來(lái)將進(jìn)一步研究社交網(wǎng)絡(luò)中推薦機(jī)制的合理性和有效性．

)

[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]徐海玲, 吳瀟, 李曉東, 等. 互聯(lián)網(wǎng)推薦系統(tǒng)比較研究[J]. 軟件學(xué)報(bào), 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.