一種融合多維信息的移動(dòng)社區(qū)發(fā)現(xiàn)方法

舒 鵬，杜慶偉

(南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,江蘇 南京 211106)

0 引 言

近年來(lái)，隨著移動(dòng)互聯(lián)網(wǎng)的迅速發(fā)展和移動(dòng)設(shè)備的日益普及，已經(jīng)涌現(xiàn)出不同類型的應(yīng)用服務(wù)，例如Foursquare、微博等社交應(yīng)用。移動(dòng)網(wǎng)絡(luò)中充斥著大量的用戶數(shù)據(jù)，包括社交通信數(shù)據(jù)、上網(wǎng)信息和軌跡信息等。利用這些信息挖掘大型網(wǎng)絡(luò)中節(jié)點(diǎn)之間的關(guān)系和社區(qū)結(jié)構(gòu)可以發(fā)現(xiàn)用戶的行為特征和關(guān)聯(lián)，進(jìn)而為實(shí)現(xiàn)信息的共享和熱點(diǎn)推薦等提供智能決策[1]。

社區(qū)發(fā)現(xiàn)即挖掘網(wǎng)絡(luò)中存在的群體結(jié)構(gòu)[2]。目前，針對(duì)社會(huì)化網(wǎng)絡(luò)領(lǐng)域的社區(qū)發(fā)現(xiàn)已有許多成果，主要有基于標(biāo)簽傳播的算法[3]、基于模塊度的算法[4-6]和基于圖分割的算法[7]。然而，這些傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法通常僅考慮單一實(shí)體的連接結(jié)構(gòu)而忽略了用戶間的共同興趣特征，難以保證社區(qū)結(jié)構(gòu)的內(nèi)聚性。在復(fù)雜異質(zhì)的移動(dòng)社區(qū)網(wǎng)絡(luò)中不僅包含用戶、地理位置、主題內(nèi)容等實(shí)體，還包含用戶間的各種偏好關(guān)系，如何高效地對(duì)復(fù)雜異質(zhì)的移動(dòng)社區(qū)網(wǎng)絡(luò)進(jìn)行社區(qū)發(fā)現(xiàn)成為關(guān)鍵問(wèn)題。

本文通過(guò)分析移動(dòng)網(wǎng)絡(luò)使用詳單數(shù)據(jù)(UDR)和移動(dòng)用戶社交數(shù)據(jù)中的用戶間社交關(guān)系、地理位置偏好關(guān)系和主題內(nèi)容偏好關(guān)系這三維信息分別構(gòu)建社交相似網(wǎng)絡(luò)、地理位置相似網(wǎng)絡(luò)和主題相似網(wǎng)絡(luò)，然后利用網(wǎng)絡(luò)融合(Network Fusion， NF)方法融合多維相似關(guān)系構(gòu)建用戶相似網(wǎng)絡(luò)，并運(yùn)用有界非負(fù)矩陣分解(Bounded Nonnegative Matrix Factorization, BNMF)來(lái)確定最優(yōu)的社區(qū)結(jié)構(gòu)劃分結(jié)果。實(shí)驗(yàn)結(jié)果表明，在復(fù)雜異質(zhì)的移動(dòng)社區(qū)網(wǎng)絡(luò)中，本文提出的BNMF-NF方法能夠高效發(fā)現(xiàn)用戶社區(qū)結(jié)構(gòu)。

1 相關(guān)工作

移動(dòng)社區(qū)網(wǎng)絡(luò)中一組內(nèi)部緊密聯(lián)系的用戶形成移動(dòng)社區(qū)，社區(qū)內(nèi)部用戶節(jié)點(diǎn)間的相互作用比社區(qū)和外部用戶節(jié)點(diǎn)的相互作用更強(qiáng)。在移動(dòng)社區(qū)網(wǎng)絡(luò)中進(jìn)行社區(qū)發(fā)現(xiàn)就是識(shí)別一系列節(jié)點(diǎn)的集合，使得移動(dòng)用戶集合內(nèi)部的用戶節(jié)點(diǎn)之間的相互聯(lián)系更加緊密，而集合與集合間用戶節(jié)點(diǎn)相互聯(lián)系更加稀松。目前，社區(qū)發(fā)現(xiàn)研究已有許多成果，大致可分為以下4類：

1)基于模塊度的社區(qū)發(fā)現(xiàn)算法。模塊度是Clauset和Newman[5]提出的評(píng)價(jià)社區(qū)結(jié)構(gòu)的指標(biāo)，定義為每個(gè)社區(qū)內(nèi)邊權(quán)重與其期望之差的和，模塊度越大表明社區(qū)結(jié)構(gòu)越明顯?；谀K度函數(shù)優(yōu)化的Louvain算法[6]是該類算法典型的代表成果。

2)基于標(biāo)簽傳播的社區(qū)發(fā)現(xiàn)算法。Raghavan等人[8]將節(jié)點(diǎn)歸屬社區(qū)抽象為標(biāo)簽，提出了基于標(biāo)簽傳播的社區(qū)發(fā)現(xiàn)算法。

3)基于隨機(jī)游走的社區(qū)發(fā)現(xiàn)算法。Rosvall等人[9]提出了基于隨機(jī)游走的社區(qū)發(fā)現(xiàn)方法，將隨機(jī)游走序列中的每個(gè)節(jié)點(diǎn)進(jìn)行Huffman編碼，同時(shí)對(duì)社區(qū)也進(jìn)行編碼，算法優(yōu)化目標(biāo)為2個(gè)部分編碼的平均描述長(zhǎng)度最小化。

4)基于圖分割的社區(qū)發(fā)現(xiàn)算法。Kernighan和Lin提出了基于圖分割的KL算法[7]。Girvan和Newman聚焦于社區(qū)結(jié)構(gòu)特性提出了另一種基于圖劃分的GN算法[10]。

V≈WH

(1)

2 融合多維信息的社區(qū)發(fā)現(xiàn)方法

2.1 移動(dòng)社區(qū)網(wǎng)絡(luò)模型

移動(dòng)社區(qū)網(wǎng)絡(luò)中不僅包含用戶-用戶的社交關(guān)系，還包含了用戶-地理位置偏好關(guān)系和用戶-媒體偏好關(guān)系。本節(jié)根據(jù)用戶間社交行為和移動(dòng)網(wǎng)絡(luò)使用詳單數(shù)據(jù)來(lái)構(gòu)建移動(dòng)社區(qū)網(wǎng)絡(luò)模型，下面給出具體定義。

定義1用戶-用戶社交關(guān)系網(wǎng)絡(luò)。用戶間的社交行為可簡(jiǎn)單表示為無(wú)向圖結(jié)構(gòu)，記為S=(U,O)，其中，U={u1,u2,…,uM}表示用戶集，O表示用戶社交關(guān)系的邊集，O={oij|oij=(ui,uj),ui,uj∈U}，其中oij是ui和uj之間表示社交關(guān)系的邊。

移動(dòng)網(wǎng)絡(luò)使用詳單數(shù)據(jù)的格式如表1所示，移動(dòng)用戶通過(guò)基站訪問(wèn)網(wǎng)絡(luò)內(nèi)容時(shí)基站側(cè)會(huì)進(jìn)行記錄，其中，開始時(shí)間和結(jié)束時(shí)間這個(gè)時(shí)間區(qū)間表示基站服務(wù)該訪問(wèn)請(qǐng)求的時(shí)長(zhǎng)，基站位置為基站的地理經(jīng)緯度信息，用戶ID為加密的用戶編號(hào)，訪問(wèn)內(nèi)容即通過(guò)基站請(qǐng)求的網(wǎng)絡(luò)內(nèi)容。為了方便，本文對(duì)基站的位置進(jìn)行標(biāo)簽化處理，以基站的編號(hào)代表基站的位置，基站位置集合記為L(zhǎng)={l1,l2,…,lN}。另外，對(duì)于眾多的網(wǎng)絡(luò)內(nèi)容進(jìn)行主題歸類，主題類別集合記為T={t1,t2,…,tF}。

表1 移動(dòng)網(wǎng)絡(luò)使用詳單數(shù)據(jù)

定義2用戶-位置關(guān)系網(wǎng)絡(luò)。根據(jù)UDR數(shù)據(jù)中的基站位置信息，用戶與位置形成的偏好關(guān)系用網(wǎng)絡(luò)表示為加權(quán)無(wú)向圖P，記為P=(U,L,R)，其中，U表示用戶集，L表示地理位置集，R表示圖中關(guān)系邊的權(quán)重關(guān)系集合，即R={rij|rij=(ui,lj),ui∈U,lj∈L}，其中rij表示用戶ui對(duì)位置lj的偏好。統(tǒng)計(jì)一段時(shí)間區(qū)間內(nèi)用戶ui在每個(gè)基站的服務(wù)時(shí)長(zhǎng)，作為該用戶在各位置的滯留時(shí)長(zhǎng)，滯留時(shí)長(zhǎng)序列記為ηi=[ni1,ni2,…,niN]，其中ni1表示用戶ui在位置l1的滯留時(shí)長(zhǎng)，那么rij以u(píng)i在位置lj上的滯留時(shí)長(zhǎng)占ui總滯留時(shí)長(zhǎng)的比例表示：

(2)

定義3用戶-主題關(guān)系網(wǎng)絡(luò)。用戶通過(guò)基站訪問(wèn)內(nèi)容的行為形成的關(guān)系網(wǎng)絡(luò)可表示為加權(quán)無(wú)向圖B，記為B=(U,T,W)，其中，U表示用戶集，T表示內(nèi)容主題集，W表示圖中關(guān)系邊的權(quán)重關(guān)系集合，即W={wij|wij=(ui,tj),ui∈U,tj∈T}，其中wij表示用戶ui對(duì)主題tj的興趣偏好。統(tǒng)計(jì)一段時(shí)間區(qū)間內(nèi)用戶ui訪問(wèn)的內(nèi)容主題的頻次，頻次序列記為γi=[mi1,mi2,…,miF]，其中mi1表示用戶ui訪問(wèn)主題為t1的內(nèi)容的次數(shù)，那么wij以訪問(wèn)內(nèi)容主題為tj的頻次占ui總請(qǐng)求頻次的比例表示為：

(3)

2.1.1 社交相似度網(wǎng)絡(luò)

社交相似度指的是用戶在社交拓?fù)渖系倪B接緊密程度。在社交拓?fù)渲腥?個(gè)節(jié)點(diǎn)間連接數(shù)量越多且連接路徑越短，則2個(gè)節(jié)點(diǎn)之間連接越緊密?；谝陨显瓌t，采用Katz算法[16]衡量社交相似度，不僅考慮2個(gè)節(jié)點(diǎn)之間的最短路徑，還考慮2個(gè)節(jié)點(diǎn)之間的所有路徑。同時(shí)，增加一個(gè)衰減因子α來(lái)控制不同長(zhǎng)度的路徑對(duì)2個(gè)節(jié)點(diǎn)之間相似度貢獻(xiàn)值，具體如下:

(4)

(5)

2.1.2 地理位置相似度網(wǎng)絡(luò)

地理位置相似度指的是用戶間在地理位置分布特征的相接近程度。利用余弦相似度表示為：

(6)

進(jìn)一步地，地理位置相似度網(wǎng)絡(luò)表示為：

(7)

2.1.3 主題相似度網(wǎng)絡(luò)

主題相似度指的是用戶間主題興趣偏好的相接近程度。同樣地，根據(jù)余弦相似度表示為：

(8)

進(jìn)一步，主題相似度網(wǎng)絡(luò)表示為：

(9)

2.2 BNMF-NF算法描述

對(duì)于上述多個(gè)相似網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)，本文提出的BNMF-NF算法首先通過(guò)加權(quán)網(wǎng)絡(luò)融合的方式構(gòu)建用戶相似度網(wǎng)絡(luò)：

V=(1-θ-ω)·Simsocial+θ·Simlocation+ω·Simtopic

(10)

其中，V表示融合后的相似網(wǎng)絡(luò)，為了適應(yīng)不同的場(chǎng)景加上θ和ω伸縮因子調(diào)整各部分的權(quán)重，例如當(dāng)希望得到同一個(gè)校區(qū)的用戶群體時(shí)，用戶地理位置相似特征應(yīng)占據(jù)較大的權(quán)重，當(dāng)更希望得到具有相似主題興趣的用戶群體時(shí)，用戶主題興趣偏好的相似特征應(yīng)占據(jù)較大的權(quán)重。對(duì)相似網(wǎng)絡(luò)V進(jìn)行非負(fù)矩陣分解，表示為：

(11)

其中，W為隸屬度矩陣，其每行元素的值表示每個(gè)節(jié)點(diǎn)隸屬于各社區(qū)的程度，k為預(yù)設(shè)社區(qū)個(gè)數(shù)?？紤]在實(shí)際的社區(qū)結(jié)構(gòu)中，網(wǎng)絡(luò)中的節(jié)點(diǎn)通常不會(huì)同時(shí)屬于多個(gè)社區(qū)[17]，因此對(duì)隸屬度矩陣行向量施加l2范數(shù)約束以增強(qiáng)其稀疏性。同理，對(duì)H矩陣的列向量施加l1范數(shù)約束以增強(qiáng)其稀疏性。改進(jìn)的有界非負(fù)矩陣分解如下：

(12)

其中，‖·‖F(xiàn)表示Frobenius范數(shù)，Wi,:和H:,j分別表示W(wǎng)的行向量和H的列向量，β和λ均為非負(fù)系數(shù)。目標(biāo)函數(shù)(12)對(duì)于W和H整體而言是非凸的，使用交替最速下降法和迭代策略可求得其局部最優(yōu)解，迭代更新式：

(13)

(14)

再對(duì)W(i+1)矩陣的各行進(jìn)行歸一化處理：

(15)

具體算法描述如下：

算法1BNMF-NF社區(qū)發(fā)現(xiàn)算法

輸入：相似網(wǎng)絡(luò)Simsocial、Simlocation和Simtopic，權(quán)重θ和ω，社區(qū)簇k，系數(shù)β和λ，誤差ε

輸出：隸屬度矩陣W

1.通過(guò)公式(10)計(jì)算得到用戶相似網(wǎng)絡(luò)V

2.令i=1，隨機(jī)非負(fù)初始化矩陣W(i)和H(i)，并由公式(15)歸一化處理隸屬度矩陣W(i)

3.REPEAT

4.通過(guò)公式(13)計(jì)算更新H(i+1)

5.通過(guò)公式(14)計(jì)算W(i+1)

6.由公式(15)歸一化處理隸屬度矩陣W(i+1)

7.ε(i+1)=|D(V‖WH)(i+1)-D(V‖WH)(i)|

8.i=i+1

9.UNTILi>imax或ε(i+1)≤ε

10.RETURNW(i)

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

3.1 數(shù)據(jù)集描述

本文選取中國(guó)電信運(yùn)營(yíng)商提供的某市匿名UDR數(shù)據(jù)集[18-22]，該數(shù)據(jù)集包含上萬(wàn)個(gè)用戶，覆蓋數(shù)千個(gè)基站，持續(xù)時(shí)間為一個(gè)月，以通信會(huì)話為基礎(chǔ)，記錄上萬(wàn)用戶通過(guò)基站訪問(wèn)網(wǎng)絡(luò)的行為。數(shù)據(jù)集的每個(gè)條目由匿名用戶標(biāo)識(shí)符、基站位置、會(huì)話時(shí)間、日期和月份組成。由于此匿名數(shù)據(jù)集缺少了用戶社交關(guān)系等信息，另外選擇Foursquare(NYC)數(shù)據(jù)集，該數(shù)據(jù)集包含了用戶-用戶社交關(guān)系和主題評(píng)論數(shù)據(jù)，并將這2個(gè)數(shù)據(jù)集通過(guò)映射組成新的實(shí)驗(yàn)數(shù)據(jù)集。由于數(shù)據(jù)集本身存在一些噪聲數(shù)據(jù)以及訪問(wèn)稀疏的位置點(diǎn)，實(shí)驗(yàn)先對(duì)數(shù)據(jù)集進(jìn)行過(guò)濾，將基站位置標(biāo)簽化并將主題進(jìn)行分類，再篩選出請(qǐng)求數(shù)超過(guò)5條的用戶及其擁有的社交關(guān)系。預(yù)處理完畢后，新的數(shù)據(jù)集包含2321個(gè)用戶、2407個(gè)位置和378個(gè)主題。

3.2 對(duì)比算法與評(píng)價(jià)指標(biāo)

為了驗(yàn)證本文提出的社區(qū)發(fā)現(xiàn)方法的有效性，選取如下算法進(jìn)行對(duì)比實(shí)驗(yàn)：

1)Louvain：基于模塊度優(yōu)化的快速社區(qū)發(fā)現(xiàn)算法，只考慮用戶節(jié)點(diǎn)的社交關(guān)系。

2)J-NMF: 程結(jié)晶等人[23]提出的一種聯(lián)合矩陣分解的劃分算法，在本實(shí)驗(yàn)中考慮用戶社交關(guān)系和用戶主題偏好關(guān)系進(jìn)行聯(lián)合矩陣分解。

3)BNMF-NF：本文提出的社區(qū)發(fā)現(xiàn)方法。

為了評(píng)價(jià)社區(qū)結(jié)構(gòu)的劃分質(zhì)量，引入模塊度Q值函數(shù)，定義為：

(16)

其中，V表示節(jié)點(diǎn)集合；M表示鄰接矩陣；di和dj分別表示節(jié)點(diǎn)i和j的度；ci和cj分別表示節(jié)點(diǎn)i和j所處的社區(qū)，當(dāng)i和j屬同一社區(qū)時(shí)δ(ci,cj)=1，否則為0；m表示網(wǎng)絡(luò)中邊的總數(shù)。

除了衡量社區(qū)結(jié)構(gòu)的劃分質(zhì)量外，主題興趣的內(nèi)聚性也是一種衡量社區(qū)劃分內(nèi)在特性的重要指標(biāo)[24]，描述社區(qū)內(nèi)所有用戶的主題興趣相似度定義如下：

(17)

其中，|EC|表示社區(qū)的邊數(shù)，計(jì)算可知，當(dāng)IC值越高時(shí)，社區(qū)的主題興趣內(nèi)聚性越好。

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

本實(shí)驗(yàn)主要關(guān)注算法在實(shí)驗(yàn)數(shù)據(jù)集覆蓋位置中具有相似主題偏好的用戶群體的劃分效果，經(jīng)多次選擇并設(shè)置伸縮因子θ和ω均為0.4，使得位置偏好相似特征和主題偏好相似特征均占據(jù)更重要的角色。在社區(qū)結(jié)構(gòu)特征評(píng)價(jià)上，比較了3種算法在實(shí)驗(yàn)數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果。圖1統(tǒng)計(jì)了不同社區(qū)規(guī)模下的用戶數(shù)，Louvain算法只劃分出13個(gè)社區(qū)，而J-NMF算法和BNMF-NF算法劃分的社區(qū)數(shù)相當(dāng)。

圖1 不同社區(qū)規(guī)模下的用戶數(shù)

表2給出了不同算法在多個(gè)社區(qū)簇參數(shù)下的模塊度。

表2 3種算法在不同社區(qū)簇k參數(shù)下模塊度對(duì)比

從表2可以看出，Louvain算法不受參數(shù)k的限制，根據(jù)式(16)所得到的Q值為0.2297，由于只考慮用戶的社交關(guān)系，獲得的模塊度值均小于其他算法。另外，J-NMF算法和BNMF-NF算法模塊度值都隨著社區(qū)簇參數(shù)k的增大先增加再減小，在k=20時(shí)，模塊度都達(dá)到最大值。比較實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，BNMF-NF算法相比J-NMF算法在不同社區(qū)簇參數(shù)下均能獲得更高的Q值，故社區(qū)發(fā)現(xiàn)的效果更好。

為了評(píng)價(jià)社區(qū)內(nèi)在的主題興趣內(nèi)聚性，本文比較了3種算法在數(shù)據(jù)集上獲得的社區(qū)IC指標(biāo)，結(jié)果如圖2所示。不難看出，BNMF-NF算法所得到的主題興趣相似度維持在0.4左右，高于其他算法。由于Louvain算法只考慮用戶社交關(guān)系而導(dǎo)致社區(qū)主題興趣內(nèi)聚性較低。綜上實(shí)驗(yàn)結(jié)果表明，本文提出的BNMF-NF算法所獲得的社區(qū)不僅表現(xiàn)出緊密的外在結(jié)構(gòu)特征，還能達(dá)到更好的主題興趣內(nèi)聚性。

圖2 社區(qū)主題興趣內(nèi)聚性

4 結(jié)束語(yǔ)

本文針對(duì)多維異質(zhì)的移動(dòng)網(wǎng)絡(luò)提出了一種融合多維信息的社區(qū)發(fā)現(xiàn)方法BNMF-NF。具體地，從社交關(guān)系數(shù)據(jù)和移動(dòng)網(wǎng)絡(luò)使用詳單數(shù)據(jù)出發(fā)，構(gòu)建由移動(dòng)用戶、地理位置和內(nèi)容主題等實(shí)體構(gòu)成的異質(zhì)網(wǎng)絡(luò)模型，并利用網(wǎng)絡(luò)融合的方法融合多維信息。改進(jìn)了非負(fù)矩陣分解的稀疏性約束并采用交替最速下降法和迭代策略得到矩陣變量的迭代更新式，最終得到最優(yōu)的社區(qū)劃分結(jié)果。最后，實(shí)驗(yàn)結(jié)果表明，本文提出的BNMF-NF方法所獲得的社區(qū)不僅表現(xiàn)出緊密的外在結(jié)構(gòu)特征，還能達(dá)到更好的主題興趣內(nèi)聚性。

在未來(lái)的工作中，筆者將進(jìn)一步優(yōu)化網(wǎng)絡(luò)融合過(guò)程，使得多網(wǎng)絡(luò)融合能降低噪聲，以后還考慮引入時(shí)間信息挖掘隨時(shí)間而動(dòng)態(tài)演化的社區(qū)結(jié)構(gòu)。