一種基于相似社團(tuán)和節(jié)點(diǎn)角色劃分的社交網(wǎng)絡(luò)用戶推薦方案

鐘曉宇，劉宴兵，肖云鵬

(重慶郵電大學(xué) 網(wǎng)絡(luò)與信息安全技術(shù)重慶市工程實(shí)驗(yàn)室，重慶 400065)

?

一種基于相似社團(tuán)和節(jié)點(diǎn)角色劃分的社交網(wǎng)絡(luò)用戶推薦方案

鐘曉宇，劉宴兵，肖云鵬

(重慶郵電大學(xué) 網(wǎng)絡(luò)與信息安全技術(shù)重慶市工程實(shí)驗(yàn)室，重慶 400065)

摘要：針對(duì)現(xiàn)有的社交網(wǎng)絡(luò)用戶推薦方案中主要考慮個(gè)體相似性問(wèn)題以及節(jié)點(diǎn)角色無(wú)層次差別的問(wèn)題，提出一種基于相似社團(tuán)和節(jié)點(diǎn)角色劃分的推薦方案。在傳統(tǒng)的用戶相似度計(jì)算基礎(chǔ)上，從社團(tuán)結(jié)構(gòu)和屬性兩方面，綜合考慮社團(tuán)間聯(lián)系的緊密程度和社團(tuán)用戶興趣愛(ài)好相似程度，提出一種社團(tuán)相似度的計(jì)算方法；其次，從用戶節(jié)點(diǎn)所在的社團(tuán)內(nèi)部和外部2個(gè)維度度量節(jié)點(diǎn)間緊密度，并據(jù)此度量節(jié)點(diǎn)的社會(huì)影響力，進(jìn)而將它們劃分成不同角色，實(shí)現(xiàn)用戶推薦的差異化。通過(guò)新浪微博真實(shí)社交數(shù)據(jù)對(duì)方案進(jìn)行驗(yàn)證，實(shí)驗(yàn)結(jié)果表明，該方案適用于存在社團(tuán)現(xiàn)象的社交網(wǎng)絡(luò)層次化用戶推薦，并具有良好的推薦效果。

關(guān)鍵詞：相似社團(tuán)；節(jié)點(diǎn)角色；用戶推薦；社交網(wǎng)絡(luò)

0引言

隨著信息化社會(huì)的到來(lái)，互聯(lián)網(wǎng)已成為人們?nèi)粘Ｉ钪械闹匾M成部分。在線社交網(wǎng)絡(luò)，如Facebook,Twitter等，更是近年來(lái)互聯(lián)網(wǎng)最炙手可熱的產(chǎn)品之一。但是，社交網(wǎng)站因其數(shù)據(jù)量巨大、數(shù)據(jù)結(jié)構(gòu)多樣化以及數(shù)據(jù)關(guān)系復(fù)雜化的特點(diǎn)，需要提高用戶獲取信息的效率，挖掘到滿足用戶個(gè)性化需求的信息資源的方法[1]。推薦技術(shù)就是在此種背景下被提出和發(fā)展的，為用戶提供高質(zhì)量的用戶推薦、項(xiàng)目或服務(wù)推薦，不僅可以增加用戶粘性，也幫助企業(yè)了解用戶需求，并開(kāi)啟了社交廣告新模式。用戶推薦作為推薦應(yīng)用中一項(xiàng)重要的服務(wù)，近年來(lái)也成為了研究熱點(diǎn)，通過(guò)計(jì)算用戶相似性，為用戶推薦還未形成鏈接但相似性高的其他用戶[2-3]。

目前大多數(shù)的用戶推薦方案的一個(gè)重要前提是2個(gè)節(jié)點(diǎn)相似性越大[4-5]，他們之間新增關(guān)注的可能性就越大，主要有以Jaccard相關(guān)系數(shù)[6]、Salton相似系數(shù)[7]為代表的基于共同鄰居的相似性指標(biāo)，以Adamic-Adar指標(biāo)[8]為代表的基于節(jié)點(diǎn)度的相似性指標(biāo)；Newman等人也考慮2個(gè)節(jié)點(diǎn)之間的路徑數(shù)對(duì)相似性產(chǎn)生的影響，提出基于路徑的相似性指標(biāo)LHN-II[9]；其他相似性算法還包括基于隨機(jī)游走定義的SimRank指標(biāo)[10-11]和重啟型隨機(jī)游走算法[12-13]。由此可以看出，傳統(tǒng)的用戶推薦方案主要以個(gè)體用戶的相似度為基礎(chǔ)，少有考慮群體因素的影響。因此，本文在此基礎(chǔ)上，將個(gè)體間相似研究擴(kuò)展為群體間相似研究，綜合考慮社團(tuán)間聯(lián)系的緊密程度和社團(tuán)用戶興趣愛(ài)好相似程度，從社團(tuán)結(jié)構(gòu)和屬性兩方面，提出一種社團(tuán)相似度的定義及計(jì)算方法。

另一方面，基于節(jié)點(diǎn)角色的社會(huì)網(wǎng)絡(luò)應(yīng)用研究也具有重要意義。Guimera, R.和Scripps, J[14-15]等人將其應(yīng)用于社交網(wǎng)絡(luò)、語(yǔ)義網(wǎng)絡(luò)的鏈接挖掘問(wèn)題。也有科學(xué)研究通過(guò)用戶節(jié)點(diǎn)行為模式來(lái)劃分角色，如Backstrom和Kumar R等人根據(jù)用戶角色分析用戶群體之間的關(guān)聯(lián)[16]，Menasce等人利用角色劃分優(yōu)化電子商務(wù)的計(jì)算資源[17]，朱天等學(xué)者利用用戶在社交網(wǎng)絡(luò)中顯露的情感行為特征將用戶聚類，劃分成不同類型[18]。綜上可知，目前少有研究將節(jié)點(diǎn)角色劃分應(yīng)用到推薦領(lǐng)域，本文則創(chuàng)新地將其引入到用戶推薦方案中，實(shí)現(xiàn)一種多角色層次的差異化推薦。

考慮到上述傳統(tǒng)用戶推薦方案中存在的不足，本文提出一種基于相似社團(tuán)和節(jié)點(diǎn)角色劃分的推薦方案。將傳統(tǒng)的僅在個(gè)體之間進(jìn)行的相似度計(jì)算擴(kuò)展到群體之間進(jìn)行，從社團(tuán)結(jié)構(gòu)和屬性兩方面提出一種社團(tuán)相似度的定義及計(jì)算方法。以2個(gè)社團(tuán)的公共相鄰社團(tuán)數(shù)占相鄰社團(tuán)總數(shù)的比例來(lái)度量它們的結(jié)構(gòu)相似度；并利用社團(tuán)用戶的標(biāo)簽信息將社團(tuán)屬性分類，2個(gè)社團(tuán)屬性特征向量相似度即為它們的屬性相似度。針對(duì)現(xiàn)有的推薦方案中推薦方式的單一性問(wèn)題，本文假設(shè)在網(wǎng)絡(luò)中擁有相似結(jié)構(gòu)的用戶節(jié)點(diǎn)具有相似的社會(huì)影響力，從社團(tuán)內(nèi)部和外部2個(gè)維度度量該節(jié)點(diǎn)與其他節(jié)點(diǎn)的緊密度，得到節(jié)點(diǎn)的影響力二維坐標(biāo)，由此將它們分類，劃分成不同角色，以實(shí)現(xiàn)用戶推薦的差異化。

1問(wèn)題形式化及相關(guān)定義

1.1問(wèn)題形式化

為形式化地描述本文研究的問(wèn)題，定義社交網(wǎng)絡(luò)為一個(gè)有向圖G={V,E}，其中V={v1,v2,…,vn}是社交網(wǎng)絡(luò)中用戶節(jié)點(diǎn)集合，E?V×V為用戶間的朋友關(guān)系，若存在邊ei,j=,表示用戶vi關(guān)注用戶vj；S={s1,s2,…,sn}表示網(wǎng)絡(luò)中的社團(tuán)集合，且si?G，社團(tuán)si與社團(tuán)sj相似度定義為Simi,j。另外，令σ(i)表示節(jié)點(diǎn)vi的影響力值，τk1和τk2分別表示角色Rk劃分的范圍閾值(k∈{1,2,3,…}且k值越小，角色重要程度越高)，若τk1≤σ(i)≤τk2，則vi∈Rk。

本文研究問(wèn)題可表示為

1)在tk時(shí)刻，根據(jù)網(wǎng)絡(luò)G={V,E}得出S={s1,s2,…,sn}，計(jì)算目標(biāo)社團(tuán)si與其他社團(tuán)sj(sj?S,sj≠si)的相似度Simi,j；

2)對(duì)?vi∈si,?vj∈sj,劃分節(jié)點(diǎn)vi與vj的角色；

3)對(duì)相似度排名前TOP-N的社團(tuán)，即rank(Simi,j)≤N,?vi∈si且vi∈Rk,?vj∈sj且vj∈Rk∪Rk-1，預(yù)測(cè)tk+1時(shí)刻是否存在邊ei,j=。

1.2相關(guān)定義

通常，用戶vi與vj的相似度為兩節(jié)點(diǎn)間相似度，是基于節(jié)點(diǎn)與節(jié)點(diǎn)之間關(guān)聯(lián)關(guān)系進(jìn)行的，在過(guò)去的研究中，用戶相似度計(jì)算可分為結(jié)構(gòu)相似和屬性相似兩方面。屬性相似是指用戶的特征信息相似；結(jié)構(gòu)相似是指節(jié)點(diǎn)在網(wǎng)絡(luò)中的結(jié)構(gòu)等價(jià)性，如果2個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中共享很多相同的鄰居節(jié)點(diǎn)，則這2個(gè)節(jié)點(diǎn)被認(rèn)為結(jié)構(gòu)等價(jià)。

定義1(Jaccard相似系數(shù))：對(duì)集合X和Y,將它們的交集和并集的比值定義為2個(gè)集合的Jaccard相似性得分，計(jì)算公式為

(1)

定義2(余弦相似系數(shù))：余弦相似度用向量空間中2個(gè)向量夾角的余弦值作為衡量2個(gè)個(gè)體間差異的大小，對(duì)向量X和Y,計(jì)算公式為

(2)

定義3(結(jié)構(gòu)相似度)：設(shè)節(jié)點(diǎn)vi與節(jié)點(diǎn)vj的結(jié)構(gòu)相似度為t(vi,vj)，令N(i)為節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)集合，N(i)∩N(j)為vi與vj的共同鄰居集合，|N(i)∩N(j)|表示其數(shù)量，則節(jié)點(diǎn)vi與節(jié)點(diǎn)vj利用Jaccard系數(shù)歸一化的結(jié)構(gòu)相似度計(jì)算公式為

(3)

定義4(屬性相似度)：設(shè)節(jié)點(diǎn)vi與節(jié)點(diǎn)vj的屬性相似度為f(vi,vj)，定義節(jié)點(diǎn)vi的n個(gè)特征屬性為一個(gè)n維向量，即vi(i1,i2,i3,…,ik)，則節(jié)點(diǎn)vi和vj的基于余弦相似系數(shù)的屬性相似度計(jì)算公式為

(4)

2基于相似社團(tuán)和用戶角色的社交網(wǎng)絡(luò)用戶推薦方案

2.1方案架構(gòu)

本方案可劃分成4個(gè)關(guān)鍵部分，如圖1所示，包括①社團(tuán)發(fā)現(xiàn)：利用社團(tuán)發(fā)現(xiàn)算法挖掘網(wǎng)絡(luò)中存在的用戶的社交社團(tuán)；②社團(tuán)相似度計(jì)算：從結(jié)構(gòu)和屬性兩方面計(jì)算社團(tuán)相似度；節(jié)點(diǎn)角色劃分；③用戶角色劃分：利用用戶節(jié)點(diǎn)在社團(tuán)中的影響力將用戶分為不同層次的角色；④用戶推薦：在相似社團(tuán)之間進(jìn)行角色層次差異化推薦。其中①是現(xiàn)有fastGN算法應(yīng)用，②③④部分為本方案的研究重點(diǎn)。

圖1　用戶推薦方案框架Fig.1　Framework of user recommendation scheme

2.2社團(tuán)相似度

由本文第2章所述，通常根據(jù)節(jié)點(diǎn)所在網(wǎng)絡(luò)的連通性和節(jié)點(diǎn)用戶的相關(guān)屬性來(lái)計(jì)算節(jié)點(diǎn)相似度，以此類推，可將社團(tuán)整體看作網(wǎng)絡(luò)中的節(jié)點(diǎn)，從結(jié)構(gòu)和屬性兩方面來(lái)定義社團(tuán)相似度。

1)結(jié)構(gòu)相似度。2個(gè)社團(tuán)在整個(gè)網(wǎng)絡(luò)中聯(lián)系越緊密，則代表2個(gè)社團(tuán)越可能相似。因此，社團(tuán)間結(jié)構(gòu)相似度可用2個(gè)社團(tuán)公共相鄰社團(tuán)比例來(lái)衡量。

定義5(社團(tuán)間結(jié)構(gòu)相似度)：設(shè)ηi表示社團(tuán)si的相鄰社團(tuán)，社團(tuán)si與社團(tuán)sj的結(jié)構(gòu)相似度為ti,j,擴(kuò)展節(jié)點(diǎn)間結(jié)構(gòu)相似度定義為

(5)

2)屬性相似度。同一社團(tuán)中的用戶通常因?yàn)榫哂邢嗤呐d趣或偏好，如圖2所示，這些興趣或愛(ài)好往往顯示在用戶的標(biāo)簽信息中，大多數(shù)情況下，社交社團(tuán)的屬性其實(shí)是相對(duì)復(fù)雜的，可能同時(shí)屬于幾個(gè)類型，對(duì)其中個(gè)別類型更具傾向性。例如，一個(gè)社團(tuán)中所有成員的標(biāo)簽對(duì)音樂(lè)、旅行、科技、財(cái)經(jīng)這4種類型都有涉及，但是所占比重并不相同，可能科技類和財(cái)經(jīng)類所占比重高于其他2類。

圖2　社交網(wǎng)絡(luò)社團(tuán)Fig.2　Communities in social network

正是考慮到上述情況，在本文中，為計(jì)算社團(tuán)間屬性相似度，我們先計(jì)算社團(tuán)屬于每個(gè)劃分類型概率，并以特征向量的形式來(lái)表現(xiàn)，再將屬性相似度計(jì)算轉(zhuǎn)化為計(jì)算特征向量的余弦相似度。

定義6(社團(tuán)劃分類型集合)：設(shè)社團(tuán)劃分類型集合C={C1,C2,…,Cn},n為劃分類型個(gè)數(shù)。

定義7(社團(tuán)屬性特征向量)：設(shè)社團(tuán)si的屬性特征向量為fi=(i1,i2,…,in),其中ik(k∈{1,2,…,n})表示社團(tuán)屬性被劃分為第k個(gè)類型的概率。

定義8(社團(tuán)間屬性相似度)：設(shè)社團(tuán)si與社團(tuán)sj的屬性相似度為fi,j

(6)

為計(jì)算社團(tuán)屬于每個(gè)劃分類型的概率，本文中我們選擇樸素貝葉斯文檔分類法，將各個(gè)標(biāo)簽出現(xiàn)的概率用社團(tuán)屬性向量來(lái)表示，根據(jù)各用戶標(biāo)簽出現(xiàn)頻率確定社團(tuán)類型的劃分標(biāo)準(zhǔn)，即社團(tuán)劃分類型集合C={C1,C2,…,Cn}，對(duì)每個(gè)社團(tuán)，針對(duì)每一個(gè)類型Ck都將其進(jìn)行一次分類。

定義9(社團(tuán)屬性向量)：設(shè)社團(tuán)si屬性向量為Xi={Xi1,Xi2，…，Xim},社團(tuán)標(biāo)簽集中每個(gè)標(biāo)簽都為社團(tuán)的一個(gè)屬性，若社團(tuán)si有m個(gè)不同標(biāo)簽，則si有m個(gè)屬性，Xij(j∈{1,2,…,m})表示社團(tuán)si的第j個(gè)標(biāo)簽出現(xiàn)的概率。

(7)

分類結(jié)果為2個(gè)類別，即Ck=1表示屬于該類型,Ck=0表示不屬于該類型。

根據(jù)貝葉斯決策理論，社團(tuán)si屬于類型Ck的概率ik,

(8)

社團(tuán)屬性相似度算法具體步驟如下。

算法： 社團(tuán)屬性相似度

輸入：社團(tuán)si,社團(tuán)sj用戶節(jié)點(diǎn)，用戶關(guān)注關(guān)系，用戶標(biāo)簽

輸出：社團(tuán)si和社團(tuán)sj屬性相似度f(wàn)i,j

1.確定社團(tuán)劃分的n個(gè)類型及其分類標(biāo)準(zhǔn)

2.對(duì)每個(gè)劃分類型，分別將其對(duì)應(yīng)訓(xùn)練樣本進(jìn)行概率參數(shù)學(xué)習(xí),生成n個(gè)分類器

3.for分類器Ck,k:1→n

6.end for

7.updatefiandfj

8.fi,j=cos(fi,fj)

3)社團(tuán)相似度。

定義10(社團(tuán)間相似度)：設(shè)社團(tuán)si和社團(tuán)sj的社團(tuán)間相似度為結(jié)構(gòu)相似度與屬性相似度的線性組合，定義為Simi,j,ti,j表示社團(tuán)si和社團(tuán)sj的結(jié)構(gòu)相似度，fi,j表示屬性相似度，α為調(diào)節(jié)參數(shù)，取0到1之間的任意值，則Simi,j=α·ti,j+(1-α)·fi,j.

2.3社團(tuán)用戶角色劃分

本文假設(shè)滿足擁有相似的結(jié)構(gòu)的節(jié)點(diǎn)占據(jù)網(wǎng)絡(luò)中的相同角色，通過(guò)分析節(jié)點(diǎn)在自身社團(tuán)內(nèi)外的影響力來(lái)定義節(jié)點(diǎn)在網(wǎng)絡(luò)中的角色，并劃分成不同層次。

對(duì)節(jié)點(diǎn)的影響力分析，本文采用一種基于社團(tuán)結(jié)構(gòu)的二維影響力度量方法，2個(gè)維度記為節(jié)點(diǎn)的Inner值和Outter值，構(gòu)成節(jié)點(diǎn)影響力二維坐標(biāo)。如圖3所示，根據(jù)影響力二維坐標(biāo)，可將網(wǎng)絡(luò)的節(jié)點(diǎn)劃分成為3種層次的角色：核心點(diǎn)、重要點(diǎn)及普通點(diǎn)。

圖3　節(jié)點(diǎn)角色圖Fig.3　Node role division

核心點(diǎn)(Role1)：表示節(jié)點(diǎn)在社團(tuán)內(nèi)外都擁有極大的社會(huì)影響力；重要點(diǎn)(Role2)：表示節(jié)點(diǎn)在社團(tuán)外部具有很大的社會(huì)影響力；普通點(diǎn)(Role3)：表示節(jié)點(diǎn)在社團(tuán)內(nèi)外社會(huì)影響力較小。

影響力度量方法的本質(zhì)是利用PageRank算法分析節(jié)點(diǎn)在社團(tuán)內(nèi)部和外部的影響力。PageRank是一種計(jì)算網(wǎng)頁(yè)重要性排名的算法，其原理是依據(jù)從許多優(yōu)質(zhì)的網(wǎng)頁(yè)鏈接過(guò)來(lái)的網(wǎng)頁(yè)，必定還是優(yōu)質(zhì)網(wǎng)頁(yè)。

頁(yè)面pi的PageRank值計(jì)算公式為

(9)

(9)式中：c為衰減因子；L(pj)表示與頁(yè)面pj相連的頁(yè)面數(shù)量；N表示所有頁(yè)面的數(shù)量。多次迭代后PR(pi)收斂。

本文中，我們采用社團(tuán)中的每個(gè)點(diǎn)在社團(tuán)內(nèi)外的重要性來(lái)量化節(jié)點(diǎn)在所屬社團(tuán)的內(nèi)部影響力和外部影響力，節(jié)點(diǎn)影響力分析的問(wèn)題可形式化表述為：

1)對(duì)每個(gè)社團(tuán)si，對(duì)與其中每個(gè)用戶vi互為好友的用戶vj，若vj∈si,則將vj加入到用戶集合ListIn中，反之將vj加入到用戶集合ListOut中；

2)用戶vi與集合ListIn構(gòu)成有向圖G′={V′,E′},V′=vi∪ListIn；用戶vi與集合ListOut構(gòu)成有向圖G″={V″,E″}， V″=vi∪ListOut；

(10)

(11)

計(jì)算節(jié)點(diǎn)影響力二維坐標(biāo)算法具體步驟如下。

算法： 節(jié)點(diǎn)影響力二維坐標(biāo)

輸入：社團(tuán)si用戶節(jié)點(diǎn)，用戶關(guān)注關(guān)系，衰減因子β

輸出：社團(tuán)中每個(gè)用戶的Inner和Outter值

1.for everyvi∈sido

Waters 2695-2475高效液相色譜儀（配Empower 2軟件）；梅特勒-托利多（METTLER TOLEDO）XS-205電子天平（精度為0.01 mg）；上海民橋精密科學(xué)儀器有限公司SL502 N電子天平（精度0.01 g）；梅特勒-托利多（METTLER TOLEDO）FE20 pH計(jì)；昆山市超聲儀器有限公司KQ-500E型超聲波清洗器。多功能微生物自動(dòng)測(cè)量分析儀（北京先驅(qū)威峰技術(shù)開(kāi)發(fā)公司，ZY-3001V）；37℃恒溫培養(yǎng)箱；鋼管自動(dòng)放置器（北京先驅(qū)威峰技術(shù)開(kāi)發(fā)公司，ZY-300G）；三洋MLS-3780高壓蒸汽滅菌鍋；Thermo Scientific A2生物安全柜。

2.ifvi,vjare connected

3.ifvj∈sithenlistInaddvj

4.ifvj?sithenlistOutaddvj

5.end for

6. for everyvi∈sido

7.for everyvj∈V′ do

10.end do

11.end for

12.for everyvj∈V″ do

15. end do

16.end for

17.end for

2.4推薦方案

傳統(tǒng)的推薦方案是在用戶相似的基礎(chǔ)上進(jìn)行的，即2個(gè)不存在連邊的用戶節(jié)點(diǎn)之間的相似度越高，越可能形成關(guān)注。但現(xiàn)實(shí)中常存在另一種情況，2個(gè)相似社團(tuán)中的各層次用戶之間也可能形成關(guān)注關(guān)系，例如，2個(gè)研究相似課題的實(shí)驗(yàn)室中，人員可劃分成實(shí)驗(yàn)室主任、科研老師和學(xué)生3個(gè)層次，2個(gè)團(tuán)隊(duì)的學(xué)生之間可能形成關(guān)注，其中一個(gè)團(tuán)隊(duì)的部分學(xué)生也可能與另一個(gè)團(tuán)隊(duì)的個(gè)別科研老師形成關(guān)注。若2個(gè)實(shí)驗(yàn)室聯(lián)系越緊密，研究課題越相似，形成的關(guān)注關(guān)系也越多。

圖4　用戶推薦方案示意圖Fig.4　User recommendation scheme in community pair

正是考慮到上述情況，本文擴(kuò)展了傳統(tǒng)的用戶推薦方案，采用一種基于相似社團(tuán)和節(jié)點(diǎn)角色劃分的方式推薦用戶。分為如下步驟。

1)在tk時(shí)刻，根據(jù)網(wǎng)絡(luò)G={V,E}得出S={s1,s2,…,sn};

2)計(jì)算目標(biāo)社團(tuán)si與其他社團(tuán)sj(sj?S,sj≠si)相似度Simi,j;

3)對(duì)?vi∈si,?vj∈sj,根據(jù)σ(i),σ(j)分別劃分節(jié)點(diǎn)vi與vj的角色；

4)對(duì)相似度排名前TOP-N的社團(tuán)，即rank(Simi,j)≤N,?vi∈si且vi∈Rk,?vj∈sj且vj∈Rk∪Rk-1,如圖4所示，將所有滿足此條件的用戶vj推薦給用戶vi.

3實(shí)驗(yàn)和結(jié)果分析

3.1實(shí)驗(yàn)數(shù)據(jù)

1)數(shù)據(jù)集。本文采用的是新浪微博數(shù)據(jù)集，新浪微博是國(guó)內(nèi)知名社交網(wǎng)站，用戶可以關(guān)注其他用戶，或者被其他粉絲關(guān)注，可以發(fā)布微博分享圖文和轉(zhuǎn)發(fā)別人發(fā)布的微博。該數(shù)據(jù)來(lái)自文獻(xiàn)[19]的實(shí)驗(yàn)數(shù)據(jù)，包含在新浪微博平臺(tái)上注冊(cè)的170萬(wàn)用戶以及他們之間的關(guān)注關(guān)系，數(shù)據(jù)集具體信息如表1所示。

用戶關(guān)注關(guān)系數(shù)據(jù)按照抓取的時(shí)間節(jié)點(diǎn)，被分為30個(gè)時(shí)間片(即30個(gè)timestamp)，從圖5中可以看出，在每個(gè)時(shí)間片都有新增的關(guān)注關(guān)系，因此，若使用此數(shù)據(jù)集，能夠?qū)崿F(xiàn)根據(jù)部分時(shí)間片關(guān)系數(shù)據(jù)形成的網(wǎng)絡(luò)驗(yàn)證用戶節(jié)點(diǎn)在后續(xù)時(shí)間片中是否形成新的連邊，符合實(shí)驗(yàn)要求。

表1　數(shù)據(jù)集信息

圖5　關(guān)注關(guān)系增量變化Fig.5　Increment of relationships

2)數(shù)據(jù)說(shuō)明。①考慮實(shí)驗(yàn)可操作性以及微博數(shù)據(jù)中相互關(guān)注的用戶更可能存在真實(shí)的社交關(guān)系這一特點(diǎn)，我們從數(shù)據(jù)集中隨機(jī)選擇10 000個(gè)用戶，根據(jù)他們之間的相互關(guān)注關(guān)系構(gòu)成的網(wǎng)絡(luò)作為實(shí)驗(yàn)數(shù)據(jù)。②使用文獻(xiàn)[20]中的軟件對(duì)實(shí)驗(yàn)數(shù)據(jù)執(zhí)行fastGN算法，挖掘出了約100個(gè)社交社團(tuán)，結(jié)合社交網(wǎng)絡(luò)的實(shí)際情況，按照社團(tuán)中用戶的數(shù)量分成3種不同規(guī)模的社團(tuán)，每種社團(tuán)中的用戶數(shù)量分別為0-50個(gè)、50-100個(gè)以及100-200個(gè)。③對(duì)這3種規(guī)模的社團(tuán)，隨機(jī)選擇每種30個(gè)分別組成3組實(shí)驗(yàn)社團(tuán)，記作dataset0，dataset1和dataset2。

另外，由于用戶標(biāo)簽數(shù)據(jù)稀疏，在計(jì)算社團(tuán)的屬性特征向量時(shí)，為達(dá)到更好效果，我們用社團(tuán)中所有用戶關(guān)注的認(rèn)證用戶(大V用戶)的標(biāo)簽作為此社團(tuán)的標(biāo)簽集，平均每個(gè)認(rèn)證用戶有5個(gè)標(biāo)簽。

3.2評(píng)價(jià)指標(biāo)

為驗(yàn)證本文算法準(zhǔn)確性，將數(shù)據(jù)集中已存在的關(guān)注數(shù)據(jù)根據(jù)關(guān)注時(shí)刻分為訓(xùn)練集(timestamp=1)與測(cè)試集(timestamp>1)兩部分。

本文提出的是一種相似社團(tuán)間的好友推薦方法，將計(jì)算用戶間相似度擴(kuò)展為計(jì)算社團(tuán)間相似度，生成的好友推薦集也不再是單個(gè)用戶而是社團(tuán)中的具有同樣角色層次的一類用戶。因此，傳統(tǒng)的用戶推薦算法的2種經(jīng)典評(píng)價(jià)指標(biāo)：Precision和AUC，也應(yīng)重新被定義。

新的評(píng)價(jià)指標(biāo)計(jì)算方法：

1)Precision:Precision=m/N

(12)

準(zhǔn)確率為推薦成功數(shù)m與推薦總數(shù)N的比值，在本文實(shí)驗(yàn)中，若目標(biāo)社團(tuán)一類用戶與推薦集的一類用戶形成的任一關(guān)注在測(cè)試集中，都記作該類用戶推薦成功。

2)AUC:AUC=(n1+0.5*n2)/n

(13)

AUC從整體上衡量預(yù)測(cè)算法的精確度，它表示在測(cè)試集中推薦的得分比一個(gè)隨機(jī)選擇的不成功的推薦得分高的概率。對(duì)每個(gè)目標(biāo)社團(tuán)，每次隨機(jī)選擇一個(gè)與之在測(cè)試集中存在關(guān)注的相似社團(tuán)和不存在關(guān)注的相似社團(tuán)進(jìn)行比較，獨(dú)立比較n次。其中存在n1次關(guān)注的社團(tuán)與目標(biāo)社團(tuán)相似度大于不存在關(guān)注的社團(tuán)與目標(biāo)社團(tuán)相似度，存在n2次兩者相等。

3.3實(shí)驗(yàn)方案

1)社交社團(tuán)。在timestamp=1時(shí)刻對(duì)實(shí)驗(yàn)數(shù)據(jù)執(zhí)行fastGN算法，使用文獻(xiàn)[14]中的軟件將其可視化，得到的部分社交社團(tuán)及具體社團(tuán)示例如圖6所示，圖6b中每個(gè)陰影區(qū)域代表一個(gè)社團(tuán)，圖6a中節(jié)點(diǎn)代表社團(tuán)中的用戶，節(jié)點(diǎn)間的連邊則代表2個(gè)用戶互相關(guān)注，節(jié)點(diǎn)標(biāo)簽為用戶的具體ID。

2)推薦準(zhǔn)確率與社團(tuán)間相似度對(duì)應(yīng)變化關(guān)系。對(duì)傳統(tǒng)的基于用戶相似度的推薦方案，通常在驗(yàn)證其可行性的科學(xué)實(shí)驗(yàn)中，采用驗(yàn)證推薦準(zhǔn)確率是否與用戶節(jié)點(diǎn)間相似度成正相關(guān)這一方式。類似地，可采用檢測(cè)推薦準(zhǔn)確率隨社團(tuán)間相似度變化的趨勢(shì)來(lái)驗(yàn)證本文提出的基于相似社團(tuán)的用戶推薦方案的可行性。

圖6　網(wǎng)絡(luò)中的社團(tuán)及其具體示例Fig.6　Communities in network and specific community example

因此，本文對(duì)3組實(shí)驗(yàn)社團(tuán)中的每個(gè)社團(tuán)都進(jìn)行相同操作：將與它相似度排名top10社團(tuán)中的用戶，按照用戶被劃分的角色層次，分別推薦給該實(shí)驗(yàn)社團(tuán)中相同層次角色的用戶，推薦準(zhǔn)確率與社團(tuán)相似度情況如圖7所示。由圖7可知，對(duì)3組實(shí)驗(yàn)社團(tuán)，推薦準(zhǔn)確率與社團(tuán)間相似度均成正相關(guān)，即為目標(biāo)社團(tuán)中的用戶推薦越高相似度社團(tuán)中的其他用戶時(shí)，越容易形成正確的推薦。

3)差異化推薦方式與非差異化推薦方式的效果對(duì)比。為驗(yàn)證角色層次差異化推薦是否對(duì)推薦效果的影響，本文在3組實(shí)驗(yàn)社團(tuán)中，分別為每個(gè)目標(biāo)社團(tuán)薦相似度排名top30社團(tuán)中的用戶，并對(duì)比如下2種方式的推薦效果：

Case1:只推薦同層次角色的用戶；

Case2:推薦同層次和高一層次角色的用戶。

圖7　推薦準(zhǔn)確率與社團(tuán)間相似度對(duì)應(yīng)變化Fig.7　Corresponding change of recommendation precision and community similarity

圖8-圖10分別顯示了對(duì)3組實(shí)驗(yàn)社團(tuán)，case2的推薦準(zhǔn)確率均略高于case1。

圖8　dataset0兩種推薦方式效果對(duì)比Fig.8　Performance comparision of two recommendation cases in dataset0

圖9　dataset1兩種推薦方式效果對(duì)比Fig.9　Performance comparison of two recommendation cases in dataset1

圖10　dataset2兩種推薦方式效果對(duì)比Fig.10　Performance comparison of two recommendation cases in dataset2

結(jié)果表明，差異化推薦能夠提升推薦效果，第2種方式準(zhǔn)確率只是略高于第1種則恰好證明多數(shù)的關(guān)注關(guān)系都在同層次用戶之間建立的，但是與高一層次用戶也可能形成推薦。

4)推薦的效果與社團(tuán)規(guī)模對(duì)應(yīng)變化。由于本文所述的推薦方案是在相似社團(tuán)直接進(jìn)行的，為研究社團(tuán)規(guī)模是否對(duì)推薦效果產(chǎn)生影響，并驗(yàn)證推薦效果最優(yōu)的社團(tuán)規(guī)模，本文在3組實(shí)驗(yàn)社團(tuán)中任意選擇兩組分別作為目標(biāo)社團(tuán)集與相似社團(tuán)集，再將相似社團(tuán)集中所有社團(tuán)采用上述case2方式推薦給每個(gè)目標(biāo)社團(tuán)，表2和表3為目標(biāo)社團(tuán)集的Precision平均值(記為AvePrecision,)和AUC平均值(記為AveAUC)變化。從表2中可以看出，本方案具有良好的推薦效果，且目標(biāo)社團(tuán)集為dataset1時(shí)效果優(yōu)于其他2組社團(tuán)集。由此可知，本方案最適用于50-100個(gè)用戶規(guī)模的社團(tuán)。

表2　3組實(shí)驗(yàn)社團(tuán)平均準(zhǔn)確率

表3　3組實(shí)驗(yàn)社團(tuán)平均AUC

4結(jié)論

本文在傳統(tǒng)社交網(wǎng)絡(luò)中用戶推薦方案基礎(chǔ)上，提出了一種基于相似社團(tuán)和節(jié)點(diǎn)角色劃分的推薦方案。首先，將傳統(tǒng)的主要在個(gè)體之間進(jìn)行的相似度計(jì)算擴(kuò)展到群體之間進(jìn)行，從社團(tuán)結(jié)構(gòu)和屬性兩方面，提出了社團(tuán)相似度的計(jì)算方法；其次，假設(shè)在網(wǎng)絡(luò)中擁有相似結(jié)構(gòu)的用戶節(jié)點(diǎn)具有相似的社會(huì)影響力，從用戶節(jié)點(diǎn)所在的社團(tuán)內(nèi)部和外部2個(gè)維度度量節(jié)點(diǎn)間緊密度，得到節(jié)點(diǎn)的影響力二維坐標(biāo)，由此將它們分類，劃分成不同角色，實(shí)現(xiàn)了用戶推薦的差異化。最后利用新浪微博真實(shí)社交數(shù)據(jù)驗(yàn)證了該方案的推薦準(zhǔn)確率與社團(tuán)間相似度成正相關(guān)變化，角色層次差異化推薦可以提升推薦效果，實(shí)驗(yàn)表明，該方案適用于存在社團(tuán)現(xiàn)象的社交網(wǎng)絡(luò)層次化用戶推薦，并具有良好的推薦效果。

參考文獻(xiàn)：

[1]FRASER M,DUTTA S.Throwing sheep in the boardroom:How online social networking will transform your life,work and world[M].USA：John Wiley & Sons,2010.

[2]TANG Jiliang, HU Xia, LIU Huan. Social recommendation: a review[J]. Social Network Analysis and Mining, 2013, 3(4): 1113-1133.

[3]PAREEK J, JHAVERI M, KAPASI M A, et al. Recommendation System Using Social Networking[J]. International Journal of Computer Science, Engineering & Information Technology, 2012, 2(5): 45-54.

[4]LU Linyuan,ZHOU Tao.Link prediction in complex networks:A survey[J].Physica A,2011(390):1150-1170.

[5]DONG Yuxiao, TANG J, et al. Link prediction and recommendation across heterogeneous social networks[C]//Data Mining (ICDM), 2012 IEEE 12th International Conference on. [s.l.]:IEEE, 2012: 181-190.

[6]JACCARD P.Etude comparative de la distribution florale dans une portion des Alpes et du Jura[J].Bulletin de la Societe Vaudoise des Sciences Naturelles,1901,37(142):547-579.

[7]SALTON G, MCGILL M J. Introduction to modern information retrieval[M]. Auckland: MuGraw-Hill, 1983.

[8]ADAMIC L A, ADAR E. Friends and neighbors on the web[J]. Social Networks, 2003, 25(3): 211-230.

[9]LEICHT E A,HOLME P,NEWMAN M E J.Vertex similarity in networks[J].Phys Rev E,2006(73):026120.

[10] JEH G, WIDOM J. SimRank: A measure of structural context similarity[C]// Proceedings of the ACM SIGKDD 2002. New York: ACM Press, 2002: 538-543.

[11] QIAO Shaojie,LI Tianrui,LI Hong,et al.SimRank:A Page Rank approach based on similarity measure[C]//Intelligent Systems and Knowledge Engineering(ISKE),2010 International Conference on.Hangzhou:IEEE,2010:390-395.

[12] BACKSTROM L, LESKOVEC J. Supervised random walks: predicting and recommending links in social networks[C]//Proceedings of the fourth ACM international conference on Web search and data mining. [s.l.]:ACM, 2011: 635-644.

[13] BRIN S, PAGE L. The anatomy of a large-scale hypertextual Web search engine[J]. Comput Netw & ISDN Syst, 1998, 30(1-7): 107-117.

[14] GUIMERA R, SALES-PARDO M，AMARAL L A N. Classes of complex networks defined by role-to-role connectivity profiles[J]. Nature physics, 2007(3)：63-69.

[15] SCRIPPS J, TAN P N，EAFAHANIAN A H. Node roles and community structure in networks[C]// Joint 9th WEBKDD and 1st SNA-KDD Workshop. [s.l.]:ACM, 2007:26-35.

[16] BACKSTORM L, KUMAR R, MARLOW C, et al. Preferential bahavior in online groups[C]//Proceedings of the ACM Web Search and Data Mining(WSDM). California: ACM, 2008:117-128.

[17] MENASCE D, ALMEIDA V, FONSECA R. A methodology for workload characterization of e-commerce sites[C]//Proceedings of ACM Conference on Electronic Commerce. Denver: ACM, 1999: 119-128.

[18] ZHU Tian, WANG Bai, WU Bin. Social network users clustering based on multivariate time series of emotional behavior[J]. The Journal of China Universities of Posts and Telecommunications, 2014, 21(2): 21-31.

[19] ZHANG Jing, LIU Biao, TANG Jie, et al. Social influence locality for modeling retweeting behaviors[C]//Proceedings of the Twenty-Third international joint conference on Artificial Intelligence. [s.l.]:AAAI Press, 2013: 2761-2767.

[20] QI Ye, WU Bin, SUO Lijun, et al. Telecomvis: Exploring temporal communities in telecom networks[M]//Machine Learning and Knowledge Discovery in Databases. Berlin Heidelberg：Springer, 2009: 755-758.

DOI：10.3979/j.issn.1673-825X.2016.04.013

基金項(xiàng)目：國(guó)家自然科學(xué)基金(61272400)；重慶市青年人才項(xiàng)目(cstc2013kjrcqnrc40004)；教育部-中國(guó)移動(dòng)研究基金(MCM20130351)；重慶市教委科學(xué)計(jì)劃項(xiàng)目(KJ1500425)；重慶郵電大學(xué)文峰基金(WF201403)

Foundation Items：The National Science Foundation of China(61272400); The Chongqing Youth Innovative Talent Project(cstc2013kjrcqnrc40004); The Ministry of Education of China and China Mobile Research Fund(MCM20130351); The Science Project of Chongqing Municipal Education Commission(KJ1500425); The WenFeng Foundation of CQUPT(WF201403).

收稿日期：2015-12-29

修訂日期：2016-05-06通訊作者：鐘曉宇zxy8712@163.com

中圖分類號(hào)：TP391

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1673-825X(2016)04-0525-08

作者簡(jiǎn)介：

鐘曉宇(1991-)，女，四川樂(lè)山人，碩士。主要研究方向?yàn)閿?shù)據(jù)挖掘，社交網(wǎng)絡(luò)推薦。E-mail:zxy8712@163.com。

劉宴兵(1971-)，男，四川遂寧人，教授，博士，博士生導(dǎo)師，主要研究方向?yàn)闊o(wú)線網(wǎng)絡(luò)管控和網(wǎng)絡(luò)信息安全。E-mail:liuyb@cqupt.edu.cn。

肖云鵬(1979-)，男，安徽人，副教授,博士，主要研究方向?yàn)榇髷?shù)據(jù)，移動(dòng)互聯(lián)網(wǎng)，信息安全。E-mail:xiaoyp@cqupt.edu.cn。

(編輯：魏琴芳)

A user recommendation scheme based on similar community and node role division in social network

ZHONG Xiaoyu，LIU Yanbing，XIAO Yunpeng

(Chongqing Engineering Laboratory of Network and Information Security, Chongqing University of Posts and Telecommunications,Chongqing 400065, P. R. China)

Abstract:In view of current research on user recommendation mainly considering similarity of node pair and ignoring role level difference of users, we introduce a new way based on similar community and node role division. At first, relying on the similarity of node pair, we put forward a method to calculate the similarity of community pairs from two perspectives: community structure and attributes of users. Secondly, according to the measurement to external and internal tightness of every node in community, we analyze the users’ social influence and divide them into different roles in order to recommend friends discriminatively. Finally, we select Sina Weibo data to verify our method. Experiment results show that the scheme performs well and is suitable for user recommendation where there are communities in the social network and users can be divided into roles of different levels.

Keywords：similar community；node role；user recommendation；social network