改進CPM的移動通信用戶關系圈挖掘

陳少權 杜翠鳳

【摘 要】針對現(xiàn)有社團發(fā)現(xiàn)算法忽略節(jié)點之間的關系強度及其動態(tài)性的問題，提出改進CPM算法挖掘移動通信的用戶關系圈。首先，采用TF-IDF剔除非重要通話群體；然后，引入時間衰減因子，采用用戶通信行為衡量用戶之間動態(tài)關系強度，結合關系閾值剔除節(jié)點之間的弱連接構建大小不同的派系；再次，利用變異系數(shù)來衡量派系中用戶關系之間的相近性，采用變異系數(shù)閾值C.V*剔除關系不緊密的派系；最后，根據(jù)用戶輸入的k值，發(fā)現(xiàn)k-派系社團。實驗證明，通過重疊社團模塊度EQ評測指標驗證，該算法的精確度高于傳統(tǒng)算法的精確度，具有一定的擴展性。

【關鍵詞】關系強度；時間衰減；關系閾值；變異系數(shù)

Relationship Mining of Mobile Communication Users Based on Improved CPM

CHEN Shaoquan， DU Cuifeng

[Abstract] In view of that existing association discovery algorithms ignore the relationship strength and dynamic nature， an improved CPM algorithm is proposed for relationship mining of mobile communication users. First， TF-IDF is used to eliminate unimportant communication groups. Then， the time attenuation factor is introduced and user communication behavior is used to measure the dynamic relationship strength between users. The relationship threshold is used to eliminate the weak connections between nodes to construct different factions of different sizes. Thirdly， the variation coefficient is used to measure the similarity between the user relationships in the factions. The variation coefficient threshold C.V* is used to eliminate the factions which are not closely related. Finally， the k- factional community is found on the basis of the k value input by the user. The experiments prove that the accuracy of the algorithm is higher than that of the traditional algorithm by the EQ evaluation index of overlapping community module degree， and it has a certain extensibility.

[Key words]relationship strength； time attenuation； relationship threshold； coefficient of variation

1 引言

移動通信用戶關系圈是根據(jù)移動用戶的通話關系特征、移動用戶的行為特征，對移動用戶進行社團劃分。這種基于用戶特征的劃分，能夠幫助運營商更加了解用戶關系網(wǎng)絡的構成，為電信業(yè)務的拓展提供科學的支撐。當前有不少成熟的社團劃分算法，如Palla等人[1]于2005年首先提出了派系過濾算法（CPM，Clique Percolation Method），該算法突破了傳統(tǒng)的非重疊社團劃分算法的限制，能夠用來分析重疊的社團結構，其分析結果更貼近現(xiàn)實的社團結構。由于CPM的計算復雜度較大，Lancichinetti等人[2]于2009年從網(wǎng)絡局部結構的角度出發(fā)，提出了基于局部擴展思想的重疊社團挖掘算法（LFM， Local Fitness Measure），提升了社團劃分的速度。Evans[3]和Ahn[4]等人突破傳統(tǒng)以網(wǎng)絡節(jié)點為研究對象進行網(wǎng)絡劃分的局限，提出了邊聚類的社團劃分方法。Evans將網(wǎng)絡結映射成為相應的線圖后，可運用非重疊社團發(fā)現(xiàn)算法來進行重疊社團的劃分。Ahn出了基于邊相似度的層次聚類算法來實現(xiàn)重疊社團的劃分。上述算法大多考慮節(jié)點之間的連接關系，忽略了節(jié)點之間關系的強弱，因此所得出的結果一般不滿足現(xiàn)實的社團劃分需求。因此，相關學者從關系強弱的角度進行了社團劃分的研究，如Onnela[5]等人通過提取電信用戶網(wǎng)絡的權重，利用權重的傳播進行社團發(fā)現(xiàn)的研究。Kumpula[6]通過移動用戶之間的通話行為提取用戶關系的權重，基于權重生成模型實現(xiàn)社團結構的提取，實現(xiàn)社團劃分。采用文獻合作網(wǎng)絡進行統(tǒng)計權重分布，根據(jù)權重大小對網(wǎng)絡的邊進行賦值，實現(xiàn)對社團的劃分[7]。上述研究算法大多數(shù)是基于靜態(tài)的，而實際生活中用戶關系以及用戶圈子的劃分是動態(tài)變化的。除此之外，注重節(jié)點之間連接權重的大小而忽略連接權重離散程度的大小，必然會造成一些不合理的節(jié)點加入到社團中，不利于真實的社團結構的發(fā)現(xiàn)。

本文針對現(xiàn)有社團發(fā)現(xiàn)算法忽略節(jié)點關系強度及特定社團中用戶連接關系變異系數(shù)等問題，在CPM算法中引入具有時間衰減效應的權重信息，并通過權重閾值縮小搜索空間降低算法的復雜度，采用權重變異系數(shù)來識別真正的社團，剔除一些不合理的節(jié)點，提出一種改進CPM的算法來挖掘移動用戶關系圈——基于時間衰減因子和關系變異系數(shù)的CPM算法。在劃分重疊社團后，需要對社團劃分質量進行評價以此說明社團劃分的合理性，當前重疊社團劃分的方法有擴展性模塊度函數(shù)[8]以及社團連通圖評價[9]等方法。由于本文基于用戶關系來實現(xiàn)社團劃分與聯(lián)通效率沒有可比性，因此采用擴展模塊度的方法實現(xiàn)社團劃分質量的評價。

交往圈是指移動用戶聯(lián)系頻繁且保持較長時間交往的用戶群體[10]。本文研究的移動用戶通信關系網(wǎng)是基于移動用戶的通話詳單構建的，由于當前的短信數(shù)量較少，因此本文對短信交往不做考慮。將移動用戶通話看作移動通信社交網(wǎng)的節(jié)點，如果用戶之間存在通話關系，則可在用戶之間添加一條邊，一般可用移動用戶之間通話頻率以及時長大小來衡量移動用戶之間的關系。如果采用上述的通信行為來衡量移動用戶的關系，難免將一些公共號碼等非重要的通話群體納入其中，因此，在提取用戶的通信交往圈前采用TF-IDF算法來進行數(shù)據(jù)的預處理。

假設需要對用戶u的移動用戶交往圈的用戶進行分析，C為移動用戶u交往圈的用戶集合，那么移動用戶u交往圈內(nèi)的其中一位移動用戶v的TF-IDF值為：

TF-IDFuv=tfuv×idfuv （1）

其中，tfuv為用戶u與用戶v的通話頻率，idfuv為用戶v與所有用戶通話的逆頻次，等于用戶u與用戶v的通話次數(shù)/用戶u與所有用戶的通話次數(shù)。因此，如果一個用戶u與其他用戶通話次數(shù)越少，那么idfuv值越高，反之亦然。這個值反映一個用戶在另一個用戶的社交圈子的重要程度，如果用戶u與眾多用戶產(chǎn)生多次通話，那么用戶u圈子里面的好友重要程度都不高；相反，如果用戶u與某幾個用戶產(chǎn)生多次通話，那么用戶u圈子里面的好友重要性程度較高。TF-IDFuv的數(shù)值能夠提出一些公眾號碼、快遞號碼、中介等號碼對用戶圈選取的影響，能夠在一定程度上保證用戶關系圈挖掘算法的精度和速度。

采用TF-IDF算法求出每一個用戶之間的TF-IDF值，然后基于設定的TF-IDF閾值進行預處理。TF-IDF閾值的設置是參考Farkas的派系強度函數(shù)公式計算得出：

（2）

其中，d（u）表示與用戶u產(chǎn)生交往的用戶數(shù)量，也可理解為用戶u的度數(shù)。如果用戶u和用戶v之間的TF-IDF值小于設定的閾值，那么可認為用戶v是用戶u的非重要通話群體并剔除掉。

3.3 提取滿足條件的節(jié)點，找到大小不同的派系

移動通信的社交關系網(wǎng)絡符合指數(shù)為3的冪定律分布的特點[11]，個人之間的聯(lián)系呈現(xiàn)出重力模型的關系。根據(jù)這一特點，結合文獻[11]得出的結論，在利用TF-IDF值剔除非重要通話群體的基礎上，提取網(wǎng)絡度數(shù)大于2的節(jié)點構建滿足度數(shù)條件的社交網(wǎng)絡，縮小派系搜索過程所花費的時間。基于該社交網(wǎng)絡，尋找度數(shù)最大的用戶集合，從該集合中隨機抽取一個用戶出發(fā)，找到包含該用戶大小為g-1的派系后，刪除該用戶以及其連接的用戶；再另選一個用戶尋找包含該用戶大小為g-1的派系，直至集合中沒有用戶為止。同理，g-1派系、g-2派系、…、k派系的尋找方法按照上述步驟進行，當g=k時，算法停止。

3.4 引用時間衰減因子衡量移動用戶之間連接關

系強度

社會網(wǎng)絡中的連接關系在特定的網(wǎng)絡中具有特定的含義：比如在真實社會網(wǎng)絡中表示好友的關系，在移動通信網(wǎng)絡中表示具有相當親密度的用戶之間的通話關系。針對通話詳單的特點，本文認為用戶u和用戶v之間的關系強度不僅考慮用戶通話的頻率以及通話的時長，更應該考慮評價通話行為的時間屬性，也就是需要引入時間衰減因子來反映用戶關系強度的動態(tài)變化特征。用戶之間的近期通話行為更能反映當前用戶之間的關系強度，而隨著時間的推進，越早的通話行為對當前的用戶關系的貢獻越小，在計算用戶關系時需要對其進行更多的折扣。因此，引入時間因子的用戶連接關系強度公式為：

（3）

其中，α和γ為常數(shù)，k表示用戶u和用戶v之間的第k次通話，tuv表示用戶u和用戶v的第k次通話的通話時長，tu是用戶u的總通話時長，tu是用戶u的總通話時長，n表示用戶u和用戶v在一段時間內(nèi)總的通話次數(shù)。

3.5 構建基于變異系數(shù)的帶權派系

對于移動通信的社交網(wǎng)絡來說，如果k-派系的兩兩用戶之間的通信行為大于設定的TF-IDF閾值，那么這k個用戶就構成一個k-派系。一般來說，派系之間的成員聯(lián)系應該非常緊密。但是從用戶之間的權重來說，很難衡量兩兩用戶之間的緊密程度，通常來說，一個派系連邊的權重越相近，則認為派系之間的關系越緊密。很顯然，標準差和變異系數(shù)都能描述一個派系的權重的相近性。圖3展示了3種帶權3-派系的情況，邊上的數(shù)字是根據(jù)上述時間衰減因子結合移動用戶之間的通話時長得出的權重信息，數(shù)值大表示對應用戶之間近期的通話行為越頻繁或者用戶之間近期通話的時間越長。圖3反映了3-派系的用戶之間的關系強度，圖（a）和圖（b）相比，圖（a）的權重越相近，其標準差或者變異系數(shù)都比圖（b）小，因此，圖（a）的用戶u、用戶v以及用戶x越有可能構成3-派系。

（a）緊密型 （b）松散型

圖3 用戶u、用戶v、用戶x構成的3-派系

但是隨著用戶數(shù)量的增加，比如4用戶、5用戶甚至更多的用戶構成更大的派系后，如果采用標準差的方式來設置閾值就顯得不合理，隨著用戶數(shù)量的增加，標準差顯然越來越大。如果采用標準差的方式來衡量用戶關系之間的相近性，肯定無法識別用戶數(shù)量較多的派系。因此，本文采用通信用戶關系變異系數(shù)來衡量用戶關系的相近性。用戶關系變異系數(shù)，又稱“標準差率”，可以用來衡量移動用戶關系的變異程度，能夠在某種程度上反映某個社團中用戶關系的穩(wěn)定性，其公式為：

（4）

其中，σ表示該派系中權重的標準差，μ表示改派系中權重的平均值。

在求出每一個派系的變異系數(shù)后，借鑒Farkas的派系強度函數(shù)計算派系權重變異系數(shù)閾值C.V*，其公式為：

（5）

其中，C為派系集合，u和v表示派系，k表示集合中派系的個數(shù)。如果c.v小于設定的閾值C.V*，則認為該k節(jié)點構成一個基于變異系數(shù)的帶權派系，否則，忽略該k派系。

3.6 挖掘重疊社團，評價社團劃分質量

根據(jù)上一步找到的基于變異系數(shù)的帶權派系，建立帶權派系重疊矩陣C，根據(jù)用戶輸入的k值，結合帶權派系重疊矩陣C，構建帶權派系連接矩陣，并發(fā)現(xiàn)k-派系社團。如何評價社團劃分的合理性是后續(xù)的一個重要的問題。擴展模塊度是描述某個節(jié)點被劃分到多個社團后，是否會對重疊社團的擴展模塊度函數(shù)值產(chǎn)生影響，以此判斷節(jié)點是否可以被多個社團共享。因此，本文借鑒文獻[10]采用擴展模塊度函數(shù)對重疊社團的劃分結果進行評價，其公式為：

（6）

其中，M表示網(wǎng)絡中的所有邊的權重總和，Oi和Oj分別表示節(jié)點i和節(jié)點j所屬的社團的個數(shù)，Wi.表示與節(jié)點i有連接的邊的權值總和，Wj.表示與節(jié)點j有連接的邊的權值總和，如果節(jié)點i和節(jié)點j同屬于一個派系，則δ（ci， cj）=1，否則δ（ci， cj）=0。

4 實驗效果分析

本文采用的是某地市2016年1月1日至2016年12月30日一年某運營商移動用戶的通話詳單數(shù)據(jù)，該數(shù)據(jù)大小為436 G，包含150多萬用戶發(fā)生通話的基站位置、通話對象、通話日期等相關信息。在下面的實驗中，本文重點對比改進后的CPM與傳統(tǒng)的CPM算法結果，驗證算法對劃分移動社交社會網(wǎng)絡的可用性。

本文通過分析移動社交網(wǎng)絡的屬性，發(fā)現(xiàn)該社交網(wǎng)絡中含有大量的三角形，也就是移動社會網(wǎng)絡中大多數(shù)的3-派系，因此本文僅僅分析k=3和k=4的算法對比結果，其他k值本文暫時不做考慮。通過圖4可以看出，k=3的EQ值總體上高于k=4的EQ值，而且從EQ值的變化趨勢可知，當變異系數(shù)在[0.5， 0.6]之間變化時，其EQ值趨于穩(wěn)定的狀態(tài)。本文采用公式（5）計算的權重變異系數(shù)閾值C.V*值0.513 85落在該區(qū)間內(nèi)，實驗結論表明，采用Farkas派系強度函數(shù)計算派系權重變異系數(shù)閾值C.V*的方法是有效的，提升了算法的擴展性。

除此之外，變異系數(shù)閾值C.V*體現(xiàn)構成派系條件的苛刻程度，閾值越小，表示模型對派系邊權重的離散程度的要求越苛刻，一些真實的社團可能不會被認為是派系，社團劃分結果中社團內(nèi)部連接非常緊密。相反，閾值越小表示模型對派系邊權重的離散程度的要求越寬泛，很多不相關的社團可能會被劃分進來，社團劃分的結果是社團內(nèi)部連接非常松散。

根據(jù)上述流程得出改進后的CPM與傳統(tǒng)的CPM算法的EQ值對比結果如圖5所示。

由圖5可知，改進后CPM算法的EQ評價值高于傳統(tǒng)的CPM算法EQ評價值。實驗結果表明，改進后的CPM算法經(jīng)過一系列的數(shù)據(jù)預處理、閾值設置處理的步驟，能夠在很大程度上剔除不合理的節(jié)點以及不滿足條件的相關派系，能夠在很大程度上保證算法所得到的結果符合社團劃分的標準。

5 結束語

本文利用移動用戶的通信數(shù)據(jù)提取用戶的社交網(wǎng)絡，采用改進CPM的算法來實現(xiàn)通信用戶關系圈的挖掘。實驗表明，在同等的k值情況下，改進的CPM算法經(jīng)過一系列數(shù)據(jù)處理后，能夠在很大程度上保證算法的精度。除此之外，該算法經(jīng)過對數(shù)據(jù)預處理、閾值設置處理等步驟剔除不合理的節(jié)點以及不滿足條件的相關派系，能夠在很大程度上滿足海量通信用戶社團的劃分要求，因此，改進后的CPM算法相比傳統(tǒng)的CPM實驗法具有更大的擴展優(yōu)勢。

參考文獻：

[1] Palla G， Dernyi I， Farkas I， et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature， 2005，435（9）： 814-818.

[2] Lancichinetti A， Fortunato S， Kertesz J. Detecting the Overlapping and Hierarchical Community Structure in Complex Networks[J]. New Journal of Physics， 2009（11）： 033015.

[3] Evans T， Lambiotte R. Line Graphs， Link Partitions， and Overlapping Communities[J]. Physical Review E， 2009，80（1）： 016105.

[4] Ahn Y Y， Bagrow J P， Lehmann S. Link Communities Reveal Multiscale Complexity in Networks[J]. Nature， 2010，466（7307）： 761.

[5] Onnela J P， Saramaki J， Hyvonen J， et a1. Structure and tie strengths in mobile communication networks[J]. Proceedings of the National Academy of Sciences， 2007，104（18）： 7332-7336.

[6] Kumpula J M， Onnela J P， Saramaki J， et a1. Emergence of communities in weighted networks[J]. Physical Review Letters， 2007，99（22）.

[7] 吳文濤，肖仰華，何震瀛，等. 基于權重信息挖掘社會網(wǎng)絡中的隱含社團[C]//Ndbc中國數(shù)據(jù)庫學術會議， 2009.

[8] Shen H， Cheng K， Cai M， et al. Detect overlapping and hierarchical community structure in networks[J]. Physica A： Statistical Mechanics and its Applications， 2009，388（8）： 1706-1712.

[9] Duan Y， Lu F. Structural robustness of city road networks based on community[J]. Computers Environment and Urban Systems， 2013（41）： 75-87.

[10] 蔣仕寶，陳少權. 基于呼叫指紋的重入網(wǎng)識別算法研究[J]. 移動通信， 2016，40（22）： 27-30.

[11] 呂明玲. 基于通話記錄和短信記錄的關系圈挖掘[D]. 廣州： 華南理工大學， 2014.