陳少權(quán) 杜翠鳳

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

【關(guān)鍵詞】關(guān)系強(qiáng)度；時(shí)間衰減；關(guān)系閾值；變異系數(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 引言

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

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

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

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

TF-IDFuv=tfuv×idfuv （1）

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

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

（2）

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

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

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

3.4 引用時(shí)間衰減因子衡量移動(dòng)用戶之間連接關(guān)

系強(qiáng)度

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

（3）

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

3.5 構(gòu)建基于變異系數(shù)的帶權(quán)派系

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

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

圖3 用戶u、用戶v、用戶x構(gòu)成的3-派系

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

（4）

其中，σ表示該派系中權(quán)重的標(biāo)準(zhǔn)差，μ表示改派系中權(quán)重的平均值。

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

（5）

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

3.6 挖掘重疊社團(tuán)，評(píng)價(jià)社團(tuán)劃分質(zhì)量

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

（6）

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

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

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

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

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

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

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

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

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

參考文獻(xiàn)：

[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] 吳文濤，肖仰華，何震瀛，等. 基于權(quán)重信息挖掘社會(huì)網(wǎng)絡(luò)中的隱含社團(tuán)[C]//Ndbc中國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議， 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] 蔣仕寶，陳少權(quán). 基于呼叫指紋的重入網(wǎng)識(shí)別算法研究[J]. 移動(dòng)通信， 2016，40（22）： 27-30.

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