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

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

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

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

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

本文的主要貢獻包括3點：

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

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

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

1 相關工作

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

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

(1)

(2)

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

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

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

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

2 LBSN的定義與模型表示

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

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

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

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

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

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

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

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

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

(3)

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

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

(4)

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

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

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

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

(5)

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

為了進一步考慮多維關系特征的影響，我們在式(5)的基礎上提出一種新的融合社交關系與興趣點特征的矩陣分解模型，整體目標函數(shù)為

(6)

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

(7)

(8)

(9)

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

(10)

(11)

(12)

4 實驗與結(jié)果分析

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

4.1 實驗數(shù)據(jù)集與對比方法

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

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

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

為了評價各方法在推薦性能上的差別，我們選取4種代表性的方法進行實驗對比：

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

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

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

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

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

4.2 評價指標

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

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

(13)

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

4.3 實驗結(jié)果比較

1) POI推薦效果對比

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

Fig. 2 Precision comparison of POI recommendation圖2 POI推薦的準確率對比

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

2) 朋友推薦效果對比

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

Fig. 4 Precision comparison of friend recommendation圖4 朋友推薦的準確率對比

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

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

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

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

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

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

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

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

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

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

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

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

5) 權重因子α與β的影響分析

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

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

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

5 總 結(jié)

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