一種基于移動(dòng)用戶行為的回路融合社區(qū)發(fā)現(xiàn)算法

肖 覓 孟祥武 史艷翠

(北京郵電大學(xué)智能通信軟件與多媒體北京市重點(diǎn)實(shí)驗(yàn)室 北京 100876)

(北京郵電大學(xué)計(jì)算機(jī)學(xué)院 北京 100876)

1 引言

隨著移動(dòng)網(wǎng)絡(luò)服務(wù)的日益涌現(xiàn)及其廣泛應(yīng)用，移動(dòng)網(wǎng)絡(luò)服務(wù)類型和信息內(nèi)容的增長(zhǎng)將逐漸超出人們所能接受的范圍，加之移動(dòng)設(shè)備的界面顯示、終端處理、輸入輸出等能力有限，將導(dǎo)致嚴(yán)重的“移動(dòng)信息過載”問題[1]。如何實(shí)時(shí)、準(zhǔn)確地為移動(dòng)用戶提供個(gè)性化的移動(dòng)網(wǎng)絡(luò)服務(wù)是其盈利最大化的關(guān)鍵。社區(qū)發(fā)現(xiàn)是一種解決用戶需求個(gè)性化問題的可行方法，并且廣泛應(yīng)用于互聯(lián)網(wǎng)社會(huì)化網(wǎng)絡(luò)服務(wù)中。與互聯(lián)網(wǎng)相比，移動(dòng)網(wǎng)絡(luò)中移動(dòng)用戶主要與朋友，同事及家人等聯(lián)系，所構(gòu)成的移動(dòng)社會(huì)網(wǎng)絡(luò)比較稀疏，因此不能完全依照互聯(lián)網(wǎng)中社會(huì)化網(wǎng)絡(luò)服務(wù)的方法對(duì)移動(dòng)社會(huì)化網(wǎng)絡(luò)進(jìn)行分析?！拔恢谩薄ⅰ皩?shí)時(shí)性”、“綁定身份”和“動(dòng)態(tài)交互”是移動(dòng)互聯(lián)網(wǎng)區(qū)別于傳統(tǒng)互聯(lián)網(wǎng)的關(guān)鍵特性[2]。因此將移動(dòng)用戶行為引入到社區(qū)發(fā)現(xiàn)中，能起到很好的輔助作用，提高移動(dòng)社區(qū)發(fā)現(xiàn)的準(zhǔn)確性。

移動(dòng)社會(huì)化網(wǎng)絡(luò)是一個(gè)現(xiàn)實(shí)網(wǎng)絡(luò)，每個(gè)用戶可以屬于多個(gè)社區(qū)，比如朋友社區(qū)、同事社區(qū)和家人社區(qū)等，因此本文著重研究重疊社區(qū)發(fā)現(xiàn)問題。文獻(xiàn)[3]中總結(jié)了目前重疊社區(qū)發(fā)現(xiàn)算法，大體上分為派系(完全子圖)過濾算法和非派系過濾算法。派系過濾算法：Palla等人[4]提出了用于發(fā)現(xiàn)重疊社區(qū)的派系過濾CPM(Clique Percolation Method)算法，如果網(wǎng)絡(luò)中的派系非常密集，該算法將把整個(gè)網(wǎng)絡(luò)認(rèn)為是一個(gè)社區(qū)；OCBCC (Overlapping Communities Based on Community Cores)算法是將派系作為初始的社區(qū)核心[5]，然后將社區(qū)核有條件地進(jìn)行融合，最后將剩余節(jié)點(diǎn)根據(jù)給定的規(guī)則加入到相應(yīng)的社區(qū)。以上兩種算法都是以派系為基礎(chǔ)，對(duì)派系較少的網(wǎng)絡(luò)難以實(shí)施。非派系過濾算法：基于標(biāo)簽傳播是一類主要的算法，RAK(文獻(xiàn)[7]根據(jù)文獻(xiàn)[6]的作者Raghavan, Albert, Kumara命名)算法是一個(gè)簡(jiǎn)單的標(biāo)簽傳播算法[6]，RAK算法受多種隨機(jī)性因素影響，其結(jié)果不穩(wěn)定，每次產(chǎn)生的社區(qū)結(jié)構(gòu)存在一定差異；COPRA(Community Overlap PRopagation Algorithm)在 RAK 標(biāo)簽傳播的基礎(chǔ)上[7]，使每個(gè)節(jié)點(diǎn)攜帶多個(gè)標(biāo)簽，通過擴(kuò)展標(biāo)簽的方式進(jìn)行重疊社區(qū)劃分，但是COPRA需要指定v參數(shù)，此參數(shù)對(duì)社區(qū)發(fā)現(xiàn)的結(jié)果影響很大，所以該算法有一定的局限性。

近年來，實(shí)體用戶行為的研究越來越廣泛，文獻(xiàn)[8]利用移動(dòng)用戶行為信息建立模型，得出用戶之間的信任關(guān)系及其信任程度，并將其與基于項(xiàng)目評(píng)分的相似度結(jié)合，應(yīng)用到項(xiàng)目評(píng)分預(yù)測(cè)模型中。文獻(xiàn)[9]提出以實(shí)體用戶行為和時(shí)間戳為條件的信任預(yù)測(cè)模型，引入多維測(cè)量指標(biāo)度量實(shí)體交互滿意度，使得滿意度計(jì)算更加精確。這些研究結(jié)果表明實(shí)體用戶行為可以很好地預(yù)測(cè)用戶之間的信任關(guān)系，提高算法的精確性。

根據(jù)上述研究，本文提出一種基于移動(dòng)用戶行為的回路融合社區(qū)發(fā)現(xiàn)算法，簡(jiǎn)稱 CM(Circuits Merging)算法。該算法具有以下意義：(1)相比于目前的基于派系的社區(qū)發(fā)現(xiàn)算法，CM 算法對(duì)派系較少的網(wǎng)絡(luò)可以得到更好的社區(qū)劃分；(2)提出的回路融合策略和節(jié)點(diǎn)添加策略能有效地提高模塊度；(3)通過加入移動(dòng)用戶行為，使得社區(qū)的劃分具有了移動(dòng)社會(huì)化網(wǎng)絡(luò)的特性，提高了劃分的準(zhǔn)確性，這樣的社區(qū)為文獻(xiàn)[10]中闡述的移動(dòng)服務(wù)推薦提供了基礎(chǔ)。本文第2節(jié)提出和分析了基于移動(dòng)用戶行為的回路融合社區(qū)發(fā)現(xiàn)算法；第3節(jié)利用公開數(shù)據(jù)集和仿真數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)驗(yàn)證，結(jié)果表明了該算法的有效性和合理性；最后給出結(jié)論。

2 算法設(shè)計(jì)及分析

2.1 移動(dòng)社會(huì)化網(wǎng)絡(luò)模型

設(shè)圖G=＜V,E＞是一個(gè)簡(jiǎn)單無向圖，頂點(diǎn)集為V= {v1,v2,… ,vN}，其中vi表示移動(dòng)通信網(wǎng)中的移動(dòng)用戶；邊集為E，如果移動(dòng)用戶vi與vj有通話記錄，則vi與vj用無向邊相連，記為eij=＜vi,vj＞;N表示移動(dòng)用戶的個(gè)數(shù)，本文用網(wǎng)絡(luò)圖來對(duì)移動(dòng)社會(huì)化網(wǎng)絡(luò)進(jìn)行建模?，F(xiàn)實(shí)世界中通話方式分為主叫方和被叫方，但實(shí)際研究中不能簡(jiǎn)單通過主叫或被叫來判斷兩人的地位關(guān)系，所以本文將這種有向關(guān)系轉(zhuǎn)化為無向關(guān)系進(jìn)行研究。

2.2 基于移動(dòng)用戶行為的移動(dòng)社會(huì)化網(wǎng)絡(luò)構(gòu)建

與互聯(lián)網(wǎng)及固話網(wǎng)相比，移動(dòng)用戶行為具有如下特征：(1)移動(dòng)用戶行為的可確定性，這種可確定性表現(xiàn)為移動(dòng)通信設(shè)備通常是一個(gè)號(hào)碼對(duì)應(yīng)一個(gè)確定的用戶，這是本文研究移動(dòng)用戶行為的基礎(chǔ)，而固定電話和互聯(lián)網(wǎng)沒有這種對(duì)應(yīng)關(guān)系，用戶行為不可確定；(2)上下文信息，與互聯(lián)網(wǎng)及固話網(wǎng)相比，由于移動(dòng)網(wǎng)絡(luò)的特點(diǎn)，移動(dòng)用戶受周圍環(huán)境的影響更加明顯，并且通過移動(dòng)終端、傳感器、GPS以及基站等可以獲取移動(dòng)用戶實(shí)時(shí)的上下文信息，例如時(shí)間、位置、情緒、周圍人員以及社會(huì)關(guān)系；(3)移動(dòng)用戶可以通過語(yǔ)音、短信、飛信等方式進(jìn)行通信，而且手機(jī)還提供拍攝、視頻錄制、音樂播放、網(wǎng)頁(yè)瀏覽、下載應(yīng)用軟件、GPS定位等功能，而固定電話除了語(yǔ)音通話，缺少以上這些豐富的服務(wù)體驗(yàn)。為了提高移動(dòng)社區(qū)劃分的準(zhǔn)確性，本文將移動(dòng)用戶間的通信行為、移動(dòng)用戶與周圍人員位置相處信息(位置、時(shí)長(zhǎng))引入到移動(dòng)社區(qū)發(fā)現(xiàn)算法中，其中位置信息包括實(shí)驗(yàn)室、家、工作單位等。

定義1移動(dòng)用戶間總的語(yǔ)音通信時(shí)長(zhǎng)TTC(Total Time of Communication)：表示移動(dòng)用戶v1與v2總的語(yǔ)音通信時(shí)長(zhǎng)，在不考慮主叫和被叫差異的前提下，TTC定義如下：

其中 t tc(v1,v2)i表示移動(dòng)用戶v1與v2第i次的通信時(shí)長(zhǎng)，m1表示通信次數(shù)。

定義2移動(dòng)用戶與周圍人員總的相處時(shí)長(zhǎng)TTL(Total Time of Location)：表示移動(dòng)用戶v1與v2總的相處時(shí)長(zhǎng)，TTL定義如下：

以移動(dòng)用戶v1和v2為例，將v1與其聯(lián)系人的所有通話時(shí)長(zhǎng)求和得到 T TC(v1),v1與v2的所有通話時(shí)長(zhǎng)為 T TC(v1,v2)，將v1與周圍人員的相處時(shí)長(zhǎng)求和得到總相處時(shí)長(zhǎng) T TL(v1),v1與v2的相處時(shí)長(zhǎng)為TTL(v1,v2)。

定義3移動(dòng)用戶v1對(duì)v2的相關(guān)度DC(Degree of Correlation), DC定義如下：

其中α≥0為權(quán)重參數(shù)，用來調(diào)節(jié)通話時(shí)長(zhǎng)和通信次數(shù)的權(quán)重，α根據(jù)3.3節(jié)(1)中介紹的遺傳算法調(diào)優(yōu)得到。

定義4移動(dòng)用戶間相關(guān)度閾值TDC(Threshold of DC)：在一次實(shí)驗(yàn)中固定不變的數(shù)值，用來限定用戶間相關(guān)度的最小值。利用這個(gè)數(shù)值把低于閾值的用戶間相關(guān)度值所對(duì)應(yīng)的聯(lián)系去除，即將由圖G表示的移動(dòng)社會(huì)化網(wǎng)絡(luò)的相應(yīng)邊去除。當(dāng)TDC設(shè)定太小，所得到的移動(dòng)社會(huì)化網(wǎng)絡(luò)將引入一些不必要的邊，即移動(dòng)用戶之間的聯(lián)系；當(dāng)TDC太大時(shí)，所得到的移動(dòng)社會(huì)化網(wǎng)絡(luò)將丟失一些移動(dòng)用戶之間的聯(lián)系。本文根據(jù) 3.1節(jié)的評(píng)價(jià)方法進(jìn)行多次重復(fù)試驗(yàn)選取合適的TDC。

定義5移動(dòng)用戶間頻繁相關(guān)度FDC(Frequency of DC)：借鑒文獻(xiàn)[11]中頻繁模式的定義思想，F(xiàn)DC表示移動(dòng)用戶間相關(guān)度值與相關(guān)度閾值的差值，F(xiàn)DC定義如下：

FDC(v1,v2)表示移動(dòng)用戶v1與v2間通信時(shí)長(zhǎng)的參照值。

按照以下規(guī)則對(duì)移動(dòng)社會(huì)化網(wǎng)絡(luò)模型圖G進(jìn)行篩選，完成基于移動(dòng)用戶行為的移動(dòng)社會(huì)化網(wǎng)絡(luò)構(gòu)建。

(1)當(dāng) F DC(v1,v2) ≥ 0 時(shí)，保留圖G中節(jié)點(diǎn)v1與v2所對(duì)應(yīng)的邊 ＜v1,v2＞ ；

(2)當(dāng) F DC(v1,v2) ＜ 0 時(shí)，刪除圖G中節(jié)點(diǎn)v1與v2所對(duì)應(yīng)的邊 ＜v1,v2＞ 。

定義6孤立子群：社會(huì)化網(wǎng)絡(luò)中與其他群體沒有邊關(guān)聯(lián)的群體稱為孤立子群，包括只有一個(gè)節(jié)點(diǎn)的孤立節(jié)點(diǎn)[12]。

2.3 k-EC算法k值合理性分析及算法效率分析

通過對(duì)文獻(xiàn)[13]所使用的EC簡(jiǎn)單回路生成算法進(jìn)行修改得到k-EC算法，k-EC算法用限定生成回路的長(zhǎng)度為k來得到適合本文社區(qū)發(fā)現(xiàn)的回路。

2.3.1 k-EC算法k值合理性分析基于小世界理論及六度分割理論[14]，將k的上限設(shè)定為6。當(dāng)k＞6時(shí)，算法的效率會(huì)降低，并且太長(zhǎng)的回路很有可能會(huì)使社區(qū)發(fā)現(xiàn)結(jié)果不精確，即在密集的網(wǎng)絡(luò)中只能發(fā)現(xiàn)一個(gè)或少數(shù)幾個(gè)很大的社區(qū)，不能夠真正區(qū)分社區(qū)結(jié)構(gòu)，失去社區(qū)發(fā)現(xiàn)的意義。根據(jù)簡(jiǎn)單回路的定義可知最小回路的長(zhǎng)度為3，因此將k的下限設(shè)定為3。綜上所述，k的取值范圍為3≤k≤6。

2.4 CM算法及正確性證明

2.4.1 CM算法描述

(1)利用2.3節(jié)介紹的k-EC算法提取每個(gè)孤立子群中滿足規(guī)定長(zhǎng)度的所有回路，將得到的回路當(dāng)作是社區(qū)核，將這樣的社區(qū)核的集合表示為Γ；同時(shí)將沒有社區(qū)核的孤立子群看作一個(gè)獨(dú)立社區(qū)，加入Γ中。

(2)社區(qū)核按照以下規(guī)則進(jìn)行融合：

其中count(C)表示社區(qū)C包含的節(jié)點(diǎn)個(gè)數(shù)。如果社區(qū)核C1和C2滿足式(5)，將這兩個(gè)社區(qū)核進(jìn)行融合，形成一個(gè)新的社區(qū)核C′，新的社區(qū)核C′添加到Γ中，并在Γ中刪除社區(qū)核C1和C2。

(3)如果Γ中沒有新的社區(qū)核生成，則Γ為生成的初步社區(qū)集合，執(zhí)行(4)，否則執(zhí)行(2)。

(4)Ψ表示網(wǎng)絡(luò)中沒有加入任何一個(gè)社區(qū)并且與Γ中的一個(gè)或多個(gè)社區(qū)有鄰邊的節(jié)點(diǎn)的集合。對(duì)于任意節(jié)點(diǎn)θ∈Ψ，如果θ只與一個(gè)社區(qū)相連，則將θ加入到這個(gè)社區(qū)中；如果θ與多個(gè)社區(qū)(C1,C2,…,Cn1)相連，則分別計(jì)算θ與每個(gè)社區(qū)中有連接邊的節(jié)點(diǎn)的相關(guān)度之和，記為 D Ci(i= 1 ,… ,n1)。將θ加入DCi取最大值時(shí)所對(duì)應(yīng)的社區(qū)中，如果DCi的最大值有幾個(gè)社區(qū)對(duì)應(yīng)，則將θ加入對(duì)應(yīng)的幾個(gè)社區(qū)中。

(5)如果所有節(jié)點(diǎn)都加入到一個(gè)或多個(gè)社區(qū)，則得到了最后的社區(qū)集合Γ，算法終止，否則執(zhí)行(4)。

2.4.2 算法正確性證明本文選擇利用文獻(xiàn)[15]所使用的循環(huán)不變式證明方法對(duì)CM算法進(jìn)行證明，將CM 算法歸納為如下的循環(huán)不定式：在每一輪循環(huán)開始前，對(duì) ?θ1∈Ci,Ci∈Γ，這樣的節(jié)點(diǎn)θ1最后屬于哪個(gè)社區(qū)是確定的，每一輪循環(huán)將沒有社區(qū)歸屬的節(jié)點(diǎn)θ歸類到一個(gè)或多個(gè)社區(qū)，使得θ∈Ci,Ci∈Γ。

初始化：步驟(1)利用k-EC算法將網(wǎng)絡(luò)中的回路提取出來作為社區(qū)核，Γ為社區(qū)核集合，步驟(2)和步驟(3)將社區(qū)核進(jìn)行合并形成初步社區(qū)，并得到新的集合Γ，對(duì) ?θ1∈Ci,Ci∈Γ，節(jié)點(diǎn)θ1在后面的循環(huán)中是不會(huì)再被處理，所以節(jié)點(diǎn)θ1社區(qū)歸屬確定不變，這樣就證明了循環(huán)不變式在循環(huán)前是成立的；

保持：在步驟(4)的循環(huán)中，每次處理一個(gè)節(jié)點(diǎn)θ∈Ψ，計(jì)算θ與有邊連接的社區(qū)的相關(guān)度DCi(i=1,…,n1)，選擇max(DC(θ)) = D Ci，將θ→Ci，因此一旦DCi計(jì)算出來，θ的社區(qū)歸屬通過這一規(guī)則確定了，在重疊社區(qū)的環(huán)境下，θ可能加入一個(gè)或多個(gè)社區(qū)，使得θ∈Ci,Ci∈Γ，因此每一輪循環(huán)都可以保證循環(huán)的不變式成立；

終止：由于網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)目的有限的，即為移動(dòng)用戶個(gè)數(shù)N，初始化中部分節(jié)點(diǎn)歸屬已經(jīng)確定，而步驟(4)中每次都會(huì)處理完一個(gè)節(jié)點(diǎn)，因此算法會(huì)重復(fù)執(zhí)行不多于N次，最終會(huì)在步驟(5)停止，此時(shí)?θ1∈V都有θ1∈Ci,Ci∈Γ，即每個(gè)節(jié)點(diǎn)都有社區(qū)歸屬，綜上可以得出算法是正確的。

3 實(shí)驗(yàn)

本小節(jié)描述實(shí)驗(yàn)方案設(shè)計(jì)以及實(shí)驗(yàn)結(jié)果分析，實(shí)驗(yàn)環(huán)境為：2 GB內(nèi)存，2.66 GHz雙核 CPU,Windows7操作系統(tǒng)，Java1.6開發(fā)語(yǔ)言，Myeclipse8.5和Matlab R2010a集成環(huán)境，Mysql5.1數(shù)據(jù)庫(kù)。

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

公開數(shù)據(jù)集：麻省理工學(xué)院多媒體實(shí)驗(yàn)室MIT收集的數(shù)據(jù)集[16]，包括94個(gè)移動(dòng)用戶從2004年9月到2005年6月共9個(gè)月移動(dòng)用戶的行為信息，并包括通話記錄(通話和短信的時(shí)間、電話的主叫和被叫、短信的發(fā)送和接收)、位置、手機(jī)狀態(tài)、藍(lán)牙設(shè)備等信息。數(shù)據(jù)集中包括通過問卷調(diào)查得出的94個(gè)移動(dòng)用戶之間的好友關(guān)系，以及用戶在實(shí)驗(yàn)室內(nèi)和實(shí)驗(yàn)室外與其他人員的相處時(shí)間等數(shù)據(jù)。

仿真數(shù)據(jù)集：參考公開數(shù)據(jù)集的格式，生成實(shí)驗(yàn)所需要的仿真數(shù)據(jù)集。該數(shù)據(jù)集包含移動(dòng)用戶通信行為列表、移動(dòng)用戶位置列表，其中移動(dòng)通信行為列表包含用戶標(biāo)識(shí)，通信聯(lián)系人標(biāo)識(shí)及每次通信時(shí)長(zhǎng)；移動(dòng)用戶位置列表分為實(shí)驗(yàn)室內(nèi)和實(shí)驗(yàn)室外兩種情況，分別包括用戶標(biāo)識(shí)，相處聯(lián)系人標(biāo)識(shí)及每次相處時(shí)長(zhǎng)。移動(dòng)用戶規(guī)模設(shè)為5000，將其分成5組。假定組內(nèi)用戶間關(guān)系較為緊密，組間用戶較為稀疏，即設(shè)定組內(nèi)移動(dòng)用戶間的通信時(shí)長(zhǎng)(相處時(shí)長(zhǎng))占本組用戶總通信時(shí)長(zhǎng)(總相處時(shí)長(zhǎng))的80%的比例，組內(nèi)用戶和其他組的用戶通信時(shí)長(zhǎng)(相處時(shí)長(zhǎng))占20%的比例。參考公開數(shù)據(jù)集，限定移動(dòng)用戶標(biāo)識(shí)，每次通信時(shí)長(zhǎng)和每次相處時(shí)長(zhǎng)的范圍(如表1)。為了適應(yīng)于本文考察派系較少網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)情況，需要對(duì)隨機(jī)生成的數(shù)據(jù)集進(jìn)行派系刪減，將網(wǎng)絡(luò)中90%的派系隨機(jī)去掉一條或多條邊，使得這些派系的結(jié)構(gòu)不滿足。

表1 屬性范圍限定

3.2 評(píng)價(jià)方法

本文采用文獻(xiàn)[5]中提出的適用于重疊社區(qū)發(fā)現(xiàn)的模塊度Qo評(píng)價(jià)方法，定義如下：

其中A代表社區(qū)社會(huì)化網(wǎng)絡(luò)圖G的鄰接矩陣，me是網(wǎng)絡(luò)中的總邊數(shù)，Γ是社區(qū)的集合，kv是節(jié)點(diǎn)v的度數(shù)，αCv表示表示節(jié)點(diǎn)v屬于社區(qū)C的程度，定義如下：

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

(1)CM 參數(shù)調(diào)優(yōu)及可行性驗(yàn)證實(shí)驗(yàn)：利用 3.1節(jié)介紹的數(shù)據(jù)集對(duì)CM算法進(jìn)行實(shí)驗(yàn)，選定兩個(gè)用戶之間的相處行為為實(shí)驗(yàn)室內(nèi)和實(shí)驗(yàn)室外的相處時(shí)長(zhǎng)。首先，對(duì)數(shù)據(jù)進(jìn)行清洗，刪去通信行為為空或通信行為記錄為0的用戶；然后用CM算法對(duì)移動(dòng)通信網(wǎng)進(jìn)行社區(qū)發(fā)現(xiàn)，得到生成的社區(qū)；由于目標(biāo)函數(shù)與用戶相關(guān)度密切相關(guān)，所以利用matlab數(shù)據(jù)包中的遺傳算法(Genetic Algorithm, GA)函數(shù)分別對(duì)兩個(gè)數(shù)據(jù)集參數(shù)進(jìn)行調(diào)優(yōu)，適應(yīng)度函數(shù)定義如下：

通過遺傳算法調(diào)優(yōu)得到兩個(gè)數(shù)據(jù)集的最優(yōu)參數(shù)值如表2所示。

然后根據(jù)表2中的參數(shù)和3.2節(jié)介紹的評(píng)價(jià)方法對(duì)模塊度和TDC進(jìn)行調(diào)優(yōu)。通過對(duì)公開數(shù)據(jù)集反復(fù)試驗(yàn)對(duì)參數(shù)TDC進(jìn)行調(diào)優(yōu)，得到最優(yōu)的模塊度值Qo1= 0 .3521，此時(shí)TDC=0.1；對(duì)仿真數(shù)據(jù)集反復(fù)試驗(yàn)對(duì)參數(shù)TDC進(jìn)行調(diào)優(yōu)，得到最優(yōu)的模塊度值Qo2= 0 .5362，此時(shí)TDC=0.15。

表2 調(diào)優(yōu)參數(shù)值

圖1為公開數(shù)據(jù)集的CM社區(qū)圖，區(qū)域A和區(qū)域B表示對(duì)應(yīng)的社區(qū)1和社區(qū)2所包含的節(jié)點(diǎn)，區(qū)域C表示重疊的節(jié)點(diǎn)。由文獻(xiàn)[5]所計(jì)算出的模塊度可知本文計(jì)算出的模塊度Qo1和Qo2在一個(gè)合理的范圍內(nèi)。由圖1可知，本文算法很好地區(qū)分了整個(gè)網(wǎng)絡(luò)圖稀疏和密集的部分，因此可得本文提出的 CM算法對(duì)派系較少的網(wǎng)絡(luò)具有良好的可行性和有效性。

(2)CPM, OCBCC, CM對(duì)比實(shí)驗(yàn)：第1節(jié)介紹的CPM是當(dāng)前最流行的重疊社區(qū)發(fā)現(xiàn)算法之一[4]，OCBCC是比較新的重疊社區(qū)發(fā)現(xiàn)算法[5]，CM是本文所提出的算法，CM的參數(shù)基于實(shí)驗(yàn)1的參數(shù)進(jìn)行設(shè)置。本節(jié)利用3.1節(jié)介紹的數(shù)據(jù)集并結(jié)合3.2節(jié)介紹的評(píng)價(jià)方法對(duì)這3種算法進(jìn)行對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表3所示。

表3 模塊度Qo對(duì)比

通過對(duì)比分析可以得出對(duì) 3.1節(jié)介紹的公開數(shù)據(jù)集來構(gòu)建的派系較少網(wǎng)絡(luò)時(shí)，使用 CM 算法比OCBCC算法的模塊度提高了131%，比CPM算法模塊度提高了108%；對(duì)仿真數(shù)據(jù)集構(gòu)建的派系較少的網(wǎng)絡(luò)時(shí)，使用CM算法比OCBCC算法模塊度提高了94%，比CPM算法模塊度提高了48%。以上結(jié)果充分說明CM算法對(duì)于派系較少的網(wǎng)絡(luò)和具有移動(dòng)特性的網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)具有更好的性能。

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

圖1 公開數(shù)據(jù)集的移動(dòng)社會(huì)化網(wǎng)絡(luò)社區(qū)圖

本文面向移動(dòng)社會(huì)化網(wǎng)絡(luò)，提出了一種基于移動(dòng)用戶行為的回路融合移動(dòng)社區(qū)發(fā)現(xiàn)(簡(jiǎn)稱 CM)算法，通過加入移動(dòng)用戶行為，采用所提出的回路融合算法，來對(duì)移動(dòng)社會(huì)化網(wǎng)絡(luò)進(jìn)行CM算法社區(qū)發(fā)現(xiàn)。實(shí)驗(yàn)部分，首先通過實(shí)驗(yàn)1，對(duì)CM算法的參數(shù)進(jìn)行調(diào)優(yōu)并且對(duì)該算法的有效性進(jìn)行了驗(yàn)證；然后通過實(shí)驗(yàn)2，驗(yàn)證了CM算法對(duì)于派系較少網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)具有更好的模塊度Qo。實(shí)驗(yàn)結(jié)果表明，CM 算法能夠解決移動(dòng)社會(huì)化網(wǎng)絡(luò)的派系較少的網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的問題，并且具有較好的模塊度Qo。由于CM算法基于簡(jiǎn)單回路，相比于基于派系的算法條件更加寬松，所以對(duì)于一般派系足夠多的網(wǎng)絡(luò)來說，也能夠?qū)嵤〤M算法。

[1]Chiu Po-huan, Kao Yi-ming, and Lo Chi-chun. Personalized blog content recommender system for mobile phone users[J].International Journal of Human-Computer Studies, 2010,68(8): 496-507.

[2]劉經(jīng)南, 郭遲, 彭瑞卿. 移動(dòng)互聯(lián)網(wǎng)時(shí)代的位置服務(wù)[J]. 中國(guó)計(jì)算機(jī)學(xué)會(huì)通訊, 2011, 12(7): 40-50.

Liu Jing-nan, Guo Chi, and Peng Rui-qing. The locationbased services of mobile Internet era[J].Communications of China Computer Federation, 2011, 12(7): 40-50.

[3]Santo F. Community detection in graphs[J].Physics Reports,2010, 486(3-5): 75-174.

[4]Palla G, Derenyi I, and Farkas I. Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005, 435: 814-818.

[5]Shang Ming-sheng, Chen Duan-bing, and Zhou Tao.Detecting overlapping communities based on community cores in complex networks[J].Chinese Physics Letters, 2010,27(5): 058901(1-4).

[6]Raghavan U N, Albert R, and Kumara S. Near linear time algorithm to detect community structures in large-scale networks[J].Physical Review E, 2007, 76(3): 036106(1-11).

[7]Gregory S. Finding overlapping communities in networks by label propagation[J].New Journal of Physics, 2010, 12(10):103018.

[8]黃武漢, 孟祥武, 王立才. 移動(dòng)通信網(wǎng)中基于用戶社會(huì)化關(guān)系挖掘的協(xié)同過濾算法[J]. 電子與信息學(xué)報(bào), 2011, 33(12):3002-3007.

Huang Wu-han, Meng Xiang-wu, and Wang Li-cai. A collaborative filtering algorithm based on users’ social relationship mining in mobile communication network[J].Journal of Electronics&Information Technology, 2011,33(12): 3002-3007.

[9]李峰, 申利民, 司亞利, 等. 一種基于實(shí)體用戶行為和時(shí)間戳的信任預(yù)測(cè)模型[J]. 電子與信息學(xué)報(bào), 2011, 33(5): 1217-1223.

Li Feng, Shen Li-ming, and Si Ya-li,et al.. A trust forecasting model based on entity context and time stamp[J].Journal of Electronics&Information Technology, 2011, 33(5):1217-1223.

[10]Wang Li-cai, Meng Xiang-wu, and Zhang Yu-jie. A heuristic approach to social network-based and context-aware mobile services recommendation[J].Journal of Convergence Information Technology, 2011, 6(10): 339-346.

[11]萬里, 廖建新, 朱曉民. 一種時(shí)間序列頻繁模式挖掘算法及其在WSAN行為預(yù)測(cè)中的應(yīng)用[J]. 電子與信息學(xué)報(bào), 2010, 32(3):682-686.

Wan Li, Liao Jian-xin, and Zhu Xiao-min. Time series frequent pattern mining algorithm and its application to WSAN behavior prediction[J].Journal of Electronics&Information Technology, 2010, 32(3): 682-686.

[12]吳鵬, 李思昆. 適于社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)分析與可視化的布局算法[J]. 軟件學(xué)報(bào), 2011, 22(10): 2467-2475.

Wu Peng and Li Si-kun. Layout algorithm suitable for structural analysis and visualization of social network[J].Journal of Software, 2011, 22(10): 2467-2475.

[13]Radde N. Fixed point characterization of biological networks with complex graph topology[J].Bioinformatics, 2010, 26(22):2874-2880.

[14]黃永生, 孟祥武, 張玉潔. 基于社會(huì)網(wǎng)絡(luò)特征的P2P內(nèi)容定位策略[J]. 軟件學(xué)報(bào), 2010, 21(10): 2622-2630.

Huang Yong-sheng, Meng Xiang-wu, and Zhang Yu-jie.Strategy of content location of P2P based on the social network[J].Journal of Software, 2010, 21(10): 2622-2630.

[15]Cormen H, Leiserson E, and Rivest L,et al.. Introduction to Algorithms[M]. Second Edition, Beijing: Higher Education Press, 2002, Chapter 2.

[16]Eagle N, Pentland A, and Lazer D. Inferring friendship network structure using mobile phone data[J].Proceedings of the National Academy of Sciences, 2009: 106(36):15274-15278.