一種基于移動用戶行為的回路融合社區發現算法

肖 覓 孟祥武 史艷翠

(北京郵電大學智能通信軟件與多媒體北京市重點實驗室 北京 100876)

(北京郵電大學計算機學院 北京 100876)

1 引言

隨著移動網絡服務的日益涌現及其廣泛應用，移動網絡服務類型和信息內容的增長將逐漸超出人們所能接受的范圍，加之移動設備的界面顯示、終端處理、輸入輸出等能力有限，將導致嚴重的“移動信息過載”問題[1]。如何實時、準確地為移動用戶提供個性化的移動網絡服務是其盈利最大化的關鍵。社區發現是一種解決用戶需求個性化問題的可行方法，并且廣泛應用于互聯網社會化網絡服務中。與互聯網相比，移動網絡中移動用戶主要與朋友，同事及家人等聯系，所構成的移動社會網絡比較稀疏，因此不能完全依照互聯網中社會化網絡服務的方法對移動社會化網絡進行分析。“位置”、“實時性”、“綁定身份”和“動態交互”是移動互聯網區別于傳統互聯網的關鍵特性[2]。因此將移動用戶行為引入到社區發現中，能起到很好的輔助作用，提高移動社區發現的準確性。

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

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

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

2 算法設計及分析

2.1 移動社會化網絡模型

設圖G=＜V,E＞是一個簡單無向圖，頂點集為V= {v1,v2,… ,vN}，其中vi表示移動通信網中的移動用戶；邊集為E，如果移動用戶vi與vj有通話記錄，則vi與vj用無向邊相連，記為eij=＜vi,vj＞;N表示移動用戶的個數，本文用網絡圖來對移動社會化網絡進行建模。現實世界中通話方式分為主叫方和被叫方，但實際研究中不能簡單通過主叫或被叫來判斷兩人的地位關系，所以本文將這種有向關系轉化為無向關系進行研究。

2.2 基于移動用戶行為的移動社會化網絡構建

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

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

其中 t tc(v1,v2)i表示移動用戶v1與v2第i次的通信時長，m1表示通信次數。

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

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

定義3移動用戶v1對v2的相關度DC(Degree of Correlation), DC定義如下：

其中α≥0為權重參數，用來調節通話時長和通信次數的權重，α根據3.3節(1)中介紹的遺傳算法調優得到。

定義4移動用戶間相關度閾值TDC(Threshold of DC)：在一次實驗中固定不變的數值，用來限定用戶間相關度的最小值。利用這個數值把低于閾值的用戶間相關度值所對應的聯系去除，即將由圖G表示的移動社會化網絡的相應邊去除。當TDC設定太小，所得到的移動社會化網絡將引入一些不必要的邊，即移動用戶之間的聯系；當TDC太大時，所得到的移動社會化網絡將丟失一些移動用戶之間的聯系。本文根據 3.1節的評價方法進行多次重復試驗選取合適的TDC。

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

FDC(v1,v2)表示移動用戶v1與v2間通信時長的參照值。

按照以下規則對移動社會化網絡模型圖G進行篩選，完成基于移動用戶行為的移動社會化網絡構建。

(1)當 F DC(v1,v2) ≥ 0 時，保留圖G中節點v1與v2所對應的邊 ＜v1,v2＞ ；

(2)當 F DC(v1,v2) ＜ 0 時，刪除圖G中節點v1與v2所對應的邊 ＜v1,v2＞ 。

定義6孤立子群：社會化網絡中與其他群體沒有邊關聯的群體稱為孤立子群，包括只有一個節點的孤立節點[12]。

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

通過對文獻[13]所使用的EC簡單回路生成算法進行修改得到k-EC算法，k-EC算法用限定生成回路的長度為k來得到適合本文社區發現的回路。

2.3.1 k-EC算法k值合理性分析基于小世界理論及六度分割理論[14]，將k的上限設定為6。當k＞6時，算法的效率會降低，并且太長的回路很有可能會使社區發現結果不精確，即在密集的網絡中只能發現一個或少數幾個很大的社區，不能夠真正區分社區結構，失去社區發現的意義。根據簡單回路的定義可知最小回路的長度為3，因此將k的下限設定為3。綜上所述，k的取值范圍為3≤k≤6。

2.4 CM算法及正確性證明

2.4.1 CM算法描述

(1)利用2.3節介紹的k-EC算法提取每個孤立子群中滿足規定長度的所有回路，將得到的回路當作是社區核，將這樣的社區核的集合表示為Γ；同時將沒有社區核的孤立子群看作一個獨立社區，加入Γ中。

(2)社區核按照以下規則進行融合：

其中count(C)表示社區C包含的節點個數。如果社區核C1和C2滿足式(5)，將這兩個社區核進行融合，形成一個新的社區核C′，新的社區核C′添加到Γ中，并在Γ中刪除社區核C1和C2。

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

(4)Ψ表示網絡中沒有加入任何一個社區并且與Γ中的一個或多個社區有鄰邊的節點的集合。對于任意節點θ∈Ψ，如果θ只與一個社區相連，則將θ加入到這個社區中；如果θ與多個社區(C1,C2,…,Cn1)相連，則分別計算θ與每個社區中有連接邊的節點的相關度之和，記為 D Ci(i= 1 ,… ,n1)。將θ加入DCi取最大值時所對應的社區中，如果DCi的最大值有幾個社區對應，則將θ加入對應的幾個社區中。

(5)如果所有節點都加入到一個或多個社區，則得到了最后的社區集合Γ，算法終止，否則執行(4)。

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

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

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

終止：由于網絡中的節點數目的有限的，即為移動用戶個數N，初始化中部分節點歸屬已經確定，而步驟(4)中每次都會處理完一個節點，因此算法會重復執行不多于N次，最終會在步驟(5)停止，此時?θ1∈V都有θ1∈Ci,Ci∈Γ，即每個節點都有社區歸屬，綜上可以得出算法是正確的。

3 實驗

本小節描述實驗方案設計以及實驗結果分析，實驗環境為：2 GB內存，2.66 GHz雙核 CPU,Windows7操作系統，Java1.6開發語言，Myeclipse8.5和Matlab R2010a集成環境，Mysql5.1數據庫。

3.1實驗數據

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

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

表1 屬性范圍限定

3.2 評價方法

本文采用文獻[5]中提出的適用于重疊社區發現的模塊度Qo評價方法，定義如下：

其中A代表社區社會化網絡圖G的鄰接矩陣，me是網絡中的總邊數，Γ是社區的集合，kv是節點v的度數，αCv表示表示節點v屬于社區C的程度，定義如下：

3.3 實驗描述及結果分析

(1)CM 參數調優及可行性驗證實驗：利用 3.1節介紹的數據集對CM算法進行實驗，選定兩個用戶之間的相處行為為實驗室內和實驗室外的相處時長。首先，對數據進行清洗，刪去通信行為為空或通信行為記錄為0的用戶；然后用CM算法對移動通信網進行社區發現，得到生成的社區；由于目標函數與用戶相關度密切相關，所以利用matlab數據包中的遺傳算法(Genetic Algorithm, GA)函數分別對兩個數據集參數進行調優，適應度函數定義如下：

通過遺傳算法調優得到兩個數據集的最優參數值如表2所示。

然后根據表2中的參數和3.2節介紹的評價方法對模塊度和TDC進行調優。通過對公開數據集反復試驗對參數TDC進行調優，得到最優的模塊度值Qo1= 0 .3521，此時TDC=0.1；對仿真數據集反復試驗對參數TDC進行調優，得到最優的模塊度值Qo2= 0 .5362，此時TDC=0.15。

表2 調優參數值

圖1為公開數據集的CM社區圖，區域A和區域B表示對應的社區1和社區2所包含的節點，區域C表示重疊的節點。由文獻[5]所計算出的模塊度可知本文計算出的模塊度Qo1和Qo2在一個合理的范圍內。由圖1可知，本文算法很好地區分了整個網絡圖稀疏和密集的部分，因此可得本文提出的 CM算法對派系較少的網絡具有良好的可行性和有效性。

(2)CPM, OCBCC, CM對比實驗：第1節介紹的CPM是當前最流行的重疊社區發現算法之一[4]，OCBCC是比較新的重疊社區發現算法[5]，CM是本文所提出的算法，CM的參數基于實驗1的參數進行設置。本節利用3.1節介紹的數據集并結合3.2節介紹的評價方法對這3種算法進行對比實驗，實驗結果如表3所示。

表3 模塊度Qo對比

通過對比分析可以得出對 3.1節介紹的公開數據集來構建的派系較少網絡時，使用 CM 算法比OCBCC算法的模塊度提高了131%，比CPM算法模塊度提高了108%；對仿真數據集構建的派系較少的網絡時，使用CM算法比OCBCC算法模塊度提高了94%，比CPM算法模塊度提高了48%。以上結果充分說明CM算法對于派系較少的網絡和具有移動特性的網絡的社區發現具有更好的性能。

4 結束語

圖1 公開數據集的移動社會化網絡社區圖

本文面向移動社會化網絡，提出了一種基于移動用戶行為的回路融合移動社區發現(簡稱 CM)算法，通過加入移動用戶行為，采用所提出的回路融合算法，來對移動社會化網絡進行CM算法社區發現。實驗部分，首先通過實驗1，對CM算法的參數進行調優并且對該算法的有效性進行了驗證；然后通過實驗2，驗證了CM算法對于派系較少網絡的社區發現具有更好的模塊度Qo。實驗結果表明，CM 算法能夠解決移動社會化網絡的派系較少的網絡社區發現的問題，并且具有較好的模塊度Qo。由于CM算法基于簡單回路，相比于基于派系的算法條件更加寬松，所以對于一般派系足夠多的網絡來說，也能夠實施CM算法。

[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]. 中國計算機學會通訊, 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]黃武漢, 孟祥武, 王立才. 移動通信網中基于用戶社會化關系挖掘的協同過濾算法[J]. 電子與信息學報, 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]李峰, 申利民, 司亞利, 等. 一種基于實體用戶行為和時間戳的信任預測模型[J]. 電子與信息學報, 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]萬里, 廖建新, 朱曉民. 一種時間序列頻繁模式挖掘算法及其在WSAN行為預測中的應用[J]. 電子與信息學報, 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]吳鵬, 李思昆. 適于社會網絡結構分析與可視化的布局算法[J]. 軟件學報, 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]黃永生, 孟祥武, 張玉潔. 基于社會網絡特征的P2P內容定位策略[J]. 軟件學報, 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.