龔衛(wèi)華 金 蓉 裴小兵 梅建萍

1(浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 杭州 310023) 2(浙江理工大學(xué)信息學(xué)院 杭州 310018) 3(華中科技大學(xué)軟件學(xué)院 武漢 430074)

近年來，隨著各種移動(dòng)社交應(yīng)用與位置服務(wù)的緊密融合，催生了一種新的異質(zhì)信息網(wǎng)絡(luò)——基于位置的社交網(wǎng)絡(luò)(location based social network, LBSN).LBSN通過用戶在位置上的簽到功能把線上虛擬社會(huì)與線下物理世界關(guān)聯(lián)在一起.舉例說明，F(xiàn)ourSquare，F(xiàn)acebookPlaces，Yelp等不僅具備傳統(tǒng)社交網(wǎng)絡(luò)的社交功能，還能衍生多種與位置相關(guān)的服務(wù)，比如位置共享、興趣點(diǎn)(point of interests，POIs)推薦、朋友或近鄰?fù)扑]等，從目前趨勢(shì)來看，面向LBSN的推薦技術(shù)已成為推薦系統(tǒng)領(lǐng)域最活躍的研究分支之一.

眾所周知，數(shù)據(jù)稀疏性一直是影響傳統(tǒng)推薦質(zhì)量的關(guān)鍵難題之一，LBSN中的興趣點(diǎn)推薦和朋友推薦在此面臨著更大的挑戰(zhàn).一方面是由于LBSN中的用戶-位置簽到矩陣是極端稀疏的，在LBSN中通常包含有數(shù)百萬(wàn)的興趣點(diǎn)，用戶日常活動(dòng)具有空間局部性，一些熱點(diǎn)位置如景點(diǎn)、餐館等地方容易受到大量用戶的關(guān)注，而對(duì)于每個(gè)用戶所能訪問的興趣點(diǎn)數(shù)量又十分有限.另一方面，LBSN中的用戶社交關(guān)系也是高度稀疏的，由用戶社交關(guān)系形成的社交網(wǎng)絡(luò)一般都具有小世界現(xiàn)象和無標(biāo)度特性，這些規(guī)律表明極少量的用戶擁有較多的關(guān)系連接，而大量的用戶僅具有少量的關(guān)系連接.大量研究發(fā)現(xiàn),深入理解并掌握LBSN中的社區(qū)結(jié)構(gòu)是有效緩解數(shù)據(jù)稀疏性的新途徑，由于現(xiàn)實(shí)世界的許多網(wǎng)絡(luò)都普遍存在著社區(qū)結(jié)構(gòu)特征，該結(jié)構(gòu)所潛在的信息傳播能力、影響力等特性對(duì)于改善推薦性能具有重要意義，比如同一社區(qū)內(nèi)有社交關(guān)聯(lián)的用戶往往會(huì)表現(xiàn)出相似的興趣愛好和簽到行為特征，又比如地理位置相近、關(guān)注興趣點(diǎn)相同的用戶比較容易聚集成社區(qū)群體，并且同一社區(qū)內(nèi)的用戶會(huì)對(duì)其他用戶的選擇產(chǎn)生一定的影響等.

目前，在傳統(tǒng)社交網(wǎng)絡(luò)領(lǐng)域雖然已有許多社區(qū)發(fā)現(xiàn)成果，但對(duì)其拓展的異質(zhì)網(wǎng)絡(luò)結(jié)構(gòu)如LBSN中的復(fù)雜社區(qū)研究卻非常匱乏.總的來說，現(xiàn)有研究大多將社交網(wǎng)絡(luò)從圖聚類或分割角度提出一些以節(jié)點(diǎn)為中心或邊為中心的社區(qū)發(fā)現(xiàn)方法，由此得到的社區(qū)結(jié)構(gòu)大致有2類：非重疊的社區(qū)與重疊的社區(qū).非重疊的社區(qū)認(rèn)為每個(gè)節(jié)點(diǎn)或用戶只能屬于一個(gè)社區(qū)，社區(qū)之間沒有重疊.而在重疊社區(qū)中，用戶可以隸屬于多個(gè)社區(qū)，并且可以與多個(gè)社區(qū)內(nèi)的用戶關(guān)系都十分緊密.相比之下，重疊社區(qū)能夠更真實(shí)地反映用戶在現(xiàn)實(shí)網(wǎng)絡(luò)中用戶群體興趣特征與行為規(guī)律，從而使得這種結(jié)構(gòu)具有更廣、更準(zhǔn)確的推薦范圍和能力.現(xiàn)階段主流的重疊社區(qū)發(fā)現(xiàn)方法有基于團(tuán)滲透的方法[1-2]、基于鏈接劃分的方法[3-4]、基于標(biāo)簽傳播的方法[5-7]、基于局部擴(kuò)展與優(yōu)化的算法[8-11]等.然而，這些研究都存在一些局限性：一是無法準(zhǔn)確表達(dá)社區(qū)重疊部分的模糊性；二是這些方法都是針對(duì)同構(gòu)的網(wǎng)絡(luò)結(jié)構(gòu)而言，而無法適用于LBSN這種包含多模實(shí)體及多維關(guān)系的異質(zhì)網(wǎng)絡(luò).為此，本文的研究動(dòng)機(jī)主要表現(xiàn)在：一方面是針對(duì)社區(qū)重疊邊界的不確定性問題，我們采用基于非負(fù)矩陣分解的模糊聚類方法更加準(zhǔn)確地刻畫重疊社區(qū)結(jié)構(gòu)特征；另一方面，由于LBSN比傳統(tǒng)社交網(wǎng)絡(luò)不僅僅是增加了位置維度，還包含了多種異質(zhì)關(guān)系，因而亟待提出一種新的融合用戶與位置實(shí)體及其多維關(guān)系的社區(qū)發(fā)現(xiàn)方法.

本文的主要貢獻(xiàn)包括3點(diǎn)：

1) 提出了基于非負(fù)矩陣分解的聯(lián)合聚類方法獲得LBSN中緊密關(guān)聯(lián)的用戶模糊社區(qū)與興趣點(diǎn)聚簇結(jié)構(gòu)，有效緩解了朋友推薦和POI推薦中的數(shù)據(jù)稀疏問題.

2) 融合了LBSN中用戶與位置這2類實(shí)體及其多維異質(zhì)關(guān)系，主要包括用戶間的社交關(guān)系、用戶-位置簽到關(guān)系、地理位置相似關(guān)系(即考慮了距離和標(biāo)簽因素的興趣點(diǎn)特征).

3) 在Gowalla和Foursquare(NYC)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，本文提出的MRNMF(multi-relational nonnegative matrix factorization)方法同時(shí)在朋友與興趣點(diǎn)這雙重推薦上比其他傳統(tǒng)方法具有更優(yōu)越的推薦性能.

1 相關(guān)工作

重疊社區(qū)已被發(fā)現(xiàn)廣泛存在于各種社交網(wǎng)絡(luò)中，現(xiàn)有針對(duì)重疊社區(qū)結(jié)構(gòu)的研究從采用的模型或方法上主要分為模糊的與非模糊的社區(qū)發(fā)現(xiàn)算法，其中非模糊的重疊社區(qū)發(fā)現(xiàn)研究一直是大多數(shù)國(guó)內(nèi)外學(xué)者關(guān)注的熱點(diǎn)方向.如引言中基于團(tuán)滲透方法的主要思想是將社區(qū)視為由一些團(tuán)(全連通子圖)構(gòu)成的集合，這些團(tuán)之間通過共享節(jié)點(diǎn)而緊密連接，代表性算法如CPM[2].基于鏈接劃分方法是將鏈接而不是節(jié)點(diǎn)作為考慮對(duì)象，通過設(shè)計(jì)適當(dāng)?shù)膭澐植呗詠慝@取鏈接社區(qū)結(jié)構(gòu)，典型的算法有DBLC[3]和DBLINK[4].基于標(biāo)簽傳播方法是一種半監(jiān)督學(xué)習(xí)方法，主要是利用已標(biāo)記節(jié)點(diǎn)的標(biāo)簽信息，通過已標(biāo)記節(jié)點(diǎn)和未標(biāo)記節(jié)點(diǎn)的相似度連邊權(quán)重預(yù)測(cè)未被標(biāo)記節(jié)點(diǎn)的標(biāo)簽信息，最常見的算法如LPA[5]，SPLA[6]，LPPB[7]等.基于局部擴(kuò)展與優(yōu)化的算法是利用網(wǎng)絡(luò)的局部特性不斷挖掘網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，例如LFM[10]，OSLOM[11]等都是該方法的典型代表.不難發(fā)現(xiàn)，這些方法的共同缺陷是無法恰當(dāng)表達(dá)重疊節(jié)點(diǎn)在多個(gè)社區(qū)中的隸屬?gòu)?qiáng)度，同時(shí)也沒有考慮多維關(guān)系的融合而得到比較單一的社區(qū)結(jié)構(gòu).

另一種以模糊聚類理論為代表的重疊社區(qū)發(fā)現(xiàn)研究成果已表明，模糊重疊更符合真實(shí)社交網(wǎng)絡(luò)的實(shí)際情況，該類方法的經(jīng)典算法如FCM(fuzzy c-means)[12]最早應(yīng)用于社交網(wǎng)絡(luò)的模糊重疊劃分，通過將重疊社區(qū)檢測(cè)建模成目標(biāo)函數(shù)的最小化問題：

(1)

(2)

易知，模糊劃分的要點(diǎn)是允許節(jié)點(diǎn)以不同的隸屬度值歸屬于多個(gè)社區(qū)，然而，由于FCM在聚類中僅考慮了節(jié)點(diǎn)距離特征因而丟失了網(wǎng)絡(luò)圖結(jié)構(gòu)信息.此后，有一些文獻(xiàn)[13-14]提出了一種結(jié)合模塊度函數(shù)的FCM聚類方法發(fā)現(xiàn)網(wǎng)絡(luò)中的重疊社區(qū)，但其缺點(diǎn)是社區(qū)結(jié)果依賴于隨機(jī)游走值和模糊因子.

此外，NMF方法也特別適合發(fā)現(xiàn)重疊的社區(qū)結(jié)構(gòu)，Zhang等人[22]提出基于對(duì)稱矩陣分解的SBMF模型發(fā)現(xiàn)重疊社區(qū)結(jié)構(gòu)，并通過劃分密度方法自動(dòng)確定合適的社區(qū)個(gè)數(shù)，該模型不僅能夠明確劃分網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，還能提供節(jié)點(diǎn)與社區(qū)的隸屬?gòu)?qiáng)度.文獻(xiàn)[23-24]都提出了基于貝葉斯的NMF方法發(fā)現(xiàn)網(wǎng)絡(luò)中的重疊社區(qū)，采用軟劃分方式有效刻畫節(jié)點(diǎn)對(duì)多個(gè)社區(qū)的隸屬程度.還有文獻(xiàn)[25]提出了基于偏好的非負(fù)矩陣分解模型PNMF，在重疊社區(qū)發(fā)現(xiàn)中融入了鏈接偏好信息.

綜上可知，現(xiàn)有大多數(shù)傳統(tǒng)的NMF方法基本上都使得被分解的2個(gè)低維矩陣具有共同的維度空間，這種矩陣分解方式僅適于發(fā)現(xiàn)同構(gòu)網(wǎng)絡(luò)中的單一社區(qū)結(jié)構(gòu)，也缺乏有效融合已知先驗(yàn)知識(shí)與多維關(guān)系或特征的方法.因此，另一些研究提出了改進(jìn)的非負(fù)矩陣分解方法實(shí)現(xiàn)聯(lián)合聚類，最早由Ding等人[26]提出了正交非負(fù)矩陣三分解的聯(lián)合聚類方法，其表示形式如X≈FBZT，其中F表示行聚類的指示矩陣，而Z表示列聚類的指示矩陣.還有文獻(xiàn)[27]也提出有限的非負(fù)矩陣三分解方法BNMTF發(fā)現(xiàn)重疊社區(qū)，其表示形式如X≈UBUT，其中U表示節(jié)點(diǎn)對(duì)社區(qū)的隸屬度矩陣，而B表示社區(qū)間的交互矩陣.這些基于NMF的聯(lián)合聚類方法雖具有比較理想的異質(zhì)關(guān)系數(shù)據(jù)處理能力，但遺憾的是，迄今針對(duì)多模異質(zhì)網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)研究仍十分缺乏，特別是對(duì)LBSN中的復(fù)雜社區(qū)結(jié)構(gòu)沒有深入的認(rèn)識(shí)與理解.

受上述工作啟發(fā)，本文將針對(duì)LBSN這種新型的異質(zhì)網(wǎng)絡(luò)提出一種基于NMF的融合多維異質(zhì)關(guān)系的聯(lián)合聚類模型，不僅能獲得準(zhǔn)確的用戶模糊社區(qū)，同時(shí)還能得到關(guān)聯(lián)的興趣點(diǎn)聚簇，該緊密結(jié)構(gòu)有助于提高朋友推薦與興趣點(diǎn)推薦的質(zhì)量.

2 LBSN的定義與模型表示

LBSN是一種由用戶與地理位置這2種實(shí)體及其多維關(guān)系復(fù)合而成的異質(zhì)網(wǎng)絡(luò)，如圖1所示.在圖1中LBSN分別由用戶層和地理位置層組成，上層為傳統(tǒng)的用戶社交關(guān)系網(wǎng)絡(luò)，下層為地理位置標(biāo)簽網(wǎng)絡(luò)，上下層之間通過用戶-位置簽到行為建立起異質(zhì)實(shí)體間的聯(lián)系.

Fig. 1 Structure of composite relational networks in LBSN圖1 LBSN中的復(fù)合關(guān)系網(wǎng)絡(luò)結(jié)構(gòu)

為了描述LBSN的形式化模型，首先給出相關(guān)的定義：

定義1.用戶社交關(guān)系網(wǎng)絡(luò).在同一用戶層的用戶間社交關(guān)系形成的網(wǎng)絡(luò)可表示成一個(gè)無向圖結(jié)構(gòu)，記為S=(Y,E)，其中，Y表示用戶集，E表示用戶社交關(guān)系的邊集，即E={(yi,yj)|yi,yj∈Y}.

定義2.用戶-位置簽到網(wǎng)絡(luò).用戶在地理位置上的簽到行為形成的關(guān)系網(wǎng)絡(luò)可表示成二部圖結(jié)構(gòu)，記為P=(Y,D,T)，其中，Y表示用戶集，D表示地理位置集，T表示用戶與位置間的簽到關(guān)系集，即T={(yi,dj)|yi∈Y,dj∈D,Y∩D=?}.

定義3.地理位置標(biāo)簽網(wǎng)絡(luò).地理位置標(biāo)簽網(wǎng)絡(luò)可抽象成一個(gè)無向圖，記為G=(D,C)，其中，D為地理位置集合，C表示地理位置間的關(guān)系邊集，即C={(di,dj)|di,dj∈D}.

在此基礎(chǔ)上，本文進(jìn)一步給出融合定義1～3的3種關(guān)系的異質(zhì)復(fù)合網(wǎng)絡(luò)模型即基于位置的社交網(wǎng)絡(luò)的形式化定義.

定義4.基于位置的社交網(wǎng)絡(luò).是一種由用戶與地理位置實(shí)體及其多維關(guān)系構(gòu)成的異質(zhì)網(wǎng)絡(luò)圖，記為WLBSN=S×P×G=(Y,E)×(Y,D,T)×(D,C)=(Y,D,E,T,C)，其中包含了2種實(shí)體：用戶集Y與地理位置集D，與對(duì)應(yīng)的3種維度關(guān)系：用戶間的社交關(guān)系E、用戶與位置的簽到關(guān)系T、位置間的相似關(guān)系C.

在LBSN的用戶層中，對(duì)于給定的用戶集合Y={y1,y2,…,yn}，用戶之間的相似性可通過檢測(cè)社交關(guān)系網(wǎng)絡(luò)S中是否具有共同朋友進(jìn)行評(píng)估，于是我們采用Sorgenfrei系數(shù)來度量用戶社交相似性：

(3)

其中，Ni與Nj分別表示用戶yi與用戶yj的鄰居集合.由此可見，用戶社交關(guān)系形成的相似性矩陣可表示為V=(vij)n×n.

對(duì)于LBSN的地理位置層，地理空間上分布的位置集合有D={d1,d2,…,dm}，各位置間的相似性不僅直接與其空間距離特性相關(guān)，還與位置上的語(yǔ)義標(biāo)簽屬性密切關(guān)聯(lián)，我們綜合考慮這2種因素給出地理位置相似性的定義：

(4)

其中，f(di,dj)表示位置di與dj間的歐氏距離，s(di,dj)∈[0,1]表示位置di與dj的標(biāo)簽相似性.因此，由地理位置相似關(guān)系構(gòu)成的位置特征矩陣可記為O=(oij)m×m.

3 融合多維異質(zhì)關(guān)系的聯(lián)合聚類模型

在第2節(jié)所述的LBSN模型基礎(chǔ)上，本文提出一種基于非負(fù)矩陣分解的用戶模糊社區(qū)發(fā)現(xiàn)與興趣點(diǎn)聚簇方法，采用三因子矩陣分解的表示形式如R≈UHL，將用戶-位置關(guān)系矩陣R的行和列同時(shí)聚類分解為3個(gè)矩陣U，H，L.其中，U與L分別為用戶端和位置端的聚類指示矩陣，H為關(guān)聯(lián)矩陣.該方法的目標(biāo)是在把原始矩陣映射到低維特征空間過程中既考慮了用戶-位置簽到關(guān)系，又融合了傳統(tǒng)的用戶社交關(guān)系與地理位置的興趣點(diǎn)特征.

為了使矩陣分解的誤差最小化，我們構(gòu)造的目標(biāo)函數(shù)為

(5)

在式(5)表示的非負(fù)矩陣分解模型中，用戶對(duì)位置的興趣偏好特征由用戶-位置簽到關(guān)系矩陣R表示，該矩陣從行聚類和列聚類角度被同時(shí)分解成關(guān)于用戶端的隸屬矩陣U與地理位置端的隸屬矩陣L，從而以更直觀的形式表明了用戶興趣模型不僅會(huì)受到用戶重疊社區(qū)結(jié)構(gòu)的影響，還與位置聚簇特征密切相關(guān).本質(zhì)上看，用戶社區(qū)結(jié)構(gòu)源于用戶間內(nèi)在的社交關(guān)系，而位置聚簇結(jié)構(gòu)則依賴于興趣點(diǎn)特征的相似性.

為了進(jìn)一步考慮多維關(guān)系特征的影響，我們?cè)谑?5)的基礎(chǔ)上提出一種新的融合社交關(guān)系與興趣點(diǎn)特征的矩陣分解模型，整體目標(biāo)函數(shù)為

(6)

為了求解目標(biāo)函數(shù)的局部最優(yōu)值，采用隨機(jī)梯度下降法(SGD)分別對(duì)U，H，L求導(dǎo)可得：

(7)

(8)

(9)

其中，式(7)與式(9)中的特征矩陣V與O分別由式(3)與式(4)計(jì)算而得，然后再根據(jù)式(10)～(12)迭代更新矩陣U，H，L的值，符號(hào)τ表示梯度下降迭代次數(shù)，μ>0表示學(xué)習(xí)速率.最終目標(biāo)是使得所求矩陣U，H，L沿梯度下降方向不斷迭代更新直至收斂或設(shè)定的閾值為止.

(10)

(11)

(12)

4 實(shí)驗(yàn)與結(jié)果分析

本實(shí)驗(yàn)的運(yùn)行環(huán)境為Intel Core i7-4500U處理器、16 GB內(nèi)存、Windows 7操作系統(tǒng)，算法采用Python2.7編程實(shí)現(xiàn).下面分別給出了實(shí)驗(yàn)數(shù)據(jù)集描述、評(píng)價(jià)指標(biāo)與實(shí)驗(yàn)結(jié)果分析.

4.1 實(shí)驗(yàn)數(shù)據(jù)集與對(duì)比方法

我們選取2種真實(shí)的數(shù)據(jù)集Foursquare (NYC)和Gowalla，驗(yàn)證本文所提方法的聯(lián)合聚類效果與推薦性能.實(shí)驗(yàn)前先過濾數(shù)據(jù)集以移除一些異常數(shù)據(jù)，對(duì)于Foursquare(NYC)數(shù)據(jù)集，我們篩選出超過2人簽到的地理位置，以及評(píng)論數(shù)多于5條的用戶及其所擁有的社交關(guān)系.在Gowalla數(shù)據(jù)集中，我們篩選出簽到數(shù)超過50的地理位置，以及社交關(guān)系超過50條且簽到次數(shù)也超過50的用戶.預(yù)處理完成后，各數(shù)據(jù)集中用戶數(shù)、位置數(shù)以及社交關(guān)系和簽到關(guān)系等基本信息如表1所示:

Table 1 Basic Information of Two LBSN Datasets表1 2種LBSN數(shù)據(jù)集的基本信息

從表1中可以看出，數(shù)據(jù)集Foursquare (NYC)與Gowalla上的用戶簽到密度都非常低，反映了LBSN中的興趣點(diǎn)有較大的稀疏性，而在用戶社交關(guān)系上，這2個(gè)數(shù)據(jù)集的社交用戶平均度分別約為9.2和14.1，表明社交用戶間的交互關(guān)系比較密切.

為了評(píng)價(jià)各方法在推薦性能上的差別，我們選取4種代表性的方法進(jìn)行實(shí)驗(yàn)對(duì)比：

1) FCM方法.FCM是一種經(jīng)典的基于模糊聚類的方法，文獻(xiàn)[12]使用該方法發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中重疊的社區(qū)結(jié)構(gòu).本實(shí)驗(yàn)中FCM方法僅從用戶社交關(guān)系維度檢測(cè)社交網(wǎng)絡(luò)中的重疊社區(qū)結(jié)構(gòu)，式(1)中的系數(shù)m=2.

2) NMF方法.NMF是由Lee等人[15]提出的一種非負(fù)矩陣分解方法，其形如X≈WH，該方法可用來發(fā)現(xiàn)社交網(wǎng)絡(luò)中的重疊社區(qū)結(jié)構(gòu).本文將用戶社交關(guān)系矩陣分解為2個(gè)對(duì)稱的用戶社區(qū)隸屬矩陣，即為X≈HHT.

3) NMTF方法.Ding等人[26]提出了非負(fù)矩陣三因子分解的聯(lián)合聚類方法NMTF，其表示形式如X≈FBZT，該方法在LBSN的用戶重疊社區(qū)發(fā)現(xiàn)過程中僅考慮結(jié)合了用戶社交關(guān)系與簽到關(guān)系這2種信息.

4) MRNMF方法.MRNMF是本文提出的社區(qū)聯(lián)合聚類方法，該方法融合了LBSN異質(zhì)網(wǎng)中的用戶社交關(guān)系、用戶-位置簽到關(guān)系以及興趣點(diǎn)特征等多維度因素，MRNMF方法既能發(fā)現(xiàn)用戶模糊社區(qū)，又能獲得興趣點(diǎn)聚簇.

上述4種對(duì)比方法中，F(xiàn)CM方法代表了典型的模糊聚類社區(qū)發(fā)現(xiàn)方法；NMF方法是傳統(tǒng)的基于對(duì)稱非負(fù)矩陣分解方法發(fā)現(xiàn)重疊社區(qū)結(jié)構(gòu)；而NMTF和MRNMF方法雖都屬于另一種代表性的基于非負(fù)矩陣三因子分解的聯(lián)合聚類方法，但本文的MRNMF方法還通過加入特征項(xiàng)深度融合了多種維度的關(guān)系與特征.

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

實(shí)驗(yàn)將采用50次10-折交叉驗(yàn)證法，把表1中2種LBSN數(shù)據(jù)集上的用戶和地理位置隨機(jī)分為10份，每次選擇其中的80%作為訓(xùn)練集，剩下的20%作為測(cè)試集，將50次評(píng)價(jià)結(jié)果取平均值得到最終的評(píng)估數(shù)據(jù).

本文提出的MRNMF模型既能得到用戶重疊社區(qū)，又能獲得興趣點(diǎn)聚簇.為了評(píng)價(jià)該結(jié)果在朋友與興趣點(diǎn)上的雙重推薦性能，我們采用準(zhǔn)確率Precision@K(P@K)和召回率Recall@K(R@K)這2種廣泛使用的Top-K指標(biāo)進(jìn)行實(shí)驗(yàn)比較.另外，為了度量算法的社區(qū)劃分質(zhì)量，本文還將模塊度作為是一種重要的評(píng)價(jià)指標(biāo)，針對(duì)重疊社區(qū)結(jié)構(gòu)的模塊度Q可定義為

(13)

其中，m表示邊數(shù)，Gij是網(wǎng)絡(luò)鄰接矩陣元素，ki表示節(jié)點(diǎn)i的度，Pic表示節(jié)點(diǎn)i在社區(qū)c中隸屬度系數(shù).式(13)表明，模塊度Q值越大則表示重疊社區(qū)的模塊化程度越高.

4.3 實(shí)驗(yàn)結(jié)果比較

1) POI推薦效果對(duì)比

在POI推薦性能方面，本文比較了4種方法在2種數(shù)據(jù)集上推薦Top-K個(gè)興趣點(diǎn)時(shí)的準(zhǔn)確率與召回率，結(jié)果如圖2與圖3所示，橫軸上的K值表示推薦的Top-K興趣點(diǎn)數(shù)量.由圖2與圖3可知，在Foursquare(NYC)和Gowalla數(shù)據(jù)集上，F(xiàn)CM與NMF方法由于僅對(duì)單一社交關(guān)系聚類而沒有用戶興趣點(diǎn)信息，使其基本不具備POI推薦能力，隨機(jī)推薦實(shí)驗(yàn)中的性能指標(biāo)都低于0.01，因此這2種方法的POI推薦能力可以忽略不計(jì).對(duì)于NMTF與MRNMF方法，當(dāng)設(shè)置相同的位置簇?cái)?shù)為30時(shí)，兩者都隨著K的增加POI推薦的準(zhǔn)確率有所下降，召回率有一定程度的上升.綜合來看，本文的MRNMF方法的POI推薦能力顯著地強(qiáng)于NMTF方法，其原因是MRNMF方法既考慮用戶社交關(guān)系和簽到關(guān)系，又融入了地理位置上的興趣點(diǎn)特征，在2種數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果都表明MRNMF方法聚類的位置簇結(jié)構(gòu)能有效地促進(jìn)POI推薦性能的提高.

Fig. 2 Precision comparison of POI recommendation圖2 POI推薦的準(zhǔn)確率對(duì)比

Fig. 3 Recall comparison of POI recommendation圖3 POI推薦的召回率對(duì)比

2) 朋友推薦效果對(duì)比

在朋友推薦性能上，本文比較了4種方法在用戶層上推薦Top-K個(gè)相似用戶或朋友的準(zhǔn)確率與召回率，結(jié)果如圖4與圖5所示，各方法所設(shè)置的用戶社區(qū)簇參數(shù)在Foursquare(NYC)與Gowalla數(shù)據(jù)集上分別為18與30.從圖4與圖5可以看出，本文的MRNMF方法在Foursquare(NYC)和Gowalla上對(duì)朋友推薦的準(zhǔn)確率、召回率指標(biāo)都普遍優(yōu)于其他3種方法;FCM與NMF方法有比較相近的朋友推薦性能，原因是這2種方法僅能得到比較簡(jiǎn)單的用戶重疊社區(qū)而無法顧及多維關(guān)系的影響.在結(jié)合了多維關(guān)系與特征之后，MRNMF方法比NMTF方法的推薦準(zhǔn)確率提升至少25%以上，同時(shí)在召回率上高出11%～20%.

Fig. 4 Precision comparison of friend recommendation圖4 朋友推薦的準(zhǔn)確率對(duì)比

Fig. 5 Recall comparison of friend recommendation圖5 朋友推薦的召回率對(duì)比

綜合圖2～5可得出，考慮到地理位置簽到密度比用戶社交關(guān)系存在更大的數(shù)據(jù)稀疏性，上述 4種方法都在朋友推薦性能上表現(xiàn)出比POI推薦更好的質(zhì)量；從數(shù)據(jù)集角度看，4種方法在Gowalla上的朋友推薦性能普遍都比Foursquare(NYC)上的效果更好，這與Gowalla數(shù)據(jù)集上的用戶社交關(guān)系較密集有關(guān)，用戶社區(qū)結(jié)構(gòu)特征也更明顯.總的來看，本文提出的MRNMF方法既能發(fā)現(xiàn)用戶重疊社區(qū)，又能獲得興趣點(diǎn)聚簇，這兩者同時(shí)還具有一定的關(guān)聯(lián)性，從而使得該方法在朋友推薦與POI推薦的性能上都整體上優(yōu)于其他方法.

3) 用戶重疊社區(qū)的模塊度比較

為了評(píng)價(jià)用戶重疊社區(qū)結(jié)構(gòu)，本文比較了4種方法分別在Foursquare(NYC)與Gowalla數(shù)據(jù)集上的重疊社區(qū)模塊度Q值，設(shè)定劃分的用戶社區(qū)簇參數(shù)c分別為12，18，24，30，實(shí)驗(yàn)結(jié)果如表2所示:

Table 2 Comparisons of Modularity Q Values of Four Methods Under Different Clusters表2 4種方法在不同社區(qū)簇c下的模塊度Q值對(duì)比

從表2中可以看到，F(xiàn)CM與NMF方法在2種數(shù)據(jù)集上的社區(qū)模塊度值基本相近，表明這2種方法獲得了幾乎相同的社區(qū)特性，由于兩者都僅考慮了單一維度的社交關(guān)系，與NMTF與MRNMF方法相比，重疊社區(qū)結(jié)構(gòu)仍不夠明顯.總體而言，本文的MRNMF方法在不同社區(qū)簇參數(shù)c下都表現(xiàn)出最好的模塊度性能，當(dāng)社區(qū)簇大小分別在Foursquare(NYC)與Gowalla上取18與30時(shí)有最大的模塊度值，其原因是MRNMF方法在矩陣三因子分解中不僅結(jié)合了用戶社交關(guān)系與簽到關(guān)系信息，還加入了興趣點(diǎn)特征，因而能夠獲得最優(yōu)的用戶重疊社區(qū)效果，由此表現(xiàn)出最佳的朋友推薦能力.

4) 社區(qū)簇c與位置簇g參數(shù)的影響分析

下面將考察MRNMF模型中的社區(qū)簇與位置簇大小分別對(duì)朋友推薦與POI推薦的性能影響.對(duì)式(6)進(jìn)行非負(fù)矩陣三因子分解時(shí)涉及到2個(gè)重要參數(shù)是社區(qū)簇c與位置簇g，圖6顯示了社區(qū)簇參數(shù)分別在Foursquare(NYC)和Gowalla數(shù)據(jù)集上對(duì)朋友推薦的準(zhǔn)確率變化情況，而圖7則給出了不同位置簇參數(shù)在這2種數(shù)據(jù)集上對(duì)POI推薦的準(zhǔn)確率結(jié)果.

由圖6可知，朋友推薦準(zhǔn)確率在2種數(shù)據(jù)集上的變化趨勢(shì)基本相同，在不同Top-K值下的朋友推薦準(zhǔn)確率都隨著社區(qū)簇的增大而逐漸升高，當(dāng)用戶社區(qū)簇c在Foursquare(NYC)與Gowalla上分別為18和30時(shí)，推薦準(zhǔn)確率達(dá)到最大值，這說明劃分合適的社區(qū)簇有助于發(fā)現(xiàn)真實(shí)的用戶群體.由于數(shù)據(jù)集Foursquare(NYC)上的用戶數(shù)量少于Gowalla，且社交用戶關(guān)系度要比Gowalla的更稀疏，因此在Foursquare(NYC)數(shù)據(jù)集上的朋友推薦準(zhǔn)確率略低于Gowalla.

從圖7可以看出，POI推薦在不同Top-K值下的準(zhǔn)確率都隨著位置簇參數(shù)g的增大而平緩升高，當(dāng)位置簇?cái)?shù)在Foursquare(NYC)與Gowalla數(shù)據(jù)集上分別取35與30時(shí)有最好的推薦性能，考慮到地理位置具有較大的稀疏性，并且位置相似性度量受到距離與標(biāo)簽屬性因素不平衡的影響，地理位置聚簇的結(jié)構(gòu)特征雖不如用戶社區(qū)簇那樣明顯，但比傳統(tǒng)POI推薦方法的準(zhǔn)確性還是有較大的提高.綜上，MRNMF方法能同時(shí)獲得關(guān)聯(lián)的用戶重疊社區(qū)與位置簇,有助于提高朋友推薦與POI推薦的精度.

Fig. 6 Effect of community cluster parameter c on friend recommendation圖6 社區(qū)簇參數(shù)c對(duì)朋友推薦的影響

Fig. 7 Effect of location cluster parameter g on POI recommendation圖7 位置簇參數(shù)g對(duì)POI推薦的影響

5) 權(quán)重因子α與β的影響分析

在如式(6)的MRNMF方法中，α與β分別代表了考慮用戶社交關(guān)系與興趣點(diǎn)特征的權(quán)重因子，它們?cè)谝欢ǔ潭壬险{(diào)節(jié)著用戶社區(qū)與位置簇的聚類結(jié)果.圖8與圖9分別檢驗(yàn)了不同的α與β對(duì)Top-K值取10時(shí)朋友推薦與POI推薦的準(zhǔn)確率變化情況.在2種數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果顯示，參數(shù)α與β分別對(duì)朋友推薦與POI推薦的準(zhǔn)確率表現(xiàn)出基本相同的變化趨勢(shì)，即都是先升后降的過程，并各自在0.5與0.1時(shí)取得最大值.實(shí)驗(yàn)驗(yàn)證了α與β所控制的社交關(guān)系與興趣點(diǎn)特征比重能夠直接影響到朋友推薦與POI推薦的效果.

Fig. 8 Precision results of friend recommendation influenced by parameter α圖8 參數(shù)α對(duì)朋友推薦的準(zhǔn)確率影響

Fig. 9 Precision results of POI recommendation influenced by parameter β圖9 參數(shù)β對(duì)POI推薦的準(zhǔn)確率影響

5 總 結(jié)

異質(zhì)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)是當(dāng)前非常值得關(guān)注的研究方向，現(xiàn)有研究一直都面臨著如何融合多模實(shí)體及其多維關(guān)系的挑戰(zhàn)性難題.本文針對(duì)LBSN這種新型異質(zhì)網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)問題，提出了一種融合用戶與位置實(shí)體及其多維關(guān)系的社區(qū)發(fā)現(xiàn)方法MRNMF.該方法采用基于非負(fù)矩陣分解的聯(lián)合聚類模型，通過構(gòu)建基于距離度量的損失函數(shù)來評(píng)估矩陣近似分解誤差，并在此基礎(chǔ)上考慮結(jié)合用戶社交關(guān)系、用戶-位置簽到關(guān)系以及興趣點(diǎn)特征等多維度的影響因素，使之融合到統(tǒng)一的表示模型中，然后運(yùn)用隨機(jī)梯度下降法來求解目標(biāo)函數(shù)的局部最優(yōu)值.其最大的優(yōu)勢(shì)和創(chuàng)新點(diǎn)是通過基于NMF的聯(lián)合聚類方法能同時(shí)獲得LBSN中緊密關(guān)聯(lián)的用戶模糊社區(qū)與興趣點(diǎn)聚簇，以有效緩解推薦中的數(shù)據(jù)稀疏問題.最后，在Foursquare(NYC)和Gowalla數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，本文所提的MRNMF方法在準(zhǔn)確率和召回率2個(gè)評(píng)價(jià)指標(biāo)都優(yōu)于其他傳統(tǒng)的社區(qū)發(fā)現(xiàn)方法，在朋友與興趣點(diǎn)這雙重推薦上都具有最優(yōu)的推薦性能.在未來工作中，我們將進(jìn)一步考慮時(shí)間因素挖掘出反映用戶及興趣點(diǎn)遷移的社區(qū)演化結(jié)構(gòu).