洪小龍

（廣州杰賽科技股份有限公司，廣東 廣州 510310）

1 引言

隨著移動(dòng)互聯(lián)網(wǎng)的快速發(fā)展，越來(lái)越多的用戶通過(guò)移動(dòng)終端可以隨時(shí)隨地與他人進(jìn)行交流或者購(gòu)物。移動(dòng)運(yùn)營(yíng)商越來(lái)越關(guān)注移動(dòng)用戶“指尖上的消費(fèi)”的行為傾向[1]，采用社區(qū)發(fā)現(xiàn)算法來(lái)挖掘移動(dòng)用戶的團(tuán)體結(jié)構(gòu)，為精準(zhǔn)營(yíng)銷提供了數(shù)據(jù)支撐。社會(huì)學(xué)的創(chuàng)始人柯曉華[2]認(rèn)為社會(huì)團(tuán)體的演變能夠在一定程度上解釋社會(huì)現(xiàn)象變化的成因。因此，移動(dòng)社區(qū)的發(fā)現(xiàn)是研究移動(dòng)社交網(wǎng)絡(luò)的一個(gè)重要任務(wù)。社區(qū)發(fā)現(xiàn)算法首先用于信息科學(xué)、社會(huì)科學(xué)以及管理科學(xué)等領(lǐng)域，并從非重疊社區(qū)發(fā)現(xiàn)起步，如KL（Kernighan Lin）算法[3]、GN（Given Newman）算法[4]以及快速Newman算法[5]等。非重疊發(fā)現(xiàn)算法得到的社區(qū)結(jié)構(gòu)是互相獨(dú)立的，社區(qū)之間不存在交集。顯然，這些算法并不能有效地解釋現(xiàn)實(shí)社交網(wǎng)絡(luò)存在的重疊社區(qū)現(xiàn)象。重疊的社區(qū)發(fā)現(xiàn)算法從實(shí)現(xiàn)的機(jī)制來(lái)說(shuō)，可以分為兩類：基于節(jié)點(diǎn)分裂的和基于模塊度優(yōu)化的。LFM算法[6]是基于模塊度優(yōu)化機(jī)制實(shí)現(xiàn)的；CPM算法[7]采用完全子圖的方法構(gòu)建重疊矩陣，然后將重疊矩陣變成社區(qū)社團(tuán)鄰接矩陣實(shí)現(xiàn)重疊社區(qū)的劃分；CONGA算法[8]是基于節(jié)點(diǎn)分裂的機(jī)制實(shí)現(xiàn)的，該算法是采用傳統(tǒng)的GN算法發(fā)現(xiàn)非重疊社區(qū)，然后通過(guò)計(jì)算節(jié)點(diǎn)之間的介數(shù)來(lái)決定節(jié)點(diǎn)的社團(tuán)歸屬。傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法沒(méi)有考慮移動(dòng)用戶之間的上下文信息，本文提出基于移動(dòng)社交網(wǎng)絡(luò)的重疊社區(qū)發(fā)現(xiàn)方法。首先，通過(guò)預(yù)處理的手段剔除社交網(wǎng)絡(luò)中關(guān)系不穩(wěn)定的邊；其次，采用GN算法實(shí)現(xiàn)社交網(wǎng)絡(luò)的劃分，并確定若干個(gè)社區(qū)核；最后，通過(guò)計(jì)算離散節(jié)點(diǎn)與社區(qū)內(nèi)每一個(gè)節(jié)點(diǎn)的時(shí)空相似度，結(jié)合相似度閾值判斷節(jié)點(diǎn)的歸屬性，從而實(shí)現(xiàn)移動(dòng)社交網(wǎng)絡(luò)的重疊社區(qū)的發(fā)現(xiàn)。

2 移動(dòng)社交網(wǎng)絡(luò)重疊社區(qū)的相關(guān)研究

2.1 移動(dòng)社交網(wǎng)絡(luò)的用戶關(guān)系

移動(dòng)社交網(wǎng)絡(luò)跟傳統(tǒng)的社交網(wǎng)絡(luò)不同，移動(dòng)社交網(wǎng)絡(luò)是一種虛擬的網(wǎng)絡(luò)，它不僅反映現(xiàn)實(shí)生活中的人際關(guān)系，還能夠反映移動(dòng)用戶的興趣圈。那就意味著，如果要全面分析移動(dòng)社交網(wǎng)絡(luò)的用戶關(guān)系，不僅要分析移動(dòng)用戶之間的交互次數(shù)，還要考慮移動(dòng)用戶上下文等因素對(duì)用戶關(guān)系的影響。因此，本文所指移動(dòng)社交網(wǎng)絡(luò)的用戶關(guān)系，是用移動(dòng)用戶之間的交互次數(shù)以及移動(dòng)軌跡的相似性等因素來(lái)衡量移動(dòng)用戶社交的緊密程度。

2.2 重疊社區(qū)發(fā)現(xiàn)方法

（1）CPM算法

社團(tuán)過(guò)濾算法（Clique Percolation Method，CPM）通過(guò)引入“完全子圖”的概念采用迭代遞歸的方式把整個(gè)網(wǎng)絡(luò)劃分成多個(gè)完全子圖；然后利用上述的“完全子圖”構(gòu)建重疊矩陣；再通過(guò)輸入的K值構(gòu)建派系連接矩陣，最終實(shí)現(xiàn)重疊社團(tuán)的發(fā)現(xiàn)。由于派系過(guò)濾算法是一個(gè)全局計(jì)算而得算法，因此效率通常比較低，不適用于大規(guī)模的網(wǎng)絡(luò)。不少學(xué)者已經(jīng)意識(shí)到該算法的缺陷，采用一些數(shù)據(jù)預(yù)處理的方法剔除不穩(wěn)定的邊，來(lái)提升算法的速度。

（2）SLPA算法

標(biāo)簽傳播算法（Label Propagation Algorithm，LPA）最早是由Raghavan提出來(lái)的。作為一種非重疊社團(tuán)的方法，首先給每一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)指定一個(gè)唯一的標(biāo)簽；然后隨機(jī)選擇一個(gè)節(jié)點(diǎn)并將其標(biāo)簽傳播給其鄰居節(jié)點(diǎn)，其鄰居節(jié)點(diǎn)的最終標(biāo)簽劃定是根據(jù)多次迭代結(jié)果決定的。作為擴(kuò)展的SLPA（Speaker-listener Label Propagation Algorithm，SLPA）與LPA不同，它記錄每一個(gè)節(jié)點(diǎn)的標(biāo)簽序列，并通過(guò)概率決定節(jié)點(diǎn)的社團(tuán)歸屬，在迭代結(jié)果趨于穩(wěn)定后可根據(jù)標(biāo)簽出現(xiàn)的概率來(lái)決定當(dāng)前節(jié)點(diǎn)被劃分到一個(gè)社區(qū)還是多個(gè)社區(qū)。該算法由于需要在全局層面上多次迭代才能完成，因此其計(jì)算效率不高。

3 基于移動(dòng)社交網(wǎng)絡(luò)的重疊社區(qū)發(fā)現(xiàn)

3.1 實(shí)驗(yàn)環(huán)境介紹

實(shí)驗(yàn)環(huán)境：Windows Server 2016，Intel Core i5 3.1 GHz，16 GB內(nèi)存，1 TB HDD。

3.2 數(shù)據(jù)獲取及數(shù)據(jù)介紹

運(yùn)營(yíng)商的數(shù)據(jù)系統(tǒng)中會(huì)記錄移動(dòng)用戶在發(fā)生業(yè)務(wù)過(guò)程中的大多數(shù)信息，包括用戶號(hào)碼、業(yè)務(wù)開始時(shí)間、業(yè)務(wù)結(jié)束時(shí)間、發(fā)生業(yè)務(wù)的類型、發(fā)生業(yè)務(wù)的基站位置等。本文選取了某個(gè)區(qū)域的500名實(shí)驗(yàn)用戶6個(gè)月的移動(dòng)業(yè)務(wù)數(shù)據(jù)，業(yè)務(wù)數(shù)據(jù)包括通過(guò)通話、短信、微信、QQ等模式進(jìn)行社會(huì)交往且運(yùn)營(yíng)商能夠獲取的數(shù)據(jù)。本文通過(guò)對(duì)上述500名用戶進(jìn)行問(wèn)卷調(diào)查，讓他們根據(jù)最近3~6個(gè)月中最信任或者最愿意交往的若干用戶聯(lián)系方式，從而得出該500名用戶的社區(qū)劃分標(biāo)簽。從原始社區(qū)劃分的結(jié)果來(lái)看，用戶的社區(qū)劃分是重疊的，也就是一個(gè)用戶能夠從屬于多個(gè)社區(qū)。本文將多種方法的劃分結(jié)果與預(yù)先設(shè)定的社區(qū)劃分結(jié)果進(jìn)行比較，以驗(yàn)證本文算法的準(zhǔn)確性。

3.3 實(shí)驗(yàn)思路

首先，根據(jù)移動(dòng)用戶的業(yè)務(wù)數(shù)據(jù)構(gòu)建社交網(wǎng)絡(luò)并對(duì)網(wǎng)絡(luò)進(jìn)行預(yù)處理。根據(jù)移動(dòng)用戶的通信業(yè)務(wù)構(gòu)建移動(dòng)社交網(wǎng)絡(luò)，該網(wǎng)絡(luò)的構(gòu)建原則是，只要移動(dòng)用戶之間存在業(yè)務(wù)關(guān)聯(lián)，那么就認(rèn)為用戶之間存在一條邊，能夠反映用戶的社交情況。在構(gòu)建社交網(wǎng)絡(luò)的基礎(chǔ)上，通過(guò)對(duì)一些不穩(wěn)定的邊進(jìn)行預(yù)處理，一方面能夠降低算法的復(fù)雜度，也能提升算法的精度。

其次，采用GN算法提取社區(qū)核。通過(guò)GN算法能夠找到若干個(gè)不相交的集合，這種集合其實(shí)是重疊社區(qū)的雛形。

再次，采用時(shí)空相似性算法判斷離散點(diǎn)與社區(qū)核內(nèi)個(gè)點(diǎn)之間的時(shí)空相似性，以便判斷離散點(diǎn)的歸屬問(wèn)題。

最后，離散點(diǎn)社區(qū)的判定。通過(guò)對(duì)比相似性閾值，判斷社區(qū)的社區(qū)歸屬。值得注意的是，離散點(diǎn)的社區(qū)歸屬并不是一一映射的關(guān)系，可以是一對(duì)一，也可以是一對(duì)多的關(guān)系。

（1）數(shù)據(jù)預(yù)處理

按照本文的算法對(duì)數(shù)據(jù)進(jìn)行預(yù)處理。眾所周知，通過(guò)移動(dòng)用戶的業(yè)務(wù)數(shù)據(jù)構(gòu)成的移動(dòng)社交網(wǎng)絡(luò)中，有一些邊是不穩(wěn)定的。因此本文把用戶的交互次數(shù)小于一定數(shù)量的邊去掉，降低算法的復(fù)雜度。相關(guān)的移動(dòng)社交網(wǎng)絡(luò)如圖1所示：

圖1 原始的用戶移動(dòng)社交圖

在圖1的移動(dòng)社交網(wǎng)絡(luò)圖中，節(jié)點(diǎn)之間存在一條邊，表示移動(dòng)用戶之間有至少一次的交互次數(shù)。本文把移動(dòng)用戶在2個(gè)月內(nèi)的交互次數(shù)閾值設(shè)為10，如果在2個(gè)月內(nèi)，用戶之間的累積次數(shù)小于10，那么可以認(rèn)為用戶之間的關(guān)系是不穩(wěn)定的，兩節(jié)點(diǎn)之間的邊可認(rèn)為是無(wú)效邊，應(yīng)該剔除。剔除結(jié)果如圖2所示：

圖2 數(shù)據(jù)處理后的用戶移動(dòng)社交圖

（2）社區(qū)核的提取

GN作為一種分裂式的圖聚類算法，首先，刪除邊介數(shù)最大的邊，把一個(gè)社團(tuán)分為多個(gè)不相交的集合；然后再刪除每一個(gè)集合中最大邊介數(shù)的邊，如此不斷地刪除網(wǎng)絡(luò)中最弱連接的邊；最終把網(wǎng)絡(luò)分成多個(gè)非重疊社團(tuán)。本文在對(duì)數(shù)據(jù)進(jìn)行預(yù)處理后，采用GN算法對(duì)上述的數(shù)據(jù)集進(jìn)行處理，形成若干個(gè)社區(qū)核以及離散點(diǎn)。社區(qū)核是重疊社區(qū)的雛形，而下一步就需要計(jì)算離散點(diǎn)與社區(qū)核中各點(diǎn)的時(shí)空相似性，以此判斷離散點(diǎn)的社區(qū)歸屬。

（3）移動(dòng)用戶時(shí)空關(guān)系的相似性

本文借鑒相關(guān)的研究[9]，通過(guò)時(shí)空相似度來(lái)反映所有用戶在不同時(shí)間段在地理位置的相似度來(lái)衡量用戶的時(shí)空相似性。把一天分為3個(gè)時(shí)間段：9：00-17：00上班時(shí)間段；17：00-22：00下班時(shí)間段；22：00-次日8：00休息時(shí)間段。然后分別計(jì)算這3個(gè)時(shí)間段移動(dòng)用戶在地理上的重合度。

其中，△T為各個(gè)時(shí)間段的時(shí)間精度，Ti(u)表示用戶到達(dá)基站li(u)的時(shí)刻。同理，Ti(v)表示用戶到達(dá)基站li(v)的時(shí)刻。如果用戶u和用戶v在某個(gè)時(shí)間段內(nèi)曾經(jīng)到達(dá)同一個(gè)基站，那么δ(li(u), li(v))=1，否則為0。θ為3個(gè)時(shí)間段各自設(shè)定的權(quán)值。

通過(guò)計(jì)算離散點(diǎn)與社區(qū)核內(nèi)各節(jié)點(diǎn)的時(shí)空相似性進(jìn)行加權(quán)平均，得出的加權(quán)平均值作為離散點(diǎn)與社區(qū)內(nèi)核的綜合時(shí)空相似度。

（4）社區(qū)歸屬判定

在對(duì)離散節(jié)點(diǎn)判定社區(qū)歸屬前，需要計(jì)算移動(dòng)用戶時(shí)空關(guān)系相似性閾值，該閾值將決定離散節(jié)點(diǎn)的社區(qū)劃分結(jié)果。

移動(dòng)用戶時(shí)空關(guān)系相似性的閾值設(shè)置參考Farkas的強(qiáng)度函數(shù)公式計(jì)算得出：

其中，C為派系集合，u表示離散點(diǎn)，v表示社區(qū)核，CoL表示協(xié)方差，n表示GN劃分社團(tuán)后離散點(diǎn)的數(shù)量，m表示社區(qū)核的數(shù)量。上述公式的計(jì)算過(guò)程為：

1）首先，選取任意一個(gè)社區(qū)核中的任意一個(gè)點(diǎn)v與任意一個(gè)離散點(diǎn)u生成協(xié)方差；接著，再選取社區(qū)核中的另外一個(gè)點(diǎn)與離散點(diǎn)u生成協(xié)方差，不斷迭代，直至把社區(qū)核中的全部點(diǎn)都參與計(jì)算后，對(duì)每一個(gè)協(xié)方差進(jìn)行連乘。

2）離散點(diǎn)u繼續(xù)選取其他社區(qū)核重復(fù)第1）步的方法，直至全部社區(qū)核的每一個(gè)點(diǎn)與離散點(diǎn)生成對(duì)應(yīng)的協(xié)方差并進(jìn)行連乘。

3）選取其他的離散點(diǎn)重復(fù)第1）步和第2）步方法進(jìn)行計(jì)算，得到最終的閾值結(jié)果。

通過(guò)把移動(dòng)用戶的時(shí)空相似性與上述的閾值進(jìn)行比較，如果存在一個(gè)離散點(diǎn)的時(shí)空關(guān)系相似性度量值大于設(shè)定的閾值，那么該離散節(jié)點(diǎn)從屬于一個(gè)或者多個(gè)社區(qū)；否則，該離散節(jié)點(diǎn)不從屬于任何社區(qū)。

4 實(shí)驗(yàn)分析

本文提出的基于移動(dòng)社交網(wǎng)絡(luò)的重疊社區(qū)發(fā)現(xiàn)算法與傳統(tǒng)的SLPA算法、CPM算法進(jìn)行比較，在真實(shí)的移動(dòng)社交網(wǎng)絡(luò)背景下，將數(shù)據(jù)預(yù)處理以及沒(méi)有預(yù)處理下得到的結(jié)果進(jìn)行測(cè)試，得到的結(jié)果如圖3所示：

圖3 本文提出算法與傳統(tǒng)SLPM、CPM算法比較

由圖3得到的結(jié)論為：在剔除移動(dòng)社交網(wǎng)絡(luò)無(wú)效邊后進(jìn)行社區(qū)劃分的準(zhǔn)確率高于直接進(jìn)行社區(qū)劃分的準(zhǔn)確率。

本文的實(shí)驗(yàn)結(jié)論為：

（1）在噪音影響的背景下，本文提出的方法受到噪音的影響程度比較小，穩(wěn)定性較高。

（2）當(dāng)前的移動(dòng)社交網(wǎng)絡(luò)的確存在用戶關(guān)系不穩(wěn)定的邊，該類別的邊會(huì)直接影響社區(qū)發(fā)現(xiàn)的精度。通過(guò)將不穩(wěn)定的邊剔除后，算法的精度將會(huì)得到不同程度的提高。

（3）通過(guò)定量來(lái)衡量節(jié)點(diǎn)之間的關(guān)系，將會(huì)更真實(shí)地反映移動(dòng)用戶網(wǎng)絡(luò)中存在多關(guān)系社區(qū)的情況。

（4）本文提出的算法與傳統(tǒng)的CPM算法和SLPA算法相比較，其精度和穩(wěn)定性較高。

本文提出的重疊算法，實(shí)質(zhì)上就是一種多關(guān)系社區(qū)發(fā)現(xiàn)方法。與傳統(tǒng)方法不一樣，本文提出的方法能夠考慮到離散點(diǎn)與各社區(qū)核關(guān)系之間的差異，這與傳統(tǒng)的一視同仁算法是有差異的。傳統(tǒng)方法下，某些關(guān)系噪音會(huì)造成多關(guān)系社區(qū)的結(jié)果不如只考慮單個(gè)關(guān)系進(jìn)行社區(qū)發(fā)現(xiàn)的結(jié)果。但文本的方法就是采用定量來(lái)衡量社區(qū)關(guān)系并從閾值層面來(lái)評(píng)判離散點(diǎn)的歸屬問(wèn)題。該方法比較適用于病毒營(yíng)銷，運(yùn)營(yíng)商根據(jù)離散點(diǎn)與社區(qū)核的關(guān)系大小將多關(guān)系的社區(qū)融合成一個(gè)綜合關(guān)系社區(qū)信息網(wǎng)絡(luò)，然后針對(duì)該社區(qū)信息網(wǎng)絡(luò)的特點(diǎn)進(jìn)行特定領(lǐng)域的產(chǎn)品或者方案營(yíng)銷，將會(huì)更有效率地傳播特定的信息。

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

本文基于真實(shí)的移動(dòng)用戶數(shù)據(jù)構(gòu)建移動(dòng)社交網(wǎng)絡(luò)，提出基于移動(dòng)社交網(wǎng)絡(luò)的重疊社區(qū)發(fā)現(xiàn)方法。首先對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，剔除社交網(wǎng)絡(luò)中關(guān)系不穩(wěn)定的邊；其次，采用GN算法提取社區(qū)核；最后，在計(jì)算移動(dòng)用戶時(shí)空關(guān)系的相似性后借助閾值判斷離散節(jié)點(diǎn)的歸屬。實(shí)驗(yàn)證明，基于移動(dòng)社交網(wǎng)絡(luò)的重疊社區(qū)發(fā)現(xiàn)算法與傳統(tǒng)的CPM算法相比具有較高的準(zhǔn)確性。